Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > CIRCUIT COMPLEXITY:
Reports tagged with circuit complexity:
TR94-012 | 12th December 1994

#### Bounds for the Computational Power and Learning Complexity of Analog Neural Nets

It is shown that high order feedforward neural nets of constant depth with piecewise
polynomial activation functions and arbitrary real weights can be simulated for boolean
inputs and outputs by neural nets of a somewhat larger size and depth with heaviside
gates and weights ... more >>>

TR95-027 | 30th May 1995
Frederic Green

#### Lower Bounds for Circuits with Mod Gates and One Exact Threshold Gate

We say an integer polynomial $p$, on Boolean inputs, weakly
$m$-represents a Boolean function $f$ if $p$ is non-constant and is zero (mod
$m$), whenever $f$ is zero. In this paper we prove that if a polynomial
weakly $m$-represents the Mod$_q$ function on $n$ inputs, where $q$ and $m$
more >>>

TR95-051 | 16th October 1995
Pascal Koiran

#### VC Dimension in Circuit Complexity

The main result of this paper is a Omega(n^{1/4}) lower bound
on the size of a sigmoidal circuit computing a specific AC^0_2 function.
This is the first lower bound for the computation model of sigmoidal
circuits with unbounded weights. We also give upper and lower bounds for
the ... more >>>

TR96-002 | 10th January 1996
Manindra Agrawal, Eric Allender

#### An Isomorphism Theorem for Circuit Complexity

We show that all sets complete for NC$^1$ under AC$^0$
reductions are isomorphic under AC$^0$-computable isomorphisms.

Although our proof does not generalize directly to other
complexity classes, we do show that, for all complexity classes C
closed under NC$^1$-computable many-one reductions, the sets ... more >>>

TR96-004 | 18th January 1996

#### Deterministic Restrictions in Circuit Complexity

We study the complexity of computing Boolean functions using AND, OR
and NOT gates. We show that a circuit of depth $d$ with $S$ gates can
be made to output a constant by setting $O(S^{1-\epsilon(d)})$ (where
$\epsilon(d) = 4^{-d}$) of its input values. This implies a
superlinear size lower bound ... more >>>

TR96-023 | 21st March 1996
Eric Allender

#### A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy

A very recent paper by Caussinus, McKenzie, Therien, and Vollmer
[CMTV] shows that ACC^0 is properly contained in ModPH, and TC^0
is properly contained in the counting hierarchy. Thus, [CMTV] shows
that there are problems in ModPH that require superpolynomial-size
uniform ACC^0 ... more >>>

TR96-024 | 21st March 1996
Eric Allender, Robert Beals, Mitsunori Ogihara

#### The complexity of matrix rank and feasible systems of linear equations

We characterize the complexity of some natural and important
problems in linear algebra. In particular, we identify natural
complexity classes for which the problems of (a) determining if a
system of linear equations is feasible and (b) computing the rank of
an integer matrix, ... more >>>

TR96-030 | 31st March 1996
Meera Sitharam

#### Approximation from linear spaces and applications to complexity

We develop an analytic framework based on
linear approximation and point out how a number of complexity
related questions --
on circuit and communication
complexity lower bounds, as well as
pseudorandomness, learnability, and general combinatorics
of Boolean functions --
fit neatly into this framework. ... more >>>

TR96-041 | 24th July 1996
Oded Goldreich, Avi Wigderson

#### On the Circuit Complexity of Perfect Hashing

We consider the size of circuits which perfectly hash
an arbitrary subset $S\!\subset\!\bitset^n$ of cardinality $2^k$
into $\bitset^m$.
We observe that, in general, the size of such circuits is
exponential in $2k-m$,
and provide a matching upper bound.

more >>>

TR96-049 | 9th September 1996
Per Enflo, Meera Sitharam

#### Stable basis families and complexity lower bounds

--
Scalar product estimates have so far been used in
proving several unweighted threshold lower bounds.
We show that if a basis set of Boolean functions satisfies
certain weak stability conditions, then
scalar product estimates
yield lower bounds for the size of weighted thresholds
of these basis functions.
Stable ... more >>>

TR96-055 | 22nd October 1996
Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

#### Hitting Properties of Hard Boolean Operators and their Consequences on BPP

We present the first worst-case hardness conditions
on the circuit complexity of EXP functions which are
sufficient to obtain P=BPP. In particular, we show that
from such hardness conditions it is possible to construct
quick Hitting Sets Generators with logarithmic prize.
... more >>>

TR98-056 | 31st August 1998
Anna Bernasconi, Igor E. Shparlinski

