Needless to say, the following works are unrelated.
### (1) Faster Generation of Random Spanning Trees

by Jonathan A. Kelner and Aleksander Madry.
### (2) Constructing Small-Bias Sets from Algebraic-Geometric Codes

by Avraham Ben-Aroya and Amnon Ta-Shma.
### (3) A Probabilistic Inequality with Applications to Threshold
Direct-Product Theorems

by Falk Unger.
### (4) A Complete Characterization of Statistical Query Learning with
Applications to Evolvability

by Vitaly Feldman.
Note: a handful of other works are covered by previous choices.

#### Oded's comments

Re (1): I'm happy to see yet another application of the paradigm
of decomposing any graph into parts that are rapidly mixing,
while omitting relatively few edges. Let me seize this opportunity
and mention the application of this paradigm in
the bipartite tester for bounded-degree graphs.

Re (2): When small-bias spaces were first defined and constructed,
I felt that the exact polynomial dependence on the length
and bias parameters (i.e., $n$ and $\eps$, respectively)
is quite immaterial. Nowadays, being even more convinced
of the fundamental nature of this notion, obtaining an efficient
construction of optimal size seems a worthy goal to me, and this
paper seems to make a significant step in this direction.

Re (3): This work generalizes Chernoff Bound to the case that the 0-1
random variables may not be independent but have a small bias in the
sense that the bias of any linear combination decreases exponentially
with its size. On the other hand, these biases correspond to
co-moments of the random variables, which may hint to why this
condition may lead to strong tail inequalities. Turning back
to the dual view of biases, which are reflected in guessing XORs of values,
this leads to proofs of Threshold Direct-Product Theorems (DPTs)
in various setting. Thus, while I still maintain that it is odd
to derive a standard DPT via the XOR Lemma
(cf. Remark following Lemma 7
in the old survey of Yao's XOR Lemma),
this work demonstrates that the XOR Lemma is a natural tool
towards deriving Theorems DPTs.

Re (4): Being fascinated with Valiant's model of Evolvability,
this paper is an obvious choice for me. It seems that this paper
indicates (more than prior works) that evlovability as modeled
by Valiant is quite realistic. I refer to the monotone feature,
and do note that it is established (for all SQ learnable classes)
only via a distribtrubtion-dependent algorithm. Still!

#### The original abstracts

See FOCS'09 proceedings.

Back to
list of Oded's choices.