Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Read-$k$ formulas:
TR16-132 | 23rd August 2016
Mitali Bafna, Satyanarayana V. Lokam, S├ębastien Tavenas, Ameya Velingker

On the Sensitivity Conjecture for Read-k Formulas

Various combinatorial/algebraic parameters are used to quantify the complexity of a Boolean function. Among them, sensitivity is one of the simplest and block sensitivity is one of the most useful. Nisan (1989) and Nisan and Szegedy (1991) showed that block sensitivity and several other parameters, such as certificate complexity, decision ... more >>>

ISSN 1433-8092 | Imprint