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 > ASYMPTOTIC BOUNDS:
Reports tagged with asymptotic bounds:
TR11-130 | 25th September 2011
Sergei Lozhkin, Alexander Shiganov

On a Modification of Lupanov's Method with More Uniform Distribution of Fan-out

In this paper we suggest a modification of classical Lupanov's method [Lupanov1958]
that allows building circuits over the basis \{\&,\vee,\neg\} for Boolean functions of n variables with size at most

\frac{2^n}{n}\left(1+\frac{3\log n + O(1)}{n}\right),

and with more uniform distribution of outgoing arcs by circuit gates.

For almost all ... more >>>




ISSN 1433-8092 | Imprint