Bella Subbotovskaya

Bella Abramovna Subbotovskaya
Белла Абрамовна Субботовская
Subbotovskaya in 1961
Born	(1937-12-17)December 17, 1937 Moscow, Russia
Died	November 23, 1982(1982-11-23) (aged 44)
Cause of death	Car crash (suspected assassination)
Resting place	Vostryakovo Jewish Cemetery, Moscow
Nationality	Russian
Alma mater	Faculty of Mechanics and Mathematics, Moscow State University
Known for	Boolean formula complexity Jewish People's University
Spouse	Ilya Muchnik ​ (m. 1961⁠–⁠1971)​
Scientific career
Fields	Mathematical logic Mathematics education
Thesis	"A criterion for the comparability of bases for the realisation of Boolean functions by formulas" (1963)
Academic advisors	Oleg Lupanov

Bella Abramovna Subbotovskaya (17 December 1937 – 23 September 1982)^[1] was a Soviet mathematician who founded the short-lived Jewish People's University (1978–1983) in Moscow.^[2][3] 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.^[4]

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.

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.