And to recap the ten we chose this year from 2005-2014
- Undirected Connectivity in Log Space
- Optimal Inapproximability for Max-Cut
- Limitations of linear programming
- Complexity of Nash Equilibrium
- Combinatorial Proof of PCP Theorem
- Constructive Proof of the Lovász Local Lemma
- Polylogarithmic independence fools AC0
- QIP = PSPACE
- Lower Bounds on Multilinear Formulas
- NEXP not in ACC0
Ten more in ten years.
The Max-Cut link also points to the log space post.
ReplyDeleteFixed. Thanks.
DeleteThanks Lance for writing these posts. They are really invaluable for beginners.
ReplyDelete