Bella Subbotovskaya

Subbotovskaya invented the method of random restrictions to Boolean functions.[5] Starting with a function ${\displaystyle f}$, a restriction ${\displaystyle \rho }$ of ${\displaystyle f}$ is a partial assignment to ${\displaystyle n-k}$ of the ${\displaystyle n}$ variables, giving a function ${\displaystyle f_{\rho }}$ of fewer variables. Take the following function:

${\displaystyle f(x_{1},x_{2},x_{3})=(x_{1}\lor x_{2}\lor x_{3})\land (\lnot x_{1}\lor x_{2})\land (x_{1}\lor \lnot x_{3})}$.

The following is a restriction of one variable

${\displaystyle f_{\rho }(y_{1},y_{2})=f(1,y_{1},y_{2})=(1\lor y_{1}\lor y_{2})\land (\lnot 1\lor y_{1})\land (1\lor \lnot y_{2})}$.

Under the usual identities of Boolean algebra this simplifies to ${\displaystyle f_{\rho }(y_{1},y_{2})=y_{1}}$.

To sample a random restriction, retain ${\displaystyle k}$ variables uniformly at random. For each remaining variable, assign it 0 or 1 with equal probability.

As demonstrated in the above example, applying a restriction to a function can massively reduce the size of its formula. Though ${\displaystyle f}$ is written with 7 variables, by only restricting one variable, we found that ${\displaystyle f_{\rho }}$ uses only 1.

Subbotovskaya proved something much stronger: if ${\displaystyle \rho }$ is a random restriction of ${\displaystyle n-k}$ variables, then the expected shrinkage between ${\displaystyle f}$ and ${\displaystyle f_{\rho }}$ is large, specifically

${\displaystyle \mathbb {E} \left[L(f_{\rho })\right]\leq \left({\frac {k}{n}}\right)^{3/2}L(f)}$,

where ${\displaystyle L}$ is the minimum number of variables in the formula.[5] Applying Markov's inequality we see

${\displaystyle \Pr \left[L(f_{\rho })\leq 4\left({\frac {k}{n}}\right)^{3/2}L(f)\right]\geq {\frac {3}{4}}}$.

Take ${\displaystyle f}$ to be the parity function over ${\displaystyle n}$ variables. After applying a random restriction of ${\displaystyle n-1}$ variables, we know that ${\displaystyle f_{\rho }}$ is either ${\displaystyle x_{i}}$ or ${\displaystyle \lnot x_{i}}$ depending the parity of the assignments to the remaining variables. Thus clearly the size of the circuit that computes ${\displaystyle f_{\rho }}$ is exactly 1. Then applying the probabilistic method, for sufficiently large ${\displaystyle n}$, we know there is some ${\displaystyle \rho }$ for which

${\displaystyle L(f_{\rho })\leq 4\left({\frac {1}{n}}\right)^{3/2}L(f)}$.

Plugging in ${\displaystyle L(f_{\rho })=1}$, we see that ${\displaystyle L(f)\geq n^{3/2}/4}$. Thus we have proven that the smallest circuit to compute the parity of ${\displaystyle n}$ variables using only ${\displaystyle \land ,\lor ,\lnot }$ must use at least this many variables.[6]

Although this is not an exceptionally strong lower bound, random restrictions have become an essential tool in complexity. In a similar vein to this proof, the exponent ${\displaystyle 3/2}$ in the main lemma has been increased through careful analysis to ${\displaystyle 1.63}$ by Paterson and Zwick (1993) and then to ${\displaystyle 2}$ by Håstad (1998).[5] Additionally, Håstad's Switching lemma (1987) applied the same technique to the much richer model of constant depth Boolean circuits.