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 from {-1,0,1\}. This provides the first ... more >>>

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$ are ... more >>>

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 same function ... more >>>

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 complete for C under NC$^0$ reductions are ... more >>>

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 >>>

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 circuits, and problems in the counting hierarchy that ... more >>>

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, (as well as other problems), are ... more >>>

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. This isolates the analytic content of ... more >>>

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 >>>

-- 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 basis ... more >>>

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 allows ... more >>>

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 >>>

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 Boolean functions in ... more >>>

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 $k$ independently ... more >>>

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 >>>

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 >>>

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

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 boundary ... more >>>

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 >>>

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 n)$. ... more >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 of ``unique solutions'', the ... more >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 in one important respect from computations ... more >>>

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 >>>

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 >>>

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 introduced ... more >>>

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 >>>

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 >>>