6533b86ffe1ef96bd12ce729

RESEARCH PRODUCT

A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity

Andris AmbainisKrišjānis Prūsis

subject

Discrete mathematicsOpen problem020206 networking & telecommunications0102 computer and information sciences02 engineering and technologyCertificate01 natural sciencesUpper and lower bounds010201 computation theory & mathematics0202 electrical engineering electronic engineering information engineeringSensitivity (control systems)Boolean functionBlock (data storage)Mathematics

description

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.

yearjournalcountryeditionlanguage
2014-08-2539th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014
10.1007/978-3-662-44465-8_4http://dx.doi.org/10.1007/978-3-662-44465-8_4