List of Accepted Papers to STOC09

Please find below a list of papers accepted to STOC09, including their authors. This list is preliminary and subject to change.

• Small-size ε-Nets for Axis-Parallel Rectangles and Boxes
  Boris Aronov, Esther Ezra, and Micha Sharir
• Non-monotone Submodular Maximization under Matroid and Knapsack Constraints
  Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko
• Private Coresets
  Dan Feldman, Amos Fiat, Haim Kaplan, and Kobbi Nissim
• Green's Conjecture and Testing Linear-Invariant Properties
  Asaf Shapira
• Distributed (Δ+1)-coloring in linear (in Δ) time
  Leonid Barenboim and Michael Elkin
• Affine Dispersers from Subspace Polynomials
  Eli Ben-Sasson and Swastik Kopparty
• A new Line of Attack on the Dichotomy Conjecture
  Gabor Kun and Mario Szegedy
• Exact Learning of Random DNF Formulas Under the Uniform Distribution
  Linda Sellie
• On Proximity Oblivious Testing
  Oded Goldreich and Dana Ron
• Explicit Construction of a Small ε-net for Linear Threshold Functions
  Yuval Rabani and Amir Shpilka
• Quantum Algorithms using the Curvelet Transform
  Yi-Kai Liu
• Multiple Intents Re-Ranking
  Yossi Azar, Iftah Gamzu, and Xiaoxin Yin
• A Constructive Proof of the Lovasz Local Lemma
  Robin A. Moser
• Holant Problems and Counting CSP
  Jin-Yi Cai, Pinyan Lu, and Mingji Xia
• Every Planar Graph is the Intersection Graph of Segments in the Plane
  Jeremie Chalopin and Daniel Goncalves
• 3-Query Locally Decodable Codes of Subexponential Length
  Klim Efremenko
• Fault-Tolerant Spanners for General Graphs
  S. Chechik, M. Langberg, D. Peleg, and L. Roditty
• Bit-Probe Lower Bounds for Succinct Data Structures
  Emanuele Viola
• A Nearly Optimal Oracle for Aoviding Failed Vertices and Edges
  Aaron Bernstein and David Karger
• An Efficient Algorithm for Partial Order Production
  Jean Cardinal, Samuel Fiorini, Gwenael Joret, Raphael M. Jungers, and J. Ian Munro
• On the Complexity of Communication Complexity
  Eyal Kushilevitz and Enav Weinreb
• List Decoding Tensor Products and Interleaved codes
  Parikshit Gopalan, Venkatesan Guruswami, and Prasad Raghavendra
• Non-Malleability Amplification
  Huijia Lin and Rafael Pass
• Max Cut and the Smallest Eigenvalue
  Luca Trevisan
• Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes
  Venkatesan Guruswami
• The Extended BG-Simulation and the Characterization of t-Resiliency
  Eli Gafni
• Finding Sparse Cuts Locally Using Evolving Sets
  Reid Andersen and Yuval Peres
• A Deterministic Reduction for the Gap Minimum Distance Problem
  Qi Cheng and Daqing Wan
• How Long Does it Take to Catch a Wild Kangaroo?
  Ravi Montenegro and Prasad Tetali
• An Improved Constant-Time Approximation Algorithm for Maximum Matchings
  Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito
• A Competitive Algorithm for Minimizing Weighted Flow Time on Unrelated Machines with Speed Augmentation
  Jivitej S. Chadha, Naveen Garg, Amit Kumar, and V. N. Muralidhara
• Randomly supported independence and resistance
  Per Austrin and Johan Håstad
• Random Graphs and the Parity Quantifier
  Phokion Kolaitis, Swastik Kopparty
• Differential Privacy and Robust Statistics
  Cynthia Dwork and Jing Lei
• Intrinsic Robustness of the Price of Anarchy
  Tim Roughgarden
• On the Convergence of Regret Minimization Dynamics in Concave Games
  Eyal Even-Dar, Yishay Mansour, and Uri Nadav
• CSP Gaps and Reductions in the Lasserre Hierarchy
  Madhur Tulsiani
• A Constant-Factor Approximation for Stochastic Steiner Forest
  Anupam Gupta and Amit Kumar
• On the Geometry of Graphs with a Forbidden Minor
  James R. Lee and Anastasios Sidiropoulos
