• 
  Michael Mitzenmacher (Ed.): Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009. ACM 2009 ISBN 978-1-60558-506-2
• 
  Avi Wigderson: The work of Leslie Valiant. 1-2

Codes

• 
  Sanjeev Arora, Constantinos Daskalakis, David Steurer: Message passing algorithms and improved LP decoding. 3-12
• 
  Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra: List decoding tensor products and interleaved codes. 13-22
• 
  Venkatesan Guruswami: Artin automorphisms, cyclotomic function fields, and folded list-decodable codes. 23-32
• 
  Qi Cheng, Daqing Wan: A deterministic reduction for the gap minimum distance problem: [extended abstract]. 33-38
• 
  Klim Efremenko: 3-query locally decodable codes of subexponential length. 39-44

Complexity I

• 
  Linda Sellie: Exact learning of random DNF over the uniform distribution. 45-54
• 
  László Babai, Robert Beals, Ákos Seress: Polynomial-time theory of matrix groups. 55-64
• 
  Eli Ben-Sasson, Swastik Kopparty: Affine dispersers from subspace polynomials. 65-74
• 
  Constantinos Daskalakis, Christos H. Papadimitriou: On oblivious PTAS's for nash equilibrium. 75-84
• 
  Eli Gafni: The extended BG-simulation and the characterization of t-resiliency. 85-92

Algorithms and data structures

• 
  Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Raphael M. Jungers, J. Ian Munro: An efficient algorithm for partial order production. 93-100
• 
  Aaron Bernstein, David R. Karger: A nearly optimal oracle for avoiding failed vertices and edges. 101-110
• 
  Leonid Barenboim, Michael Elkin: Distributed (delta+1)-coloring in linear (in delta) time. 111-120
• 
  Tobias Friedrich, Thomas Sauerwald: Near-perfect load balancing by randomized rounding. 121-130

Property testing

• 
  Russell Impagliazzo, Valentine Kabanets, Avi Wigderson: New direct-product testers and 2-query PCPs. 131-140
• 
  Oded Goldreich, Dana Ron: On proximity oblivious testing. 141-150
• 
  Eric Blais: Testing juntas nearly optimally. 151-158
• 
  Asaf Shapira: Green's conjecture and testing linear-invariant properties. 159-166
• 
  Shafi Goldwasser: Athena lecture: Controlling Access to Programs? 167-168

Crypto I

• 
  Craig Gentry: Fully homomorphic encryption using ideal lattices. 169-178
• 
  Huijia Lin, Rafael Pass, Muthuramakrishnan Venkitasubramaniam: A unified framework for concurrent security: universal composability from stand-alone non-malleability. 179-188
• 
  Huijia Lin, Rafael Pass: Non-malleability amplification. 189-198

Approx algorithms I

• 
  Alexandr Andoni, Krzysztof Onak: Approximating edit distance in near-linear time. 199-204
• 
  Kenneth L. Clarkson, David P. Woodruff: Numerical linear algebra in the streaming model. 205-214
• 
  Nam H. Nguyen, Thong T. Do, Trac D. Tran: A fast and efficient algorithm for low-rank approximation of a matrix. 215-224
• 
  Yuichi Yoshida, Masaki Yamamoto, Hiro Ito: An improved constant-time approximation algorithm for maximum~matchings. 225-234

Graphs cuts and flows

• 
  Reid Andersen, Yuval Peres: Finding sparse cuts locally using evolving sets. 235-244
• 
  James R. Lee, Anastasios Sidiropoulos: On the geometry of graphs with a forbidden minor. 245-254
• 
  Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava: Twice-ramanujan sparsifiers. 255-262
• 
  Luca Trevisan: Max cut and the smallest eigenvalue. 263-272
• 
  Erin W. Chambers, Jeff Erickson, Amir Nayyeri: Homology flows, cohomology cuts. 273-282

Optimization

• 
  Moses Charikar, Konstantin Makarychev, Yury Makarychev: Integrality gaps for Sherali-Adams relaxations. 283-292
• 
  Claire Mathieu, Alistair Sinclair: Sherali-adams relaxations of the matching polytope. 293-302
• 
  Madhur Tulsiani: CSP gaps and reductions in the lasserre hierarchy. 303-312
• 
  Marek Karpinski, Warren Schudy: Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems. 313-322
• 
  Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, Maxim Sviridenko: Non-monotone submodular maximization under matroid and knapsack constraints. 323-332

Award papers

• 
  Chris Peikert: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. 333-342
• 
  Robin A. Moser: A constructive proof of the Lovász local lemma. 343-350

Privacy

• 
  Arpita Ghosh, Tim Roughgarden, Mukund Sundararajan: Universally utility-maximizing privacy mechanisms. 351-360
