Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with formula size:
TR09-040 | 20th April 2009
Pavel Hrubes, Stasys Jukna, Alexander Kulikov, Pavel Pudlak

On convex complexity measures

Khrapchenko's classical lower bound $n^2$ on the formula size of the
parity function~$f$ can be interpreted as designing a suitable
measure of subrectangles of the combinatorial rectangle
$f^{-1}(0)\times f^{-1}(1)$. Trying to generalize this approach we
arrived at the concept of \emph{convex measures}. We prove the
more >>>

TR09-051 | 2nd July 2009
Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy

The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory

We continue an investigation into resource-bounded Kolmogorov complexity \cite{abkmr}, which highlights the close connections between circuit complexity and Levin's time-bounded Kolmogorov complexity measure Kt (and other measures with a similar flavor), and also exploits derandomization techniques to provide new insights regarding Kolmogorov complexity.
The Kolmogorov measures that have been ... more >>>

TR12-062 | 17th May 2012
Ilan Komargodski, Ran Raz

Average-Case Lower Bounds for Formula Size

Revisions: 2

We give an explicit function $h:\{0,1\}^n\to\{0,1\}$ such that any deMorgan formula of size $O(n^{2.499})$ agrees with $h$ on at most $\frac{1}{2} + \epsilon$ fraction of the inputs, where $\epsilon$ is exponentially small (i.e. $\epsilon = 2^{-n^{\Omega(1)}}$). Previous lower bounds for formula size were obtained for exact computation.

The same ... more >>>

TR17-034 | 21st February 2017
Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam

On algebraic branching programs of small width

Revisions: 1

In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the ... more >>>

TR17-091 | 17th May 2017
Andrej Bogdanov

Small bias requires large formulas

Revisions: 1

A small-biased function is a randomized function whose distribution of truth-tables is small-biased. We demonstrate that known explicit lower bounds on the size of (1) general Boolean formulas, (2) Boolean formulas of fan-in two, (3) de Morgan formulas, as well as (4) correlation lower bounds against small de Morgan formulas ... more >>>

ISSN 1433-8092 | Imprint