All reports by Author Alexander Shiganov:

__
TR11-130
| 25th September 2011
__

Sergei Lozhkin, Alexander Shiganov#### On a Modification of Lupanov's Method with More Uniform Distribution of Fan-out

Sergei Lozhkin, Alexander Shiganov

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