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 bounds:
TR02-055 | 13th September 2002
Valentine Kabanets, Russell Impagliazzo

Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

Revisions: 1

We show that derandomizing Polynomial Identity Testing is,
essentially, equivalent to proving circuit lower bounds for
NEXP. More precisely, we prove that if one can test in polynomial
time (or, even, nondeterministic subexponential time, infinitely
often) whether a given arithmetic circuit over integers computes an
identically zero polynomial, then either ... more >>>

TR05-040 | 13th April 2005
Scott Aaronson

Oracles Are Subtle But Not Malicious

Theoretical computer scientists have been debating the role of
oracles since the 1970's. This paper illustrates both that oracles
can give us nontrivial insights about the barrier problems in
circuit complexity, and that they need not prevent us from trying to
solve those problems.

First, we ... more >>>

TR06-003 | 8th January 2006
Joshua Buresh-Oppenheim, Rahul Santhanam

Making Hard Problems Harder

We consider a general approach to the hoary problem of (im)proving circuit lower bounds. We define notions of hardness condensing and hardness extraction, in analogy to the corresponding notions from the computational theory of randomness. A hardness condenser is a procedure that takes in a Boolean function as input, as ... more >>>

TR07-005 | 17th January 2007
Rahul Santhanam

Circuit Lower Bounds for Merlin-Arthur Classes

We show that for each k > 0, MA/1 (MA with 1 bit of advice) does not have circuits of size n^k. This implies the first superlinear circuit lower bounds for the promise versions of the classes MA, AM and ZPP_{||}^{NP}.

We extend our main result in several ways. For ... more >>>

TR10-105 | 29th June 2010
Scott Aaronson, Dieter van Melkebeek

A note on circuit lower bounds from derandomization

We present an alternate proof of the result by Kabanets and Impagliazzo that derandomizing polynomial identity testing implies circuit lower bounds. Our proof is simpler, scales better, and yields a somewhat stronger result than the original argument.

more >>>

TR10-129 | 16th August 2010
Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel

Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds

The area of derandomization attempts to provide efficient deterministic simulations of randomized algorithms in various algorithmic settings. Goldreich and Wigderson introduced a notion of "typically-correct" deterministic simulations, which are allowed to err on few inputs. In this paper we further the study of typically-correct derandomization in two ways.

First, we ... more >>>

TR10-174 | 12th November 2010
Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John Hitchcock, Dieter van Melkebeek

A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games

We present an alternate proof of the recent result by Gutfreund and Kawachi that derandomizing Arthur-Merlin games into $P^{NP}$ implies linear-exponential circuit lower bounds for $E^{NP}$. Our proof is simpler and yields stronger results. In particular, consider the promise-$AM$ problem of distinguishing between the case where a given Boolean circuit ... more >>>

TR11-125 | 16th September 2011
Andrew Drucker

Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators

Revisions: 1 , Comments: 1

We study the circuit complexity of Boolean operators, i.e., collections of Boolean functions defined over a common input. Our focus is the well-studied model in which arbitrary Boolean functions are allowed as gates, and in which a circuit's complexity is measured by its depth and number of wires. We show ... more >>>

TR11-131 | 29th September 2011
Rahul Santhanam, Srikanth Srinivasan

On the Limits of Sparsification

Impagliazzo, Paturi and Zane (JCSS 2001) proved a sparsification lemma for $k$-CNFs:
every k-CNF is a sub-exponential size disjunction of $k$-CNFs with a linear
number of clauses. This lemma has subsequently played a key role in the study
of the exact complexity of the satisfiability problem. A natural question is
more >>>

TR11-133 | 4th October 2011
Maurice Jansen, Rahul Santhanam

Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent

Suppose $f$ is a univariate polynomial of degree $r=r(n)$ that is computed by a size $n$ arithmetic circuit.
It is a basic fact of algebra that a nonzero univariate polynomial of degree $r$ can vanish on at most $r$ points. This implies that for checking whether $f$ is identically zero, ... more >>>

TR12-084 | 3rd July 2012
Rahul Santhanam

Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds

I discuss recent progress in developing and exploiting connections between
SAT algorithms and circuit lower bounds. The centrepiece of the article is
Williams' proof that $NEXP \not \subseteq ACC^0$, which proceeds via a new
algorithm for $ACC^0$-SAT beating brute-force search. His result exploits
a formal connection from non-trivial SAT algorithms ... more >>>

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-043 | 25th March 2013
Oded Goldreich, Avi Wigderson

On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions

Revisions: 1

We propose that multi-linear functions of relatively low degree
over GF(2) may be good candidates for obtaining exponential
lower bounds on the size of constant-depth Boolean circuits
(computing explicit functions).
Specifically, we propose to move gradually from linear functions
to multilinear ones, and conjecture that, for any $t\geq2$,
more >>>

TR13-057 | 5th April 2013
Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman

Mining Circuit Lower Bound Proofs for Meta-Algorithms

We show that circuit lower bound proofs based on the method of random restrictions yield non-trivial compression algorithms for ``easy'' Boolean functions from the corresponding circuit classes. The compression problem is defined as follows: given the truth table of an $n$-variate Boolean function $f$ computable by some unknown small circuit ... more >>>

TR13-077 | 14th May 2013
Ján Pich

Circuit Lower Bounds in Bounded Arithmetics

We prove that $T_{NC^1}$, the true universal first-order theory in the language containing names for all uniform $NC^1$ algorithms, cannot prove that for sufficiently large $n$, SAT is not computable by circuits of size $n^{2kc}$ where $k\geq 1, c\geq 4$ unless each function $f\in SIZE(n^k)$ can be approximated by formulas ... more >>>

