Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with shrinkage:
TR13-024 | 7th February 2013
Valentine Kabanets, Antonina Kolokolova

Compression of Boolean Functions

We consider the problem of compression for ``easy'' Boolean functions: given the truth table of an $n$-variate Boolean function $f$ computable by some \emph{unknown small circuit} from a \emph{known class} of circuits, find in deterministic time $\poly(2^n)$ a circuit $C$ (no restriction on the type of $C$) computing $f$ so ... more >>>

TR13-058 | 5th April 2013
Ilan Komargodski, Ran Raz, Avishay Tal

Improved Average-Case Lower Bounds for DeMorgan Formula Size

Revisions: 2

We give a function $h:\{0,1\}^n\to\{0,1\}$ such that every deMorgan formula of size $n^{3-o(1)}/r^2$ agrees with $h$ on at most a fraction of $\frac{1}{2}+2^{-\Omega(r)}$ of the inputs. This improves the previous average-case lower bound of Komargodski and Raz (STOC, 2013).

Our technical contributions include a theorem that shows that the ``expected ... more >>>

TR13-163 | 28th November 2013
Russell Impagliazzo, Valentine Kabanets

Fourier Concentration from Shrinkage

Revisions: 2

For Boolean functions computed by de Morgan formulas of subquadratic size or read-once de Morgan formulas, we prove a sharp concentration of the Fourier mass on ``small-degree'' coefficients. For a Boolean function $f:\{0,1\}^n\to\{1,-1\}$ computable by a de Morgan formula of size $s$, we show that
\sum_{A\subseteq [n]\; :\; |A|>s^{1/\Gamma ... more >>>

TR14-048 | 10th April 2014
Avishay Tal

Shrinkage of De Morgan Formulae from Quantum Query Complexity

Revisions: 1

We give a new and improved proof that the shrinkage exponent of De Morgan formulae is $2$. Namely, we show that for any Boolean function $f: \{-1,1\}^n \to \{-1,1\}$, setting each variable out of $x_1, \ldots, x_n$ with probability $1-p$ to a randomly chosen constant, reduces the expected formula size ... more >>>

TR15-114 | 18th July 2015
Avishay Tal

#SAT Algorithms from Shrinkage

We present a deterministic algorithm that counts the number of satisfying assignments for any de Morgan formula $F$ of size at most $n^{3-16\epsilon}$ in time $2^{n-n^{\epsilon}}\cdot \mathrm{poly}(n)$, for any small constant $\epsilon>0$. We do this by derandomizing the randomized algorithm mentioned by Komargodski et al. (FOCS, 2013) and Chen et ... more >>>

ISSN 1433-8092 | Imprint