Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > UNIFORM CIRCUIT LOWER BOUNDS:
Reports tagged with uniform circuit lower bounds:
TR12-007 | 28th January 2012
Ruiwen Chen, Valentine Kabanets

Lower Bounds against Weakly Uniform Circuits

Revisions: 1

A family of Boolean circuits $\{C_n\}_{n\geq 0}$ is called \emph{$\gamma(n)$-weakly uniform} if
there is a polynomial-time algorithm for deciding the direct-connection language of every $C_n$,
given \emph{advice} of size $\gamma(n)$. This is a relaxation of the usual notion of uniformity, which allows one
to interpolate between complete uniformity (when $\gamma(n)=0$) ... more >>>




ISSN 1433-8092 | Imprint