Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with boolean function complexity:
TR06-049 | 9th April 2006
Guy Wolfovitz

The Complexity of Depth-3 Circuits Computing Symmetric Boolean Functions

We give tight lower bounds for the size of depth-3 circuits with limited bottom fanin computing symmetric Boolean functions. We show that any depth-3 circuit with bottom fanin $k$ which computes the Boolean function $EXACT_{n/(k+1)}^{n}$, has at least $(1+1/k)^{n+\O(\log n)}$ gates. We show that this lower bound is tight, by ... more >>>

TR13-051 | 2nd April 2013
Eric Blais, Li-Yang Tan

Approximating Boolean functions with depth-2 circuits

We study the complexity of approximating Boolean functions with DNFs and other depth-2 circuits, exploring two main directions: universal bounds on the approximability of all Boolean functions, and the approximability of the parity function.
In the first direction, our main positive results are the first non-trivial universal upper bounds on ... more >>>

TR22-001 | 28th December 2021
Yogesh Dahiya, Meena Mahajan

On (Simple) Decision Tree Rank

In the decision tree computation model for Boolean functions, the depth corresponds to query complexity, and size corresponds to storage space. The depth measure is the most well-studied one, and is known to be polynomially related to several non-computational complexity measures of functions such as certificate complexity. The size measure ... more >>>

ISSN 1433-8092 | Imprint