Under the auspices of the Computational Complexity Foundation (CCF)

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

Revisions: 1

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 >>> TR20-066 | 28th April 2020 Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal #### Quantum Implications of Huang's Sensitivity Theorem Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function$f$, the deterministic query complexity,$D(f)$, is at most quartic in the quantum query complexity,$Q(f)$:$D(f) = O(Q(f)^4)\$. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, ... more >>>

ISSN 1433-8092 | Imprint