STOC 2009

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

-   STOC 2009 Home   -