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

∧

{\displaystyle \land }

,

∨

{\displaystyle \lor }

, and

¬

{\displaystyle \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

{\displaystyle f}

, a restriction

ρ

{\displaystyle \rho }

of

f

{\displaystyle f}

is a partial assignment to

n

−

k

{\displaystyle n-k}

of the

n

{\displaystyle n}

variables, giving a function

f

ρ

{\displaystyle f_{\rho }}

of fewer variables. Take the following function:

f

(

x

1

,

x

2

,

x

3

)

=

(

x

1

∨

x

2

∨

x

3

)

∧

(

¬

x

1

∨

x

2

)

∧

(

x

1

∨

¬

x

3

)

{\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

f

ρ

(

y

1

,

y

2

)

=

f

(

1

,

y

1

,

y

2

)

=

(

1

∨

y

1

∨

y

2

)

∧

(

¬

1

∨

y

1

)

∧

(

1

∨

¬

y

2

)

{\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

f

ρ

(

y

1

,

y

2

)

=

y

1

{\displaystyle f_{\rho }(y_{1},y_{2})=y_{1}}

.