TY - GEN
T1 - A tight lower bound on certificate complexity in terms of block sensitivity and sensitivity
AU - Ambainis, Andris
AU - Prusis, Krišjanis
PY - 2014
Y1 - 2014
N2 - Sensitivity, certificate complexity and block sensitivity are widely used Boolean function complexity measures. A longstanding open problem, proposed by Nisan and Szegedy [7], is whether sensitivity and block sensitivity are polynomially related. Motivated by the constructions of functions which achieve the largest known separations, we study the relation between 1-certificate complexity and 0-sensitivity and 0-block sensitivity. Previously the best known lower bound was C1(f) ≤ bs0(f)/2s0(f), achieved by Kenyon and Kutin [6]. We improve this to C1(f) ≥ 3bs0(f)/2s0(f). While this improvement is only by a constant factor, this is quite important, as it precludes achieving a superquadratic separation between bs(f) and s(f) by iterating functions which reach this bound. In addition, this bound is tight, as it matches the construction of Ambainis and Sun [3] up to an additive constant.
AB - Sensitivity, certificate complexity and block sensitivity are widely used Boolean function complexity measures. A longstanding open problem, proposed by Nisan and Szegedy [7], is whether sensitivity and block sensitivity are polynomially related. Motivated by the constructions of functions which achieve the largest known separations, we study the relation between 1-certificate complexity and 0-sensitivity and 0-block sensitivity. Previously the best known lower bound was C1(f) ≤ bs0(f)/2s0(f), achieved by Kenyon and Kutin [6]. We improve this to C1(f) ≥ 3bs0(f)/2s0(f). While this improvement is only by a constant factor, this is quite important, as it precludes achieving a superquadratic separation between bs(f) and s(f) by iterating functions which reach this bound. In addition, this bound is tight, as it matches the construction of Ambainis and Sun [3] up to an additive constant.
UR - https://www.scopus.com/pages/publications/84906268850
U2 - 10.1007/978-3-662-44465-8_4
DO - 10.1007/978-3-662-44465-8_4
M3 - Conference paper
AN - SCOPUS:84906268850
SN - 9783662444641
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 33
EP - 44
BT - Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Proceedings
PB - Springer Verlag
T2 - 39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014
Y2 - 25 August 2014 through 29 August 2014
ER -