Lupanov Representation

Lupanov's (''k'', ''s'')-representation, named after Oleg Lupanov, is a way of representing Boolean circuits so as to show that the reciprocal of the Shannon effect. Shannon had showed that almost all Boolean functions of ''n'' variables need a circuit of size at least 2^''n''''n''⁻¹. The reciprocal is that:

All Boolean functions of ''n'' variables can be computed with a circuit of at most 2^''n''''n''⁻¹ + o(2^''n''''n''⁻¹) gates.

Definition

The idea is to represent the values of a boolean function ''ƒ'' 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'\leq s$.
Let ''ƒ''_''i''(''x'') = ''ƒ''(''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

Boolean algebra
Circuit complexity