Satyanarayana V. Lokam

On the Sensitivity Conjecture for Read-k Formulas.

2016 · Electronic colloquium on computational complexity

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 …