Snstivityora ojre for functions withs alternating numbers Shengyu Zhang The Chinese University of Hong Kong (Joint work with Chengyu Lin) arXiv:1602.06627
Shengyu Zhang The Chinese University of Hong Kong (Joint work with Chengyu Lin) arXiv:1602.06627
Complexity Structural complexity: High-level questions. -P vs.NP.P vs.BPP.P vs.PSPACE.etc. -Many conditional results. ·Concrete complexity Low-level questions. Lower bounds on specific model of computation such as DT,CC,polynomials,etc. -Aim at unconditional results
Complexity • Structural complexity: – High-level questions. – P vs. NP, P vs. BPP, P vs. PSPACE, etc. – Many conditional results. • Concrete complexity – Low-level questions. – Lower bounds on specific model of computation such as DT, CC, polynomials, etc. – Aim at unconditional results
Complexity measures ·Object::f:{0,1}n→{0,1. Complexity measures:some natural measures defined from combinatorial, algebraic and computational perspectives. Related to our work are: Sensitivity,block sensitivity,certificate complexity Decision tree complexity,communication complexity -Polynomial degrees Rank of Boolean matrix
Complexity measures • Object: 𝑓: 0,1 𝑛 → 0,1 . • Complexity measures: some natural measures defined from combinatorial, algebraic and computational perspectives. • Related to our work are: – Sensitivity, block sensitivity, certificate complexity – Decision tree complexity, communication complexity – Polynomial degrees – Rank of Boolean matrix
sensitivity ·Notation:x∈{0,1n,i∈[n],Bs[n. -x:obtained from x by flipping bit i -x5:obtained from x by flipping all bits in B ·x is sensitive to i:f(x)≠f(x). ·s(f,x)={i:f(x)≠f(x)}. Sensitivity of f:s(f)=maxs(f,x). X -A measure of“smoothness
sensitivity • Notation: 𝑥 ∈ 0,1 𝑛 , 𝑖 ∈ [𝑛], 𝐵 ⊆ 𝑛 . – 𝑥 𝑖 : obtained from 𝑥 by flipping bit 𝑖 – 𝑥 𝐵 : obtained from 𝑥 by flipping all bits in 𝐵 • 𝑥 is sensitive to 𝑖: 𝑓 𝑥 ≠ 𝑓 𝑥 𝑖 . • 𝑠 𝑓, 𝑥 = 𝑖: 𝑓 𝑥 ≠ 𝑓 𝑥 𝑖 . • Sensitivity of 𝑓: 𝑠 𝑓 = max 𝑥 𝑠 𝑓, 𝑥 . – A measure of “smoothness
Block sensitivity ·x is sensitive to a block B:f(x)≠f(xB). -Recall:x is sensitive to i if f(x)f(). bs(f,x)=maximum number of disjoint sensitive blocks. X B1 B2 Bk Block sensitivity of f:bs(f)=max bs(f,x). ·By definition,s(f)≤bs(f)
Block sensitivity • 𝑥 is sensitive to a block 𝐵: 𝑓 𝑥 ≠ 𝑓 𝑥 𝐵 . – Recall: 𝑥 is sensitive to 𝑖 if 𝑓 𝑥 ≠ 𝑓 𝑥 𝑖 . • 𝑏𝑠 𝑓, 𝑥 = maximum number of disjoint sensitive blocks. • Block sensitivity of 𝑓: 𝑏𝑠 𝑓 = max 𝑥 𝑏𝑠 𝑓, 𝑥 . • By definition, 𝑠 𝑓 ≤ 𝑏𝑠 𝑓 . 𝑥 𝐵1 𝐵2 𝐵𝑘