# Bella Subbotovskaya

Bella Abramovna Subbotovskaya (17 December 1937 – 23 September 1982) was a Soviet mathematician who founded the short-lived Jewish People's University (1978–1983) in Moscow. The school's purpose was to offer free education to those affected by structured anti-Semitism within the Soviet educational system. Its existence was outside Soviet authority and it was investigated by the KGB. Subbotovskaya herself was interrogated a number of times by the KGB and shortly thereafter was hit by a truck and died, in what has been speculated was an assassination.

## Academic work

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

### Random restrictions

Subbotovskaya invented the method of random restrictions to Boolean functions. Starting with a function $f$, a restriction $\rho$ of $f$ is a partial assignment to $n-k$ of the $n$ variables, giving a function $f_{\rho }$ of fewer variables. Take the following function:
    $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
    $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 $f_{\rho }(y_{1},y_{2})=y_{1}$.
To sample a random restriction, retain $k$ variables uniformly at random. For each remaining variable, assign it 0 or 1 with equal probability.

### Formula Size and Restrictions

As demonstrated in the above example, applying a restriction to a function can massively reduce the size of its formula. Though $f$ is written with 7 variables, by only restricting one variable, we found that $f_{\rho }$ uses only 1.
Subbotovskaya proved something much stronger: if $\rho$ is a random restriction of $n-k$ variables, then the expected shrinkage between $f$ and $f_{\rho }$ is large, specifically
    $\mathbb {E} \left[L(f_{\rho })\right]\leq \left({\frac {k}{n}}\right)^{3/2}L(f)$,
where $L$ is the minimum number of variables in the formula. Applying Markov's inequality we see
    $\Pr \left[L(f_{\rho })\leq 4\left({\frac {k}{n}}\right)^{3/2}L(f)\right]\geq {\frac {3}{4}}$.

### Example application

Take $f$ to be the parity function over $n$ variables. After applying a random restriction of $n-1$ variables, we know that $f_{\rho }$ is either $x_{i}$ or $\lnot x_{i}$ depending the parity of the assignments to the remaining variables. Thus clearly the size of the circuit that computes $f_{\rho }$ is exactly 1. Then applying the probabilistic method, for sufficiently large $n$, we know there is some $\rho$ for which
    $L(f_{\rho })\leq 4\left({\frac {1}{n}}\right)^{3/2}L(f)$.
Plugging in $L(f_{\rho })=1$, we see that $L(f)\geq n^{3/2}/4$. Thus we have proven that the smallest circuit to compute the parity of $n$ variables using only $\land ,\lor ,\lnot$ must use at least this many variables.

### Influence

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 $3/2$ in the main lemma has been increased through careful analysis to $1.63$ by Paterson and Zwick (1993) and then to $2$ by Håstad (1998). Additionally, Håstad's Switching lemma (1987) applied the same technique to the much richer model of constant depth Boolean circuits.