Ran Raz, Amir Shpilka

We prove super-linear lower bounds for the number of edges

in constant depth circuits with $n$ inputs and up to $n$ outputs.

Our lower bounds are proved for all types of constant depth

circuits, e.g., constant depth arithmetic circuits, constant depth

threshold circuits ...
more >>>

Eli Ben-Sasson, Prahladh Harsha

We present a simple proof of the bounded-depth Frege lower bounds of

Pitassi et. al. and Krajicek et. al. for the pigeonhole

principle. Our method uses the interpretation of proofs as two player

games given by Pudlak and Buss. Our lower bound is conceptually

simpler than previous ones, and relies ...
more >>>

Pavel Pudlak

We shall prove a lower bound on the number of edges in some bounded

depth graphs. This theorem is stronger than lower bounds proved on

bounded depth superconcentrators and enables us to prove a lower bound

on certain bounded depth circuits for which we cannot use

superconcentrators: we prove that ...
more >>>

Stasys Jukna

In this note we consider unbounded fanin depth-2 circuits with arbitrary boolean functions as gates.

We define the entropy of an operator f:{0,1}^n --> {0,1}^m is as the logarithm of the maximum number of vectors distinguishable by at least one special subfunction of f. Then we prove that every ... more >>>

Zohar Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich

We give the first sub-exponential time deterministic polynomial

identity testing algorithm for depth-$4$ multilinear circuits with

a small top fan-in. More accurately, our algorithm works for

depth-$4$ circuits with a plus gate at the top (also known as

$\Spsp$ circuits) and has a running time of

$\exp(\poly(\log(n),\log(s),k))$ where $n$ is ...
more >>>

Shachar Lovett, Emanuele Viola

We study a variant of the classical circuit-lower-bound problems: proving lower bounds for sampling distributions given random bits. We prove a lower bound of $1-1/n^{\Omega(1)}$ on the statistical distance between (i) the output distribution of any small constant-depth (a.k.a.~$\mathrm{AC}^0$) circuit $f : \{0,1\}^{\mathrm{poly}(n)} \to \{0,1\}^n$, and (ii) the uniform distribution ... more >>>

Gil Cohen, Anat Ganor, Ran Raz

In the Coin Problem, one is given n independent flips of a coin that has bias $\beta > 0$ towards either Head or Tail. The goal is to decide which side the coin is biased towards, with high confidence. An optimal strategy for solving the coin problem is to apply ... more >>>

Avishay Tal

We show that $AC^0$ circuits of depth $d$ and size $m$ have at most $2^{-\Omega(k/(\log m)^{d-1})}$ of their Fourier mass at level $k$ or above. Our proof builds on a previous result by H{\aa}stad (SICOMP, 2014) who proved this bound for the special case $k=n$. Our result is tight up ... more >>>