Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-098 | 4th September 2005 00:00

Bravely, Moderately: A Common Theme in Four Recent Results


Authors: Oded Goldreich
Publication: 4th September 2005 15:52
Downloads: 1369


We highlight a common theme in four relatively recent works
that establish remarkable results by an iterative approach.
Starting from a trivial construct,
each of these works applies an ingeniously designed
sequence of iterations that yields the desired result,
which is highly non-trivial. Furthermore, in each iteration,
the construct is modified in a relatively moderate manner.
The four works we refer to are
1) the polynomial-time approximation of the permanent of non-negative matrices
(by Jerrum, Sinclair, and Vigoda, 33rd STOC, 2001);
2) the iterative (Zig-Zag) construction of expander graphs
(by Reingold, Vadhan, and Wigderson, 41st FOCS, 2000);
3) the log-space algorithm for undirected connectivity
(by Reingold, 37th STOC, 2005);
4) and, the alternative proof of the PCP Theorem
(by Dinur, ECCC, TR05-046, 2005).

ISSN 1433-8092 | Imprint