• Resilient Knowledge-Based Mechanisms For Truly Combinatorial Auctions (and Implementation in Surviving Strategies)
  Jing Chen and Silvio Micali
• Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem
  Chris Peikert
• One-Round Authenticated Key Agreement from Weak Secrets
  Yevgeniy Dodis and Daniel Wichs
• Twice-Ramanujan Sparsifiers
  Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava
• Conditional Hardness for Satisfiable-3CSPs
  Ryan O'Donnell and Yi Wu
• Near-Perfect Load Balancing by Randomized Rounding
  Tobias Friedrich and Thomas Sauerwald
• Homology Flows, Cohomology Cuts
  Erin W. Chambers, Jeff Erickson, and Amir Nayyeri
• Numerical Linear Algebra in the Streaming Model
  Kenneth L. Clarkson and David P. Woodruff
• Testing Juntas Nearly Optimally
  Eric Blais
• Linear-time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems
  Marek Karpinski and Warren Schudy
• Direct Product Testing: Improved and Derandomized
  Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson
• An Axiomatic Approach to Algebrization
  Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova
• Efficient Discrete-Time Simulations of Continuous-Time Quantum Query Algorithms
  Richard Cleve, Daniel Gottesman, Michele Mosca, Rolando Somma, and David Yonge-Mallo
• Tight Lower Bounds for Greedy Routing in Uniform Small World Rings
  Martin Dietzfelbinger and Philipp Woelfel
• Sherali-Adams Relaxations of the Matching Polytope
  Claire Mathieu and Alistair Sinclair
• Mixing Time for the Solid-On-Solid Model
  Fabio Martinelli and Alistair Sinclair
• The Detectability Lemma and Quantum Gap Amplification
  Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh Vazirani
• MaxMin Allocation via Degree Lower-Bounded Arborescences
  MohammadHossein Bateni, Moses Charikar, and Venkatesan Guruswami
• Inaccessible Entropy
  Iftach Haitner, Omer Reingold, Salil Vadhan, and Hoeteck Wee
• Hadwiger's Conjecture is Decidable
  Ken-ichi Kawarabayashi and Bruce Reed
• A Unified Framework for Concurrent Security: Universal Composability from Stand-alone Non-malleability
  Huijia Lin, Rafael Pass, and Muthuramakrishnan Venkitasubramaniam
• Multiplicative Updates Outperform Generic No-Regret Learning in Congestion Games
  Robert Kleinberg, Georgios Piliouras, and Eva Tardos
• Affiliation Networks
  Silvio Lattanzi and D. Sivakumar
• Finding, Minimizing, and Counting Weighted Subgraphs
  Virginia Vassilevska and Ryan Williams
• Online and Stochastic Survivable Network Design
  Anupam Gupta, Ravishankar Krishnaswamy, and R. Ravi
• Reconstruction for the Potts Model
  Allan Sly
• Approximating Edit Distance in Near-Linear Time
  Alexandr Andoni and Krzysztof Onak
• Universally Utility-Maximizing Privacy Mechanisms
  Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan
• Integrality Gaps for Sherali-Adams Relaxations
  Moses Charikar, Konstantin Makarychev, and Yury Makarychev
• On Oblivious PTAS for Nash Equilibrium
  Constantinos Daskalakis and Christos H. Papadimitriou
• On Homomorphic Encryption over Circuits of Arbitrary Depth
  Craig Gentry
• Random walks on polytopes and an affine interior point method for linear programming.
  Ravi Kannan and Hariharan Narayanan
• When and How Can Data be Efficiently Released with Privacy?
  Cynthia Dwork, Moni Naor, Omer Reingold, Guy Rothblum, and Salil Vadhan
• On Cryptography with Auxiliary Input
  Yevgeniy Dodis, Yael Tauman Kalai, and Shachar Lovett
• Polynomial-time Theory of Matrix Groups
  László Babai, Robert M. Beals, and Ákos Seress
• Message Passing Algorithms and Improved LP Decoding
  Sanjeev Arora, Constantinos Daskalakis, and David Steurer
• A Fast and Efficient Algorithm for Low-rank Approximation of a Matrix
  Nam H. Nguyen, Thong T. Do, and Trac D. Tran
• Short Seed Extractors Against Quantum Storage
  Amnon Ta-Shma