Prior to founding the Jewish People's University, Subbotovskaya published papers in mathematical logic. Her results on Boolean formulas written in terms of ${\displaystyle \land }$ , ${\displaystyle \lor }$ , and ${\displaystyle \lnot }$  were influential in the then nascent field of computational complexity theory.

Random restrictions edit

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.

Formula Size and Restrictions edit

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}}}$ .

Example application edit

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]

Influence edit

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.