#### Circuit Complexity of Testing Square-Free Numbers

In this paper we extend the area of applications of
the Abstract Harmonic Analysis to the field of Boolean function complexity.
In particular, we extend the class of functions to which
a spectral technique developed in a series of works of the first author
can be applied.
This extension ... more >>>

TR98-067 | 12th November 1998
Paul Beame

#### Propositional Proof Complexity: Past, Present and Future

Proof complexity, the study of the lengths of proofs in
propositional logic, is an area of study that is fundamentally connected
both to major open questions of computational complexity theory and
to practical properties of automated theorem provers. In the last
decade, there have been a number of significant advances ... more >>>

TR98-070 | 7th December 1998
Rüdiger Reischuk

#### Can Large Fanin Circuits Perform Reliable Computations in the Presence of Noise?

For ordinary circuits with a fixed upper bound on the maximal fanin
of gates it has been shown that logarithmic redundancy is necessary and
sufficient to overcome random hardware faults.
Here, we consider the same question for unbounded fanin circuits that
in the noiseless case can compute ... more >>>

TR01-009 | 5th January 2001
Ronen Shaltiel

#### Towards proving strong direct product theorems

A fundamental question of complexity theory is the direct product
question. Namely weather the assumption that a function $f$ is hard on
average for some computational class (meaning that every algorithm from
the class has small advantage over random guessing when computing $f$)
entails that computing $f$ on ... more >>>

TR01-067 | 18th September 2001
Hubie Chen

#### Polynomial Programs and the Razborov-Smolensky Method

Representations of boolean functions as polynomials (over rings) have
been used to establish lower bounds in complexity theory. Such
representations were used to great effect by Smolensky, who
established that MOD q \notin AC^0[MOD p] (for distinct primes p, q)
by representing AC^0[MOD p] functions as low-degree multilinear
polynomials over ... more >>>

TR01-070 | 24th October 2001
Robert Albin Legenstein

#### Total Wire Length as a Salient Circuit Complexity Measure for Sensory Processing

We introduce em total wire length as salient complexity measure
for analyzing the circuit complexity of sensory processing in
biological neural systems and neuromorphic engineering. The new
complexity measure is applied in this paper to two basic
computational problems that arise in translation- and
scale-invariant pattern recognition, and hence appear ... more >>>

TR01-071 | 24th October 2001
Robert Albin Legenstein

#### Neural Circuits for Pattern Recognition with Small Total Wire Length

One of the most basic pattern recognition problems is whether a
certain local feature occurs in some linear array to the left of
solve this problem with an asymptotically optimal number of
threshold gates. Furthermore it is shown that ... more >>>

TR01-095 | 12th November 2001
Hubie Chen

#### Arithmetic Versions of Constant Depth Circuit Complexity Classes

The boolean circuit complexity classes
AC^0 \subseteq AC^0[m] \subseteq TC^0 \subseteq NC^1 have been studied
intensely. Other than NC^1, they are defined by constant-depth
circuits of polynomial size and unbounded fan-in over some set of
allowed gates. One reason for interest in these classes is that they
contain the ... more >>>

TR03-067 | 14th August 2003
Ran Raz

#### Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size

An arithmetic formula is multi-linear if the polynomial computed
by each of its sub-formulas is multi-linear. We prove that any
multi-linear arithmetic formula for the permanent or the
determinant of an $n \times n$ matrix is of size super-polynomial
in $n$.

more >>>

TR04-042 | 21st May 2004
Ran Raz

#### Multilinear-$NC_1$ $\ne$ Multilinear-$NC_2$

