Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SENSITIVITY CONJECTURE:
Reports tagged with Sensitivity Conjecture:
TR13-164 | 28th November 2013
Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian

Weak Parity

We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2+eps fraction of input strings, but must do so with high probability on those inputs where one does succeed. It is well-known that ... more >>>


TR16-062 | 18th April 2016
Avishay Tal

On The Sensitivity Conjecture

The sensitivity of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ is the maximal number of neighbors a point in the Boolean hypercube has with different $f$-value. Roughly speaking, the block sensitivity allows to flip a set of bits (called a block) rather than just one bit, in order to change the ... more >>>


TR16-084 | 23rd May 2016
Shalev Ben-David

Low-Sensitivity Functions from Unambiguous Certificates

We provide new query complexity separations against sensitivity for total Boolean functions: a power 3 separation between deterministic (and even randomized or quantum) query complexity and sensitivity, and a power 2.1 separation between certificate complexity and sensitivity. We get these separations by using a new connection between sensitivity and a ... more >>>


TR17-025 | 16th February 2017
Pooya Hatami, Avishay Tal

Pseudorandom Generators for Low-Sensitivity Functions

A Boolean function is said to have maximal sensitivity $s$ if $s$ is the largest number of Hamming neighbors of a point which differ from it in function value. We construct a pseudorandom generator with seed-length $2^{O(\sqrt{s})} \cdot \log(n)$ that fools Boolean functions on $n$ variables with maximal sensitivity at ... more >>>


TR17-192 | 15th December 2017
Krishnamoorthy Dinesh, Jayalal Sarma

Alternation, Sparsity and Sensitivity : Bounds and Exponential Gaps

The well-known Sensitivity Conjecture regarding combinatorial complexity measures on Boolean functions states that for any Boolean function $f:\{0,1\}^n \to \{0,1\}$, block sensitivity of $f$ is polynomially related to sensitivity of $f$ (denoted by $\mathbf{sens}(f)$). From the complexity theory side, the XOR Log-Rank Conjecture states that for any Boolean function, $f:\{0,1\}^n ... more >>>


TR18-205 | 3rd December 2018
Siddhesh Chaubal, Anna Gal

New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity

Nisan and Szegedy conjectured that block sensitivity is at most polynomial in sensitivity for any Boolean function. There is a huge gap between the best known upper bound on block sensitivity in terms of sensitivity - which is exponential, and the best known separating examples - which give only a ... more >>>




ISSN 1433-8092 | Imprint