Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with deMorgan formulas:
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 >>>

TR23-184 | 22nd November 2023
Gabriel Bathie, Ryan Williams

Towards Stronger Depth Lower Bounds

A fundamental problem in circuit complexity is to find explicit functions that require large depth to compute. When considering the natural DeMorgan basis of $\{\text{OR},\text{AND}\}$, where negations incur no cost, the best known depth lower bounds for an explicit function in NP have the form $(3-o(1))\log_2 n$, established by H{\aa}stad ... more >>>

ISSN 1433-8092 | Imprint