Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > WEAKLY UNIFORM CIRCUITS:
Reports tagged with weakly uniform circuits:
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