41. STOC 2009: Bethesda, MD, USA

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 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
S. Chechik, M. 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