Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with MOD gates:
TR05-122 | 31st October 2005
Pavel Pudlak

A nonlinear bound on the number of wires in bounded depth circuits

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

TR09-084 | 24th September 2009
Arkadev Chattopadhyay, Avi Wigderson

Linear systems over composite moduli

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

ISSN 1433-8092 | Imprint