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

Arkadev Chattopadhyay, Avi Wigderson

We study solution sets to systems of generalized linear equations of the following form:

$\ell_i (x_1, x_2, \cdots , x_n)\, \in \,A_i \,\, (\text{mod } m)$,

where $\ell_1, \ldots ,\ell_t$ are linear forms in $n$ Boolean variables, each $A_i$ is an arbitrary subset of $\mathbb{Z}_m$, and $m$ is a composite ...
more >>>