Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with approximation error:
TR01-014 | 7th February 2001
Marcos Kiwi, Frederic Magniez, Miklos Santha

Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey

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

TR23-034 | 24th March 2023
Oded Goldreich

On teaching the approximation method for circuit lower bounds

Revisions: 1

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

ISSN 1433-8092 | Imprint