Bella Subbotovskaya

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 ∧ , ∨ , and ¬ were influential in the then nascent field of computational complexity theory.

Random Restrictions

She invented the method of random restrictions to Boolean functions. Starting with a function f , a restriction ρ of f is a partial assignment to n − k of the n variables, giving a function f ρ 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 f ρ ( 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 ρ uses only 1.

Subbotovskaya proved something much stronger: if ρ is a random restriction of n − k variables, then the expected shrinkage between f and f ρ is large, specifically

where L is the minimum number of variables in the formula. Applying Markov's inequality we see

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 ρ is either x i or ¬ x i depending the parity of the assignments to the remaining variables. Thus clearly the size of the circuit that computes f ρ is exactly 1. Then applying the probabilistic method, for sufficiently large n , we know there is some ρ for which

Plugging in L ( f ρ ) = 1 , we see that L ( f ) ≥ n 3 / 2 / 4 . Thus we have proven that the smallest circuit to compute the parity of n variables using only ∧ , ∨ , ¬ 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.