Marcos Kiwi, Frederic Magniez, Miklos Santha

In the late 80's Blum, Luby, Rubinfeld, Kannan et al. pioneered

the theory of self-testing as an alternative way of dealing with

the problem of software reliability.

Over the last decade this theory played a crucial role in

the construction of probabilistically checkable proofs and

the ...
more >>>

Oded Goldreich

This text provides a basic presentation of the the approximation method of Razborov (Matematicheskie Zametki, 1987) and its application by Smolensky (19th STOC, 1987) for proving lower bounds on the size of ${\cal AC}^0[p]$-circuits that compute sums mod~$q$ (for primes $q\neq p$).

The textbook presentations of the latter result ...
more >>>