TR13-108 | 9th August 2013
Rahul Santhanam, Ryan Williams

New Algorithms for QBF Satisfiability and Implications for Circuit Complexity

Revisions: 1

We revisit the complexity of the satisfiability problem for quantified Boolean formulas. We show that satisfiability
of quantified CNFs of size $\poly(n)$ on $n$ variables with $O(1)$
quantifier blocks can be solved in time $2^{n-n^{\Omega(1)}}$ by zero-error
randomized algorithms. This is the first known improvement over brute force search in ... more >>>

TR13-117 | 1st September 2013
Igor Oliveira

Algorithms versus Circuit Lower Bounds

Different techniques have been used to prove several transference theorems of the form "nontrivial algorithms for a circuit class C yield circuit lower bounds against C". In this survey we revisit many of these results. We discuss how circuit lower bounds can be obtained from derandomization, compression, learning, and satisfiability ... more >>>

TR13-129 | 17th September 2013
Adam Klivans, Pravesh Kothari, Igor Oliveira

Constructing Hard Functions from Learning Algorithms

Revisions: 1

Fortnow and Klivans proved the following relationship between efficient learning algorithms and circuit lower bounds: if a class $\mathcal{C} \subseteq P/poly$ of Boolean circuits is exactly learnable with membership and equivalence queries in polynomial-time, then $EXP^{NP} \not \subseteq \mathcal{C}$ (the class $EXP^{NP}$ was subsequently improved to $P$ by Hitchcock and ... more >>>

TR14-099 | 7th August 2014
Gil Cohen, Igor Shinkar

The Complexity of DNF of Parities

We study depth 3 circuits of the form $\mathrm{OR} \circ \mathrm{AND} \circ \mathrm{XOR}$, or equivalently -- DNF of parities. This model was first explicitly studied by Jukna (CPC'06) who obtained a $2^{\Omega(n)}$ lower bound for explicit functions. Several related models have gained attention in the last few years, such as ... more >>>

TR14-164 | 30th November 2014
Cody Murray, Ryan Williams

On the (Non) NP-Hardness of Computing Circuit Complexity

The Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function $f$ and a size parameter $k$, is the circuit complexity of $f$ at most $k$? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. Unlike many problems of ... more >>>

TR16-008 | 26th January 2016
Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

Algorithms from Natural Lower Bounds

Circuit analysis algorithms such as learning, SAT, minimum circuit size, and compression imply circuit lower bounds. We show a generic implication in the opposite direction: natural properties (in the sense of Razborov and Rudich) imply randomized learning and compression algorithms. This is the first such implication outside of the derandomization ... more >>>

TR16-119 | 1st August 2016
Alexander Golovnev, Edward Hirsch, Alexander Knop, Alexander Kulikov

On the Limits of Gate Elimination

Although a simple counting argument shows the existence of Boolean functions of exponential circuit complexity, proving superlinear circuit lower bounds for explicit functions seems to be out of reach of the current techniques. There has been a (very slow) progress in proving linear lower bounds with the latest record of ... more >>>

TR17-023 | 15th February 2017
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

The Power of Natural Properties as Oracles

We study the power of randomized complexity classes that are given oracle access to a natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal Circuit Size Problem (MCSP).
We obtain new circuit lower bounds, as well as some hardness results for the relativized version ... more >>>

TR17-026 | 17th February 2017
Valentine Kabanets, Daniel Kane, Zhenjian Lu

A Polynomial Restriction Lemma with Applications

A polynomial threshold function (PTF) of degree $d$ is a boolean function of the form $f=\mathrm{sgn}(p)$, where $p$ is a degree-$d$ polynomial, and $\mathrm{sgn}$ is the sign function. The main result of the paper is an almost optimal bound on the probability that a random restriction of a PTF is ... more >>>

TR17-144 | 27th September 2017
Moritz Müller, Ján Pich

Feasibly constructive proofs of succinct weak circuit lower bounds

We ask for feasibly constructive proofs of known circuit lower bounds for explicit functions on bit strings of length $n$. In 1995 Razborov showed that many can be proved in Cook’s theory $PV_1$, a bounded arithmetic formalizing polynomial time reasoning. He formalized circuit lower bound statements for small $n$ of ... more >>>

TR17-173 | 6th November 2017
Igor Carboni Oliveira, Ruiwen Chen, Rahul Santhanam

An Average-Case Lower Bound against ACC^0

In a seminal work, Williams [Wil14] showed that NEXP (non-deterministic exponential time) does not have polynomial-size ACC^0 circuits. Williams' technique inherently gives a worst-case lower bound, and until now, no average-case version of his result was known.

We show that there is a language L in NEXP (resp. EXP^NP) ... more >>>

TR18-003 | 2nd January 2018
Roei Tell

Proving that prBPP=prP is as hard as "almost" proving that P \ne NP

Revisions: 1

We show that any proof that $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$ necessitates proving circuit lower bounds that almost yield that $\mathcal{P}\ne\mathcal{NP}$. More accurately, we show that if $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$, then for essentially any super-constant function $f(n)=\omega(1)$ it holds that $NTIME[n^{f(n)}]\not\subseteq\mathcal{P}/\mathrm{poly}$. The conclusion of the foregoing conditional statement cannot be improved (to conclude that $\mathcal{NP}\not\subseteq\mathcal{P}/\mathrm{poly}$) without ... more >>>

ISSN 1433-8092 | Imprint