Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR11-130 | 25th September 2011 23:01

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

TR11-130
Authors: Sergei Lozhkin, Alexander Shiganov
Publication: 25th September 2011 23:13
Keywords:

Abstract:

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 Boolean functions of $n$ variables in the circuits for
these functions, which are built using our method, the fraction of gates
with fan-out 2 is asymptotically at least 1/32. This fact disproves upper bound [Yamamoto2011]
on the number of circuits with exact number of gates with fan-out at least 2.

ISSN 1433-8092 | Imprint