An arithmetic circuit or formula is multilinear if the polynomial
computed at each of its wires is multilinear.
We give an explicit example for a polynomial $f(x_1,...,x_n)$,
with coefficients in $\{0,1\}$, such that over any field:
1) $f$ can be computed by a polynomial-size multilinear circuit
of depth $O(\log^2 ... more >>> TR04-044 | 1st June 2004 Eric Allender, Harry Buhrman, Michal Koucky #### What Can be Efficiently Reduced to the Kolmogorov-Random Strings? We investigate the question of whether one can characterize complexity classes (such as PSPACE or NEXP) in terms of efficient reducibility to the set of Kolmogorov-random strings R_C. We show that this question cannot be posed without explicitly dealing with issues raised by the choice of universal machine in the ... more >>> TR04-047 | 22nd April 2004 Xiaoyang Gu #### A note on dimensions of polynomial size circuits In this paper, we use resource-bounded dimension theory to investigate polynomial size circuits. We show that for every$i\geq 0$,$\Ppoly$has$i$th order scaled$\pthree$-strong dimension$0$. We also show that$\Ppoly^\io$has$\pthree$-dimension$1/2$,$\pthree$-strong dimension$1$. Our results improve previous measure results of Lutz (1992) and dimension ... more >>> TR04-056 | 1st July 2004 Vinodchandran Variyam #### A note on the circuit complexity of PP In this short note we show that for any integer k, there are languages in the complexity class PP that do not have Boolean circuits of size$n^k$. more >>> TR04-108 | 24th November 2004 Eric Allender, Samir Datta, Sambuddha Roy #### Topology inside NC^1 We show that ACC^0 is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar constant-width circuits also characterize ACC^0. Thus polylogarithmic genus provides no additional computational power in this model. We consider other generalizations of ... more >>> TR05-018 | 6th February 2005 Oded Goldreich #### On Promise Problems (a survey in memory of Shimon Even [1935-2004]) The notion of promise problems was introduced and initially studied by Even, Selman and Yacobi (Information and Control, Vol.~61, pages 159-173, 1984). In this article we survey some of the applications that this notion has found in the twenty years that elapsed. These include the notion ... more >>> TR05-049 | 1st April 2005 Joan Boyar, rene peralta #### The Exact Multiplicative Complexity of the Hamming Weight Function We consider the problem of computing the Hamming weight of an n-bit vector using a circuit with gates for GF2 addition and multiplication only. We show the number of multiplications necessary and sufficient to build such a circuit is n - |n| where |n| is the Hamming weight of the ... more >>> TR05-070 | 6th July 2005 Mahdi Cheraghchi #### On Matrix Rigidity and the Complexity of Linear Forms The rigidity function of a matrix is defined as the minimum number of its entries that need to be changed in order to reduce the rank of the matrix to below a given parameter. Proving a strong enough lower bound on the rigidity of a matrix implies a nontrivial lower ... more >>> 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 >>> TR06-107 | 26th August 2006 Arkadev Chattopadhyay #### An improved bound on correlation between polynomials over Z_m and MOD_q Revisions: 1 Let m,q > 1 be two integers that are co-prime and A be any subset of Z_m. Let P be any multi-linear polynomial of degree d in n variables over Z_m. We show that the MOD_q boolean function on n variables has correlation at most exp(-\Omega(n/(m2^{m-1})^d)) with the boolean function ... more >>> TR06-138 | 13th November 2006 Kei Uchizawa, Rodney Douglas #### Energy Complexity and Entropy of Threshold Circuits Circuits composed of threshold gates (McCulloch-Pitts neurons, or perceptrons) are simplified models of neural circuits with the advantage that they are theoretically more tractable than their biological counterparts. However, when such threshold circuits are designed to perform a specific computational task they usually differ ... more >>> TR08-038 | 4th April 2008 Eric Allender, Michal Koucky #### Amplifying Lower Bounds by Means of Self-Reducibility Revisions: 2 We observe that many important computational problems in NC^1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC^0 circuits if and only if it has TC^0 circuits of size n^{1+\epsilon} for every \epsilon > 0 (counting the ... more >>> TR09-011 | 31st January 2009 Mark Braverman #### Poly-logarithmic independence fools AC0 circuits We prove that poly-sized AC0 circuits cannot distinguish a poly-logarithmically independent distribution from the uniform one. This settles the 1990 conjecture by Linial and Nisan [LN90]. The only prior progress on the problem was by Bazzi [Baz07], who showed that O(log^2 n)-independent distributions fool poly-size DNF formulas. Razborov [Raz08] has ... 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 >>> TR09-085 | 14th September 2009 Christoph Behle, Andreas Krebs, Stephanie Reifferscheid #### An Approach to characterize the Regular Languages in TC0 with Linear Wires Revisions: 1 We consider the regular languages recognized by weighted threshold circuits with a linear number of wires. We present a simple proof to show that parity cannot be computed by such circuits. Our proofs are based on an explicit construction to restrict the input of the circuit such that the value ... more >>> TR09-146 | 29th December 2009 Dan Gutfreund, Akinori Kawachi #### Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds We show that if Arthur-Merlin protocols can be derandomized, then there is a Boolean function computable in deterministic exponential-time with access to an NP oracle, that cannot be computed by Boolean circuits of exponential size. More formally, if$\mathrm{prAM}\subseteq \mathrm{P}^{\mathrm{NP}}$then there is a Boolean function in$\mathrm{E}^{\mathrm{NP}}$that requires ... more >>> TR11-095 | 22nd June 2011 Christoph Behle, Andreas Krebs, Klaus-Joern Lange, Pierre McKenzie #### Low uniform versions of NC1 Revisions: 1 In the setting known as DLOGTIME-uniformity, the fundamental complexity classes$AC^0\subset ACC^0\subseteq TC^0\subseteq NC^1$have several robust characterizations. In this paper we refine uniformity further and examine the impact of these refinements on$NC^1$and its subclasses. When applied to the logarithmic circuit depth characterization of$NC^1$, some refinements leave ... more >>> TR11-128 | 21st September 2011 Michael Elberfeld, Andreas Jakoby, Till Tantau #### Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth An algorithmic meta theorem for a logic and a class$C$of structures states that all problems expressible in this logic can be solved efficiently for inputs from$C$. The prime example is Courcelle's Theorem, which states that monadic second-order (MSO) definable problems are linear-time solvable on graphs of bounded ... more >>> TR11-145 | 2nd November 2011 Alexander A. Sherstov #### The Multiparty Communication Complexity of Set Disjointness We study the set disjointness problem in the number-on-the-forehead model. (i) We prove that$k$-party set disjointness has randomized and nondeterministic communication complexity$\Omega(n/4^k)^{1/4}$and Merlin-Arthur complexity$\Omega(n/4^k)^{1/8}.$These bounds are close to tight. Previous lower bounds (2007-2008) for$k\geq3$parties were weaker than$n^{1/(k+1)}/2^{k^2}$in all ... more >>> TR11-158 | 25th November 2011 Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin #### Locality from Circuit Lower Bounds We study the locality of an extension of first-order logic that captures graph queries computable in AC$^0$, i.e., by families of polynomial-size constant-depth circuits. The extension considers first-order formulas over relational structures which may use arbitrary numerical predicates in such a way that their truth value is independent of the ... more >>> TR12-059 | 14th May 2012 Rahul Santhanam, Ryan Williams #### Uniform Circuits, Lower Bounds, and QBF Algorithms We explore the relationships between circuit complexity, the complexity of generating circuits, and circuit-analysis algorithms. Our results can be roughly divided into three parts: 1. Lower Bounds Against Medium-Uniform Circuits. Informally, a circuit class is medium uniform'' if it can be generated by an algorithmic process that is somewhat complex ... more >>> TR13-021 | 5th February 2013 Kristoffer Arnsfelt Hansen, Vladimir Podolskii #### Polynomial threshold functions and Boolean threshold circuits We study the complexity of computing Boolean functions on general Boolean domains by polynomial threshold functions (PTFs). A typical example of a general Boolean domain is$\{1,2\}^n$. We are mainly interested in the length (the number of monomials) of PTFs, with their degree and weight being of secondary interest. We ... more >>> TR13-102 | 17th July 2013 Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah #### Small Depth Proof Systems A proof system for a language$L$is a function$f$such that Range$(f)$is exactly$L$. In this paper, we look at proofsystems from a circuit complexity point of view and study proof systems that are computationally very restricted. The restriction we study is: they can be computed by ... more >>> TR14-120 | 16th September 2014 Olaf Beyersdorff, Leroy Chew, Mikolas Janota #### Proof Complexity of Resolution-based QBF Calculi Proof systems for quantified Boolean formulas (QBFs) provide a theoretical underpinning for the performance of important QBF solvers. However, the proof complexity of these proof systems is currently not well understood and in particular lower bound techniques are missing. In this paper we exhibit a new and elegant proof technique ... more >>> TR15-018 | 31st January 2015 Eric Allender, Ian Mertz #### Complexity of Regular Functions Revisions: 1 We give complexity bounds for various classes of functions computed by cost register automata. more >>> TR15-030 | 6th March 2015 Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie ####${\mathrm{AC}^{0} \circ \mathrm{MOD}_2}$lower bounds for the Boolean Inner Product Revisions: 1$\mathrm{AC}^{0} \circ \mathrm{MOD}_2$circuits are$\mathrm{AC}^{0}$circuits augmented with a layer of parity gates just above the input layer. We study the$\mathrm{AC}^{0} \circ \mathrm{MOD}_2$circuit lower bound for computing the Boolean Inner Product functions. Recent works by Servedio and Viola (ECCC TR12-144) and Akavia et al. (ITCS 2014) have ... more >>> TR15-188 | 24th November 2015 Daniel Kane, Ryan Williams #### Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits In order to formally understand the power of neural computing, we first need to crack the frontier of threshold circuits with two and three layers, a regime that has been surprisingly intractable to analyze. We prove the first super-linear gate lower bounds and the first super-quadratic wire lower bounds for ... more >>> TR16-022 | 22nd February 2016 Alexander Golovnev, Alexander Kulikov, Alexander Smal, Suguru Tamaki #### Circuit size lower bounds and #SAT upper bounds through a general framework Revisions: 1 Most of the known lower bounds for binary Boolean circuits with unrestricted depth are proved by the gate elimination method. The most efficient known algorithms for the #SAT problem on binary Boolean circuits use similar case analyses to the ones in gate elimination. Chen and Kabanets recently showed that the ... more >>> TR16-071 | 1st May 2016 Jan Krajicek, Igor Carboni Oliveira #### Unprovability of circuit upper bounds in Cook's theory PV We establish unconditionally that for every integer$k \geq 1$there is a language$L \in P$such that it is consistent with Cook's theory PV that$L \notin SIZE(n^k)$. Our argument is non-constructive and does not provide an explicit description of this language. more >>> TR16-095 | 7th June 2016 Arkadev Chattopadhyay, Nikhil Mande #### Small Error Versus Unbounded Error Protocols in the NOF Model Revisions: 1 , Comments: 1 We show that a simple function has small unbounded error communication complexity in the$k$-party number-on-forehead (NOF) model but every probabilistic protocol that solves it with sub-exponential advantage over random guessing has cost essentially$\Omega\left(\frac{\sqrt{n}}{4^k}\right)$bits. Such a separation was first shown for$k=2$independently by Buhrman et al. ['07] ... more >>> TR16-110 | 19th July 2016 Alexander Golovnev, Oded Regev, Omri Weinstein #### The Minrank of Random Graphs Revisions: 1 The minrank of a graph$G$is the minimum rank of a matrix$M$that can be obtained from the adjacency matrix of$G$by switching ones to zeros (i.e., deleting edges) and setting all diagonal entries to one. This quantity is closely related to the fundamental information-theoretic problems of ... more >>> TR16-158 | 9th October 2016 Alexander Kulikov, Vladimir Podolskii #### Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates We study the following computational problem: for which values of$k$, the majority of$n$bits$\text{MAJ}_n$can be computed with a depth two formula whose each gate computes a majority function of at most$k$bits? The corresponding computational model is denoted by$\text{MAJ}_k \circ \text{MAJ}_k$. We observe that ... more >>> TR17-019 | 8th February 2017 Andreas Krebs, Nutan Limaye, Michael Ludwig #### A Unified Method for Placing Problems in Polylogarithmic Depth Revisions: 2 In this work we consider the term evaluation problem which involves, given a term over some algebra and a valid input to the term, computing the value of the term on that input. This is a classical problem studied under many names such as formula evaluation problem, formula value problem ... more >>> TR17-022 | 13th February 2017 Benjamin Rossman, Srikanth Srinivasan #### Separation of AC$^0[\oplus]$Formulas and Circuits This paper gives the first separation between the power of {\em formulas} and {\em circuits} of equal depth in the$\mathrm{AC}^0[\oplus]$basis (unbounded fan-in AND, OR, NOT and MOD$_2$gates). We show, for all$d(n) \le O(\frac{\log n}{\log\log n})$, that there exist {\em polynomial-size depth-$d$circuits} that are not equivalent ... more >>> TR17-092 | 10th May 2017 Shuichi Hirahara #### A Duality Between Depth-Three Formulas and Approximation by Depth-Two We establish an explicit link between depth-3 formulas and one-sided approximation by depth-2 formulas, which were previously studied independently. Specifically, we show that the minimum size of depth-3 formulas is (up to a factor of n) equal to the inverse of the maximum, over all depth-2 formulas, of one-sided-error correlation ... more >>> TR17-109 | 22nd June 2017 Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani #### Does Looking Inside a Circuit Help? The Black-Box Hypothesis, introduced by Barak et al. (JACM, 2012), states that any property of boolean functions decided efficiently (e.g., in BPP) with inputs represented by circuits can also be decided efficiently in the black-box setting, where an algorithm is given an oracle access to the input function and an ... more >>> TR17-149 | 7th October 2017 Or Meir, Avi Wigderson #### Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds Revisions: 1 Consider a random sequence of$n$bits that has entropy at least$n-k$, where$k\ll n\$. A commonly used observation is that an average coordinate of this random sequence is close to being uniformly distributed, that is, the coordinate “looks random”. In this work, we prove a stronger result that ... more >>>

ISSN 1433-8092 | Imprint