STOC 2011 Accepted Papers (with pdf files)

1. Quantum One-Way Communication can be Exponentially Stronger Than Classical Communication Bo’az Klartag and Oded Regev [arXiv]
2. Multicut is FPT Nicolas Bousquet and Jean Daligault and Stephan Thomasse [arXiv]
3. Pareto Optimal Solutions for Smoothed Analysts Ankur Moitra and Ryan O’Donnell [arXiv]
4. An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance Amit Chakrabarti and Oded Regev [arXiv]
5. Constant Round Non-Malleable Protocols using One Way Functions Vipul Goyal [ePrint]
6. Fixed-parameter tractability of multicut parameterized by the size of the cutset Daniel Marx and Igor Razgon [arXiv]
7. Secure Computation with Information Leaking to an Adversary Miklos Ajtai
8. Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP Yuichi Yoshida [ECCC]
9. Near-Optimal Private Approximation Protocols via a Black-Box Transformation David P. Woodruff
10. Cover times, blanket times, and majorizing measures Jian Ding and James R. Lee and Yuval Peres [arXiv]
11. Breaking the $k^2$ barrier for explicit RIP matrices Jean Bourgain, S. J. Dilworth, Kevin Ford, Sergei Konyagin, Denka Kutzarova [pdf]
12. Analyzing Network Coding Gossip Made Easy Bernhard Haeupler [arXiv]
13. Deterministic Construction of a high dimensional $\ell_p$ section in $\ell_1^n$ for any $p<2$ Zohar S. Karnin [ECCC]
14. Schaefer’s Theorem for Graphs Manuel Bodirsky and Michael Pinsker [arXiv]
15. Tight Bounds for Parallel Randomized Load Balancing Christoph Lenzen and Roger Wattenhofer [pdf]
16. Pseudorandom Generators for Group Products Michal Koucky and Prajakta Nimbhorkar and Pavel Pudlak [pdf]
17. Contraction Decomposition in H-Minor-Free Graphs and Algorithmic Applications Erik Demaine and Mohammad Hajiaghayi and Ken-ichi Kawarabayashi
18. Correlation testing for affine invariant properties on $\F_p^n$ in the high error regime Hamed Hatami and Shachar Lovett
19. Every Property of Hyperfinite Graphs is Testable Ilan Newman and Christian Sohler
20. Fast Moment Estimation in Data Streams in Optimal Space Daniel M. Kane and Jelani Nelson and Ely Porat and David P. Woodruff [arXiv]
21. An Algorithm for the Graph Crossing Number Problem Julia Chuzhoy [arXiv]
22. From Affine to Two-Source Extractors via Approximate Duality Eli Ben-Sasson, Noga Zewi [ECCC]
23. On Optimal Single-Item Auctions Christos Papadimitriou and George Pierrakos [arXiv]
24. Directed Spanners via Flow-Based Linear Programs Michael Dinitz and Robert Krauthgamer [arXiv]
25. Mechanism design with uncertain inputs (to err is human, to forgive divine) Uriel Feige and Moshe Tennenholtz
26. Santa Claus Schedules Jobs on Unrelated Machines Ola Svensson [arXiv]
27. Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes Boaz Barak and Zeev Dvir and Avi Wigderson and Amir Yehudayoff [ECCC]
28. A simpler algorithm and shorter proof for the graph minor decomposition Ken-ichi Kawarabayashi and Paul Wollan
29. Finding topological subgraphs is fixed-parameter tractable Martin Grohe and Ken-ichi Kawarabayashi and Daniel Marx and Paul Wollan [arXiv]
30. Constant-Round Non-Malleable Commitments from Any One-Way Function Huijia Lin, Rafael Pass [ePrint]
31. Privacy-preserving Statistical Estimation with Optimal Convergence Rates Adam Smith
32. Learning Submodular Functions Maria Florina Balcan and Nicholas J. A. Harvey [arXiv]
33. Pseudorandom Generators for Combinatorial Shapes Parikshit Gopalan and Raghu Meka and Omer Reingold and David Zuckerman [ECCC]
34. NP-Hardness of Approximately Solving Linear Equations Over Reals Subhash Khot and Dana Moshkovitz [ECCC]
35. Towards Coding for Maximum Errors in Interactive Communication Mark Braverman and Anup Rao [pdf]
36. K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance Piotr Indyk and Eric Price
37. Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs Paul Christiano and Jonathan A. Kelner and Aleksander Madry and Daniel A. Spielman and Shang-Hua Teng [arXiv]
38. A General Framework for Graph Sparsification Wai Shing Fung and Ramesh Hariharan and Nicholas J. A. Harvey and Debmalya Panigrahi
39. Breaking O(n^{1/2})-approximation algorithms for the edge-disjoint paths problem Ken-ichi Kawarabayashi and Yusuke Kobayashi
40. Linearizable Implementations Do Not Suffice for Randomized Distributed Computation Wojciech Golab and Lisa Higham and Philipp Woelfel
41. Online Bipartite Matching with Unknown Distributions Chinmay Karande and Aranyak Mehta and Pushkar Tripathi
42. Near-optimal distortion bounds for embedding doubling spaces into $L_1$ James R. Lee and Anastasios Sidiropoulos
43. Mechanisms for (Mis)allocating Scientific Credit Jon Kleinberg and Sigal Oren
44. Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes Chandra Chekuri and Jan Vondrak and Rico Zenklusen
45. Improved Minimum Cuts and Maximum Flows in Undirected Planar Graphs Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen
46. An Impossibility Result for Truthful Combinatorial Auctions with Submodular Valuations Shahar Dobzinski [arXiv]
47. Geometric Complexity Theory and Tensor Rank Peter Buergisser and Christian Ikenmeyer [arXiv]
48. A quasipolynomial-time algorithm for the quantum separability problem Fernando Brandao and Matthias Christandl and Jon Yard
49. A Full Derandomization of Schoening’s k-SAT Algorithm Robin A. Moser and Dominik Scheder [arXiv]
50. Rank-1 Bimatrix Games: A Homeomorphism and a Polynomial Time Algorithm Bharat Adsul and Jugal Garg and Ruta Mehta and Milind Sohoni [arXiv]
51. How to Leak on Key Updates Allison Lewko and Mark Lewko and Brent Waters
52. Separating Succinct Non-Interactive Arguments From All Falsifiable Assumptions Craig Gentry and Daniel Wichs [ePrint]
53. Social Networks Spread Rumors in Sublogarithmic Time Benjamin Doerr and Mahmoud Fouz and Tobias Friedrich
54. High-rate codes with sublinear-time decoding Swastik Kopparty and Shubhangi Saraf and Sergey Yekhanin [ECCC]
55. The Computational Complexity of Linear Optics Scott Aaronson and Alex Arkhipov [arXiv]
56. Dueling algorithms Nicole Immorlica and Adam Tauman Kalai and Brendan Lucier and Ankur Moitra and Andrew Postlewaite and Moshe Tennenholtz [arXiv]
57. Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn’t matter Nitin Saxena and C. Seshadhri [ECCC]
58. Don’t Rush into a Union: Take Time to Find Your Roots Mihai Patrascu and Mikkel Thorup
59. From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions for Submodular Bidders Shaddin Dughmi and Tim Roughgarden and Qiqi Yan
60. Privately Releasing Conjunctions and the Statistical Query Barrier Anupam Gupta and Moritz Hardt and Aaron Roth and Jonathan Ullman [arXiv]
61. Optimal Path Search in Small Worlds: Dimension Matters George Giakkoupis and Nicolas Schabanel
62. Distributed Verification and Hardness of Distributed Approximation Atish Das Sarma and Stephan Holzer and Liah Kor and Amos Korman and Danupon Nanongkai and Gopal Pandurangan and David Peleg and Roger Wattenhofer [arXiv]
63. Parallel Repetition of Entangled Games Julia Kempe and Thomas Vidick [arXiv]
64. Subspace Embeddings for the L_1-norm with Applications Christian Sohler and David Woodruff
65. A Unified Framework for Approximating and Clustering Data Dan Feldman and Michael Langberg
66. The Equivalence of the Random Oracle Model and the Ideal Cipher Model, Revisited Thomas Holenstein and Robin Kunzler and Stefano Tessaro [arXiv]
67. Limits of Provable Security From Standard Assumptions Rafael Pass
68. Optimal Auctions with Correlated Bidders are Easy Shahar Dobzinski and Hu Fu and Robert Kleinberg [arXiv]
69. Strong Direct Product Theorems for Quantum Communication and Query Complexity Alexander A. Sherstov [arXiv]
70. Inner Product Spaces for MinSum Coordination Mechanisms Richard Cole and Jose R. Correa and Vasilis Gkatzelis and Vahab Mirrokni and Neil Olver [arXiv]
71. The Topology of Wireless Communication Erez Kantor and Zvi Lotker and Merav Parter and David Peleg
72. An LLL-Reduction Algorithm with Quasi-linear Time Complexity Andrew Novocin and Damien Stehle and Gilles Villard [pdf]
73. From Low-Distortion Norm Embeddings to Explicit Uncertainty Relations and Efficient Information Locking Omar Fawzi and Patrick Hayden and Pranab Sen [arXiv]
74. The Power of Simple Tabulation Hashing Mihai Patrascu and Mikkel Thorup [arXiv]
75. Subexponential lower bounds for randomized pivoting rules for the simplex algorithm Oliver Friedmann and Thomas Dueholm Hansen and Uri Zwick [pdf]
76. Almost Settling the Hardness of Noncommutative Determinant Steve Chien and Prahladh Harsha and Alistair Sinclair and Srikanth Srinivasan [arXiv]
77. Approximate Polytope Membership Queries Sunil Arya and Guilherme D. da Fonseca and David M. Mount [pdf]
78. Exact Algorithms for Solving Stochastic Games Kristoffer Arnsfelt Hansen and Michal Koucky and Niels Lauritzen and Peter Bro Miltersen and Elias P. Tsigaridas
79. Online Bipartite Matching with Random Arrivals: A Strongly Factor Revealing LP Approach Mohammad Mahdian and Qiqi Yan
80. Estimating the unseen: an n/log(n)-sample estimator for entropy, support size, and other distribution properties, with a proof of optimality via two new central limit theorems Gregory Valiant and Paul Valiant
81. Almost Tight Bounds for Reordering Buffer Management Anna Adamaszek and Artur Czumaj and Matthias Englert and Harald Raecke
82. Black-Box Identity Testing of Depth-4 Multilinear Circuits Shubhangi Saraf and Ilya Volkovich
83. Moser and Tardos meet Lovasz Kashyap Kolipaka and Mario Szegedy
84. On the Complexity of Powering in Finite Fields Swastik Kopparty