Lupanov representation

Lupanov's (k, s)-representation, named after Oleg Lupanov, is a means of representing Boolean circuits to demonstrate an asymptotically tight upper bound on the circuit size (i.e., the number of gates) needed to represent a Boolean function. Claude Shannon showed that almost all Boolean functions of n variables need a circuit of size at least 2ⁿn⁻¹. Lupanov's (k, s)-representation shows that all Boolean functions of n variables can be computed with a circuit of 2ⁿn⁻¹ + o(2ⁿn⁻¹) gates.

Definition

The idea is to represent the values of a Boolean function f in a table of 2^k rows, representing the possible values of the k first variables x₁, ..., x_k, and 2^n−k columns representing the values of the other variables.

Let A₁, ..., A_p be a partition of the rows of this table such that for i < p, |A_i| = s and $|A_p|=s^{\prime }\le s$. Let f_i(x) = f(x) iff x ∈ A_i.

Moreover, let $B_{i,w}$ be the set of the columns whose intersection with $A_i$ is $w$.

External links

• Course material describing the Lupanov representation
• An additional example from the same course material

This article "Lupanov representation" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Lupanov representation. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• CKod
• Johnston diagram
• Zhegalkin algebra

---