|Bella Abramovna Subbotovskaya|
|Native name||Белла Абрамовна Субботовская|
December 17, 1937|
|Died||November 23, 1982(aged 43–44)|
|Cause of death||Car crash (suspected assassination)|
|Resting place||Vostryakovo Jewish Cemetery, Moscow|
|Alma mater||Moscow State University (Mekh-Mat)|
|Known for||Boolean formula complexity
Jewish People's University
|Spouse(s)||Ilya Muchnik (1961-1971)|
|Thesis||"A criterion for the comparability of bases for the realisation of Boolean functions by formulas" (1963)|
|Academic advisors||Oleg Borisovitch Lupanov|
Bella Abramovna Subbotovskaya (b. 1938 - d. 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 a assassination.
Prior to founding the Jewish People's University, Subbotovskaya published papers in mathematical logic. Her results on Boolean formulas written in terms of , , and were influential in the then nascent field of computational complexity theory.
She invented the method of random restrictions to Boolean functions. Starting with a function , a restriction of is a partial assignment to of the variables, giving a function of fewer variables. Take the following function:
The following is a restriction of one variable
Under the usual identities of Boolean algebra this simplifies to .
To sample a random restriction, retain 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 is written with 7 variables, by only restricting one variable, we found that uses only 1.
Subbotovskaya proved something much stronger: if is a random restriction of variables, then the expected shrinkage between and is large, specifically 
where is the minimum number of variables in the formula. Applying Markov's inequality we see
Take to be the parity function over variables. After applying a random restriction of variables, we know that is either or depending the parity of the assignments to the remaining variables. Thus clearly the size of the circuit that computes is exactly 1. Then applying the probabilistic method, for sufficiently large , we know there is some for which
Plugging in , we see that . Thus we have proven that the smallest circuit to compute the parity of variables using only must use at least this many variables.
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 in the main lemma has been increased through careful analysis to by Paterson and Zwick (1993) and then to 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.
- O'Connor, J; Robertson, E. "Bella Abramovna Subbotovskaya". MacTutor History of Mathematics archive. School of Mathematics and Statistics, University of St Andrews, Scotland. Retrieved 22 January 2017.
- Szpiro, G. (2007), "Bella Abramovna Subbotovskaya and the Jewish People's University", Notices of the American Mathematical Society, 54(10), 1326–1330.
- Zelevinsky, A. (2005), "Remembering Bella Abramovna", You Failed Your Math Test Comrade Einstein (M. Shifman, ed.), World Scientific, 191–195.
- "Remembering Math Heroine Bella Abramovna Subbotovskaya". Math in the News. Mathematical Association of America. 12 November 2007. Retrieved 28 June 2014.
- Jukna, Stasys (Jan 6, 2012). Boolean Function Complexity: Advances and Frontiers. Springer Science & Business Media. p. 167-173. ISBN 3642245080.
- Kulikov, Alexander. "Circuit Complexity Minicourse: The Shrinkage Exponent of Formulas over U2" (PDF). Retrieved 22 January 2017.