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 𝐵𝑘
Certificate complexity X 。 Restricting a few variables fixes the function value. Eg.Fixing three edges make a graph to have a triangle. .C(f,x)=the minimum number of variables needed to be restricted to fix f(x). Certificate complexity of f: C(f)=max C(f,x) 2
Certificate complexity • Restricting a few variables fixes the function value. – Eg. Fixing three edges make a graph to have a triangle. • 𝐶 𝑓, 𝑥 = the minimum number of variables needed to be restricted to fix 𝑓 𝑥 . • Certificate complexity of 𝑓: 𝐶 𝑓 = max 𝑥 𝐶 𝑓, 𝑥 𝑥
decision tree complexity ·Task:compute f(x) f(x1,x2,x3)=x1A(x2 VX3) 。The variables x;are X1=? unknown and can be 0 accessed by queries f(x1,X2,x3=0 ·Decision tree X2=? complexity DT(f):the minimum depth of a X3=? f(x1,x2,x3)=1 decision tree that computes f. f(x1,x2,x3=0 f(x1,x2,x3)1
decision tree complexity 0 1 0 1 0 1 𝑓 𝑥1 , 𝑥2 ,𝑥3 = 𝑥1 ∧ (𝑥2 ∨ 𝑥3 ) • Task: compute 𝑓 𝑥 • The variables 𝑥𝑖 are unknown and can be accessed by queries. • Decision tree complexity 𝐷𝑇 𝑓 : the minimum depth of a decision tree that computes 𝑓
Big open question 1 There are many other complexity measures. Polynomial degree,randomized/quantum DT,.. 。It turns out that for any f:{0,1n→{0，l,all these measures are polynomially related... -e.g.bs(f)≤C(f)≤DT(f)≤bs(f)3 ....except for sensitivity s(f). No example separates s(f)from the family. Sensitivity Conjecture:bs(f)=poly(s(f))
Big open question 1 • There are many other complexity measures. – Polynomial degree, randomized/quantum DT, … • It turns out that for any 𝑓: 0,1 𝑛 → 0,1 , all these measures are polynomially related… – e.g. 𝑏𝑠 𝑓 ≤ 𝐶 𝑓 ≤ 𝐷𝑇 𝑓 ≤ 𝑏𝑠 𝑓 3 • …except for sensitivity 𝑠 𝑓 . • No example separates 𝑠 𝑓 from the family. • Sensitivity Conjecture: 𝑏𝑠 𝑓 = 𝑝𝑜𝑙𝑦 𝑠 𝑓
Communication complexity F(x,y) Two parties,Alice and Bob,jointly compute a function F on input (x,y). -x known only to Alice and y only to Bob. Communication complexity*1:how many bits are needed to be exchanged? *1.A.Ya0.STOC,1979
Communication complexity • Two parties, Alice and Bob, jointly compute a function 𝐹 on input (𝑥, 𝑦). – 𝑥 known only to Alice and 𝑦 only to Bob. • Communication complexity* 1 : how many bits are needed to be exchanged? 𝐹(𝑥, 𝑦) 𝑥 𝑦 *1. A. Yao. STOC, 1979
Log-rank conjecture Not only interesting on its own,but also important because of numerous applications to prove lower bounds. 0 Question:How to lower bound communication complexity itself? y Communication matrix X→ F(x,y) ME [F(x,y)]x.y: 10
Log-rank conjecture • Not only interesting on its own, but also important because of numerous applications. – to prove lower bounds. • Question: How to lower bound communication complexity itself? • Communication matrix 𝑀𝐹 ≝ 𝐹 𝑥, 𝑦 𝑥,𝑦: 10 𝑥 → 𝑦 ↓ 𝐹(𝑥, 𝑦)