ECCC-Report TR05-098https://eccc.weizmann.ac.il/report/2005/098Comments and Revisions published for TR05-098en-usSun, 04 Sep 2005 15:52:42 +0300
Paper TR05-098
| Bravely, Moderately: A Common Theme in Four Recent Results |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2005/098
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).
Sun, 04 Sep 2005 15:52:42 +0300https://eccc.weizmann.ac.il/report/2005/098