Bravely, Moderately: A Common Theme in Four Recent Results
Webpage for an essay by Oded Goldreich
Abstract
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
- the polynomial-time approximation of the permanent of non-negative matrices
(by Jerrum, Sinclair, and Vigoda, 33rd STOC, 2001);
- the iterative (Zig-Zag) construction of expander graphs
(by Reingold, Vadhan, and Wigderson, 41st FOCS, 2000);
- the log-space algorithm for undirected connectivity
(by Reingold, 37th STOC, 2005);
- and, the alternative proof of the PCP Theorem
(by Dinur, ECCC, TR05-046, 2005).
Material available on-line
Back to
either Oded Goldreich's homepage.
or general list of papers.