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

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