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: 𝑏𝑠 𝑓 = 𝑝𝑜𝑙𝑦 𝑠 𝑓