Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with circuit lower bound:
TR11-086 | 2nd June 2011
Masaki Yamamoto

A tighter lower bound on the circuit size of the hardest Boolean functions

In [IPL2005],
Frandsen and Miltersen improved bounds on the circuit size $L(n)$ of the hardest Boolean function on $n$ input bits:
for some constant $c>0$:
\left(1+\frac{\log n}{n}-\frac{c}{n}\right)
\left(1+3\frac{\log n}{n}+\frac{c}{n}\right)
In this note,
we announce a modest ... more >>>

TR12-071 | 29th May 2012
Kazuhisa Seto, Suguru Tamaki

A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis

We present a moderately exponential time algorithm for the satisfiability of Boolean formulas over the full binary basis.
For formulas of size at most $cn$, our algorithm runs in time $2^{(1-\mu_c)n}$ for some constant $\mu_c>0$.
As a byproduct of the running time analysis of our algorithm,
we get strong ... more >>>

TR16-085 | 28th May 2016
Shiteng Chen, Periklis Papakonstantinou

Depth-reduction for composites

We obtain a new depth-reduction construction, which implies a super-exponential improvement in the depth lower bound separating $NEXP$ from non-uniform $ACC$.

In particular, we show that every circuit with $AND,OR,NOT$, and $MOD_m$ gates, $m\in\mathbb{Z}^+$, of polynomial size and depth $d$ can be reduced to a depth-$2$, $SYM\circ AND$, circuit of ... more >>>

TR16-100 | 27th June 2016
Suguru Tamaki

A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates

We consider depth 2 unbounded fan-in circuits with symmetric and linear threshold gates. We present a deterministic algorithm that, given such a circuit with $n$ variables and $m$ gates, counts the number of satisfying assignments in time $2^{n-\Omega\left(\left(\frac{n}{\sqrt{m} \cdot \poly(\log n)}\right)^a\right)}$ for some constant $a>0$. Our algorithm runs in time ... more >>>

TR18-188 | 7th November 2018
Zeev Dvir, Alexander Golovnev, Omri Weinstein

Static Data Structure Lower Bounds Imply Rigidity

Revisions: 2

We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower bound of $t \geq \omega(\log^2 n)$ on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small ... more >>>

TR20-122 | 8th August 2020
Joshua Cook

Size Bounds on Low Depth Circuits for Promise Majority

Revisions: 3

We give two results on the size of AC0 circuits computing promise majority. $\epsilon$-promise majority is majority promised that either at most an $\epsilon$ fraction of the input bits are 1, or at most $\epsilon$ are 0.

First, we show super quadratic lower bounds on both monotone and general depth ... more >>>

TR20-183 | 6th December 2020
Rahul Ilango

Constant Depth Formula and Partial Function Versions of MCSP are Hard

Attempts to prove the intractability of the Minimum Circuit Size Problem (MCSP) date as far back as the 1950s and are well-motivated by connections to cryptography, learning theory, and average-case complexity. In this work, we make progress, on two fronts, towards showing MCSP is intractable under worst-case assumptions.

While ... more >>>

ISSN 1433-8092 | Imprint