• 
  Dan Feldman, Amos Fiat, Haim Kaplan, Kobbi Nissim: Private coresets. 361-370
• 
  Cynthia Dwork, Jing Lei: Differential privacy and robust statistics. 371-380
• 
  Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, Salil P. Vadhan: On the complexity of differentially private data release: efficient algorithms and hardness results. 381-390

Quantum

• 
  Yi-Kai Liu: Quantum algorithms using the curvelet transform. 391-400
• 
  Amnon Ta-Shma: Short seed extractors against quantum storage. 401-408
• 
  Richard Cleve, Daniel Gottesman, Michele Mosca, Rolando D. Somma, David L. Yonge-Mallo: Efficient discrete-time simulations of continuous-time quantum query algorithms. 409-416
• 
  Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani: The detectability lemma and quantum gap amplification. 417-426

Graphs

• 
  Silvio Lattanzi, D. Sivakumar: Affiliation networks. 427-434
• 
  Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty: Fault-tolerant spanners for general graphs. 435-444
• 
  Ken-ichi Kawarabayashi, Bruce A. Reed: Hadwiger's conjecture is decidable. 445-454
• 
  Virginia Vassilevska, Ryan Williams: Finding, minimizing, and counting weighted subgraphs. 455-464

Complexity II

• 
  Eyal Kushilevitz, Enav Weinreb: On the complexity of communication complexity. 465-474
• 
  Emanuele Viola: Bit-probe lower bounds for succinct data structures. 475-482
• 
  Per Austrin, Johan Håstad: Randomly supported independence and resistance. 483-492
• 
  Ryan O'Donnell, Yi Wu: Conditional hardness for satisfiable 3-CSPs. 493-502

Economics

• 
  Jing Chen, Silvio Micali: A new approach to auctions and resilient mechanism design. 503-512
• 
  Tim Roughgarden: Intrinsic robustness of the price of anarchy. 513-522
• 
  Eyal Even-Dar, Yishay Mansour, Uri Nadav: On the convergence of regret minimization dynamics in concave games. 523-532
• 
  Robert Kleinberg, Georgios Piliouras, Éva Tardos: Multiplicative updates outperform generic no-regret learning in congestion games: extended abstract. 533-542
• 
  MohammadHossein Bateni, Moses Charikar, Venkatesan Guruswami: MaxMin allocation via degree lower-bounded arborescences. 543-552

Markov chains

• 
  Ravi Montenegro, Prasad Tetali: How long does it take to catch a wild kangaroo? 553-560
• 
  Ravi Kannan, Hariharan Narayanan: Random walks on polytopes and an affine interior point method for linear programming. 561-570
• 
  Fabio Martinelli, Alistair Sinclair: Mixing time for the solid-on-solid model. 571-580
• 
  Allan Sly: Reconstruction for the Potts model. 581-590
• 
  Martin Dietzfelbinger, Philipp Woelfel: Tight lower bounds for greedy routing in uniform small world rings. 591-600

Crypto II

• 
  Yevgeniy Dodis, Daniel Wichs: Non-malleable extractors and symmetric key cryptography from weak secrets. 601-610
• 
  Iftach Haitner, Omer Reingold, Salil P. Vadhan, Hoeteck Wee: Inaccessible entropy. 611-620
• 
  Yevgeniy Dodis, Yael Tauman Kalai, Shachar Lovett: On cryptography with auxiliary input. 621-630

Geometry

• 
  Jérémie Chalopin, Daniel Gonçalves: Every planar graph is the intersection graph of segments in the plane: extended abstract. 631-638
• 
  Boris Aronov, Esther Ezra, Micha Sharir: Small-size epsilon-nets for axis-parallel rectangles and boxes. 639-648
• 
  Yuval Rabani, Amir Shpilka: Explicit construction of a small epsilon-net for linear threshold functions. 649-658

Approximation algorithms II

• 
  Anupam Gupta, Amit Kumar: A constant-factor approximation for stochastic Steiner forest. 659-668
• 
  Yossi Azar, Iftah Gamzu, Xiaoxin Yin: Multiple intents re-ranking. 669-678
• 
  Jivitej S. Chadha, Naveen Garg, Amit Kumar, V. N. Muralidhara: A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation. 679-684
• 
  Anupam Gupta, Ravishankar Krishnaswamy, R. Ravi: Online and stochastic survivable network design. 685-694

Complexity III

• 
  Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova: An axiomatic approach to algebrization. 695-704
• 
  Phokion G. Kolaitis, Swastik Kopparty: Random graphs and the parity quantifier. 705-714
• 
  Jin-yi Cai, Pinyan Lu, Mingji Xia: Holant problems and counting CSP. 715-724
• 
  Gábor Kun, Mario Szegedy: A new line of attack on the dichotomy conjecture. 725-734