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.
 Smallsize εNets for AxisParallel Rectangles and Boxes
Boris Aronov, Esther Ezra, and Micha Sharir
 Nonmonotone 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 LinearInvariant Properties
Asaf Shapira
 Distributed (Δ+1)coloring in linear (in Δ) time
Leonid Barenboim and Michael Elkin
 Affine Dispersers from Subspace Polynomials
Eli BenSasson 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
YiKai Liu
 Multiple Intents ReRanking
Yossi Azar, Iftah Gamzu, and Xiaoxin Yin
 A Constructive Proof of the Lovasz Local Lemma
Robin A. Moser
 Holant Problems and Counting CSP
JinYi Cai, Pinyan Lu, and Mingji Xia
 Every Planar Graph is the Intersection Graph of Segments in the Plane
Jeremie Chalopin and Daniel Goncalves
 3Query Locally Decodable Codes of Subexponential Length
Klim Efremenko
 FaultTolerant Spanners for General Graphs
S. Chechik, M. Langberg, D. Peleg, and L. Roditty
 BitProbe 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
 NonMalleability Amplification
Huijia Lin and Rafael Pass
 Max Cut and the Smallest Eigenvalue
Luca Trevisan
 Artin automorphisms, Cyclotomic function fields, and Folded listdecodable codes
Venkatesan Guruswami
 The Extended BGSimulation and the Characterization of tResiliency
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 ConstantTime 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 EvenDar, Yishay Mansour, and Uri Nadav
 CSP Gaps and Reductions in the Lasserre Hierarchy
Madhur Tulsiani
 A ConstantFactor 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 KnowledgeBased Mechanisms For Truly Combinatorial Auctions (and Implementation in Surviving Strategies)
Jing Chen and Silvio Micali
 PublicKey Cryptosystems from the WorstCase Shortest Vector Problem
Chris Peikert
 OneRound Authenticated Key Agreement from Weak Secrets
Yevgeniy Dodis and Daniel Wichs
 TwiceRamanujan Sparsifiers
Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava
 Conditional Hardness for Satisfiable3CSPs
Ryan O'Donnell and Yi Wu
 NearPerfect 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
 Lineartime Approximation Schemes for the GaleBerlekamp 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 DiscreteTime Simulations of ContinuousTime Quantum Query Algorithms
Richard Cleve, Daniel Gottesman, Michele Mosca, Rolando Somma, and David YongeMallo
 Tight Lower Bounds for Greedy Routing in Uniform Small World Rings
Martin Dietzfelbinger and Philipp Woelfel
 SheraliAdams Relaxations of the Matching Polytope
Claire Mathieu and Alistair Sinclair
 Mixing Time for the SolidOnSolid 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 LowerBounded Arborescences
MohammadHossein Bateni, Moses Charikar, and Venkatesan
Guruswami
 Inaccessible Entropy
Iftach Haitner, Omer Reingold, Salil Vadhan, and Hoeteck Wee
 Hadwiger's Conjecture is Decidable
Kenichi Kawarabayashi and Bruce Reed
 A Unified Framework for Concurrent Security: Universal Composability from Standalone Nonmalleability
Huijia Lin, Rafael Pass, and Muthuramakrishnan
Venkitasubramaniam
 Multiplicative Updates Outperform Generic NoRegret 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 NearLinear Time
Alexandr Andoni and Krzysztof Onak
 Universally UtilityMaximizing Privacy Mechanisms
Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan
 Integrality Gaps for SheraliAdams 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
 Polynomialtime 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 Lowrank Approximation of a Matrix
Nam H. Nguyen, Thong T. Do, and Trac D. Tran
 Short Seed Extractors Against Quantum Storage
Amnon TaShma
