We bound the minimum number w of wires needed to compute any (asymptotically good) error-correcting code
C:\{0,1\}^{\Omega(n)} \to \{0,1\}^n with minimum distance \Omega(n),
using unbounded fan-in circuits of depth d with arbitrary gates. Our main results are:

(1) If d=2 then w = \Theta(n ({\log n/ \log \log n})^2).

(2) ... more >>>

Spira showed that any Boolean formula of size s can be simulated in depth O(\log s). We generalize Spira's theorem and show that any Boolean circuit of size s with segregators of size f(s) can be simulated in depth O(f(s)\log s). If the segregator size is at least s^{\varepsilon} for ... more >>>

We propose the following computational assumption: in general if we try to compress the depth of a circuit family (parallel time) more than a constant factor we will suffer super-quasi-polynomial blowup in the size (number of processors). This assumption is only slightly stronger than the popular assumption about the robustness ... more >>>

Aiming to provide weak as possible axiomatic assumptions in which one can develop basic linear algebra, we give a uniform and integral version of the short propositional proofs for the determinant identities demonstrated over GF(2) in Hrubes-Tzameret [SICOMP'15]. Specifically, we show that the multiplicativity of the determinant function and the ... more >>>

The best known circuit lower bounds against unrestricted circuits remained around 3n for several decades. Moreover, the only known technique for proving lower bounds in this model, gate elimination, is inherently limited to proving lower bounds of less than 5n. In this work, we suggest a first non-gate-elimination approach for ... more >>>

One of the major open problems in complexity theory is proving super-logarithmic
lower bounds on the depth of circuits (i.e., \mathbf{P}\not\subseteq\mathbf{NC}^1). Karchmer, Raz, and Wigderson (Computational Complexity 5, 3/4) suggested to approach this problem by proving that depth complexity behaves "as expected" with respect to the composition of functions $f ... more >>>