__
TR05-098 | 4th September 2005 00:00
__

#### Bravely, Moderately: A Common Theme in Four Recent Results

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

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