STOC 2015 Accepted Papers

• Computing with Tangles.
  Martin Grohe (RWTH Aachen University) and Pascal Schweitzer (RWTH Aachen University)

• Quantum Spectrum Testing.
  Ryan O'Donnell (Carnegie Mellon University); John Wright (Carnegie Mellon University)

• The Directed Grid Theorem.
  Ken-ichi Kawarabayashi (National Institute of Informatics and JST ERATO) and Stephan Kreutzer (Technical University Berlin)

• Test-and-Set in Optimal Space.
  George Giakkoupis (INRIA Rennes); Maryam Helmi (University of Calgary); Lisa Higham (University of Calgary); Philipp Woelfel (University of Calgary)

• l_p Row Sampling by Lewis Weights.
  Michael B. Cohen (MIT) and Richard Peng (MIT)

• Rectangles Are Nonnegative Juntas.
  Mika Göös (University of Toronto); Shachar Lovett (University of California, San Diego); Raghu Meka (University of California, Los Angeles); Thomas Watson (University of Toronto); David Zuckerman (University of Texas at Austin)

• Garbled RAM From One-Way Functions.
  Sanjam Garg (UC Berkeley), Steve Lu (UCLA), Rafail Ostrovsky (UCLA), Alessandra Scafuro (Boston University and Northeastern University)

• Testing Cluster Structure of Graphs.
  Artur Czumaj (University of Warwick), Pan Peng (TU Dortmund and Chinese Academy of Sciences), Christian Sohler (TU Dortmund)

• The Complexity of the Simplex Method.
  John Fearnley (University of Liverpool); Rahul Savani (University of Liverpool);

• Greedy Algorithms for Steiner Forest.
  Anupam Gupta (Carnegie Mellon University) and Amit Kumar (IIT Delhi)

• Inapproximability of Nash Equilibrium.
  Aviad Rubinstein (UC Berkeley)

• Non-malleable Reductions and Applications.
  Divesh Aggarwal (EPFL), Yevgeniy Dodis (NYU), Tomasz Kazana (University of Warsaw), Maciej Obremski (University of Warsaw)

• Approximate k-flat Nearest Neighbor Search.
  Wolfgang Mulzer (FU Berlin); Huy L. Nguyen (Simons Institute); Paul Seiferth (FU Berlin); Yannik Stein (FU Berlin)

• Sparse Quantum Codes from Quantum Circuits.
  Dave Bacon (University of Washington and Google), Steven T. Flammia (U Sydney), Aram W. Harrow (MIT), Jonathan Shi (Cornell)

• Minimizing Flow-Time on Unrelated Machines.
  Nikhil Bansal (Eindhoven University of Technology, Netherlands); Janardhan Kulkarni (Duke University)

• Prioritized Metric Structures and Embedding.
  Michael Elkin (Ben-Gurion University of the Negev); Arnold Filtser (Ben-Gurion University of the Negev); Neiman Ofer (Ben-Gurion University of the Negev)

• Random permutations using switching networks.
  Artur Czumaj (University of Warwick)

• From Independence to Expansion and Back Again.
  Tobias Christiani (IT University of Copenhagen); Rasmus Pagh (IT University of Copenhagen); Mikkel Thorup (University of Copenhagen);

• FPTAS for #BIS with Degree Bounds on One Side.
  Jingcheng Liu (UC Berkeley), Pinyan Lu (Microsoft Research)

• Excluded Grid Theorem: Improved and Simplified.
  Julia Chuzhoy (Toyota Technological Institute at Chicago)

• 2-Server PIR with sub-polynomial communication.
  Zeev Dvir (Princeton University) and Sivakanth Gopi (Princeton University)

• Sum-of-squares lower bounds for planted clique.
  Raghu Meka (UCLA), Aaron Potechin (MIT), Avi Wigderson (IAS)

• Reed-Muller codes for random erasures and errors.
  Emmanuel Abbe (Princeton University); Amir Shpilka (Tel-Aviv University); Avi Wigderson (IAS, Princeton).

• Sketching and Embedding are Equivalent for Norms.
  Alexandr Andoni (Simons Institute); Robert Krauthgamer (Weizmann Institute of Science); Ilya Razenshteyn (MIT)

• Clustered Integer 3SUM via Additive Combinatorics.
  Timothy M. Chan (University of Waterloo); Moshe Lewenstein (Bar-Ilan University)

• Small value parallel repetition for general games.
  Mark Braverman (Princeton University); Ankit Garg (Princeton University).

• Approximate Distance Oracles with Improved Bounds.
  Shiri Chechik (Tel-Aviv University)

• Learning Mixtures of Gaussians in High Dimensions.
  Rong Ge (Microsoft Research New England); Qingqing Huang (MIT); Sham M. Kakade (Microsoft Research New England)

• On the Lovasz Theta function for Independent Sets.
  Nikhil Bansal (TU Eindhoven), Anupam Gupta (CMU), Guru Guruganesh (CMU)

• Secretary Problems with Non-Uniform Arrival Order.
  Thomas Kesselheim (Max-Planck-Institut fur Informatik); Robert Kleinberg (Cornell University and Microsoft Research); Rad Niazadeh (Cornell University)

• Proof of the satisfiability conjecture for large k.
  Jian Ding (University of Chicago); Allan Sly (UC Berkeley and Australian National University); Nike Sun (Microsoft Research and MIT)

• How Well Can Graphs Represent Wireless Interference?
  Magnus M. Halldorsson (Reykjavik University) and Tigran Tonoyan (Reykjavik University)

• Tight bounds for learning a mixture of two Gaussians.
  Moritz Hardt (IBM Research Almaden); Eric Price (The University of Texas at Austin)

• Succinct Randomized Encodings and their Applications.
  Nir Bitansky (MIT); Sanjam Garg (University of California, Berkeley); Huijia Lin (University of California, Santa Barbara); Rafael Pass (Cornell University); Sidharth Telang (Cornell University)

• An Interactive Information Odometer and Applications.
  Mark Braverman (Princeton University) and Omri Weinstein (Princeton University)

• Efficiently learning Ising models on Arbitrary Graphs.
  Guy Bresler (MIT)

• Sum of Squares Lower Bounds from Pairwise Independence.
  Boaz Barak (Microsoft Research), Pravesh Kothari (University of Texas at Austin), Siu On Chan (Microsoft Research)

• Consistency Thresholds for the Planted Bisection Model.
  Elchanan Mossel (U.C. Berkeley and University of Pennsylvania) ; Joe Neeman (U.T. Austin); Allan Sly (U.C. Berkeley and Australian National University)

• Randomized Rounding for the Largest $j$-Simplex Problem.
  Aleksandar Nikolov (Microsoft Research)

• Hardness of Graph Pricing Through Generalized Max-Dicut.
  Euiwoong Lee (Carnegie Mellon)

• Adjacency labeling schemes and induced-universal graphs.
  Stephen Alstrup (University of Copenhagen), Haim Kaplan (Tel Aviv University), Mikkel Thorup (University of Copenhagen), Uri Zwick (Tel-Aviv University)

• On the Complexity of Nash Equilibria in Anonymous Games.
  Xi Chen (Georgia Institute of Technology); David Durfee (Columbia University); Anthi Orfanou (Columbia University)

• Analysis of a Classical Matrix Preconditioning Algorithm.
  Leonard J. Schulman (Caltech); Alistair Sinclair (UC Berkeley)

• Online Submodular Welfare Maximization: Greedy beats 1/2.
  Nitish Korula (Google Research); Vahab Mirrokni (Google Research); Morteza Zadimoghaddam (Google Research)

• Preserving Statistical Validity in Adaptive Data Analysis.
  Cynthia Dwork (Microsoft Research); Vitaly Feldman (IBM Research - Almaden); Moritz Hardt (IBM Research - Almaden); Toniann Pitassi (University of Toronto); Omer Reingold; Aaron Roth (University of Pennsylvania)

• High Parallel Complexity Graphs and Memory-Hard Functions.
  Jo\"el Alwen (IST Austria); Vladimir Serbinenko (Google Z\"urich)

• Almost Optimal Pseudorandom Generators for Spherical Caps.
  Pravesh K. Kothari (The University of Texas at Austin); Raghu Meka (University of California Los Angeles)

• The communication complexity of interleaved group products.
  W. T. Gowers (University of Cambridge); Emanuele Viola (Northeastern & Harvard)

• Leveled Fully Homomorphic Signatures from Standard Lattices.
  Sergey Gorbunov (MIT); Vinod Vaikuntanathan (MIT); Daniel Wichs (Northeastern)

• Local, Private, Efficient Protocols for Succinct Histograms.
  Raef Bassily (The Pennsylvania State University); Adam Smith (The Pennsylvania State University)

• Faster canonical forms for primitive coherent configurations.
  John Wilmes (University of Chicago) and Xiaorui Sun (Columbia University)

• Approximating the Nash Social Welfare with Indivisible Items.
  Richard Cole (New York University) and Vasilis Gkatzelis (Stanford University)

• Optimal Data-Dependent Hashing for Approximate Near Neighbors.
  Alexandr Andoni (Simons Institute) and Ilya Razenshteyn (MIT)

• The List Decoding Radius of Reed Muller Codes over Small Fields.
  Abhishek Bhowmick (University of Texas at Austin) and Shachar Lovett (University of California, San Diego)

• Time lower bounds for nonadaptive turnstile streaming algorithms.
  Kasper Green Larsen (Aarhus University), Jelani Nelson (Harvard University), Huy Le Nguyen (Simons Institute)

• Lower bounds on the size of semidefinite programming relaxations.
  James R. Lee (University of Washington), Prasad Raghavendra (UC Berkeley), David Steurer (Cornell)

• Bypassing KLS: Gaussian Cooling and an $O*(n^3)$ Volume Algorithm.
  Ben Cousins (Georgia Tech); Santosh Vempala (Georgia Tech)

• Learning Arbitrary Statistical Mixtures of Discrete Distributions.
  Jian Li (Tsinghua University), Yuval Rabani (The Hebrew University), Leonard J. Schulman (California Institute of Technology), Chaitanya Swamy (University of Waterloo)

• Nearly-Linear Time Positive LP Solver with Faster Convergence Rate.
  Zeyuan Allen-Zhu (MIT); Lorenzo Orecchia (Boston University)

• Inapproximability of combinatorial problems via small LPs and SDPs.
  Gábor Braun (Georgia Tech); Sebastian Pokutta (Georgia Tech); Daniel Zink (Georgia Tech)

• Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms.
  Anand Louis (Princeton University)

• A characterization of the capacity of online (causal) binary channels.
  Zitan Chen (The Chinese University of Hong Kong), Sidharth Jaggi (The Chinese University of Hong Kong), Michael Langberg (SUNY at Buffalo)

• A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection.
  Kyle Fox (Duke University); Philip N. Klein (Brown University); Shay Mozes (Interdisciplinary Center, Herzliya, Israel)

• Fast Matrix Multiplication: Limitations of Coppersmith-Winograd Method.
  Andris Ambainis (University of Latvia); Yuval Filmus (Institute for Advanced Study); François Le Gall (University of Tokyo)

• Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time.
  Ken-ichi Kawarabayashi (National Institute of Informatics, Tokyo, Japan) and Mikkel Thorup (University of Copenhagen, Denmark)

• Randomized Composable Core-sets for Distributed Submodular Maximization.
  Vahab Mirrokni (Google Research New York); Morteza Zadimoghaddam (Google Research New York)

• Succinct Garbling and Indistinguishability Obfuscation for RAM Programs.
  Ran Canetti (Tel-Aviv University and Boston University); Justin Holmgren (MIT); Abhishek Jain (Johns Hopkins); Vinod Vaikuntanathan (MIT)

• Matching triangles and basing hardness on an extremely popular conjecture.
  Amir Abboud (Stanford), Virginia Vassilevska Williams (Stanford), Huacheng Yu (Stanford)

• Beyond the Euler characteristic: Approximating the genus of general graphs.
  Ken-ichi Kawarabayashi (National Institute of Informatics, Japan); ; Anastasios Sidiropoulos (The Ohio State University)

• On the Complexity of Random Satisfiability Problems with Planted Solutions.
  Vitaly Feldman (IBM Research - Almaden); Will Perkins (University of Birmingham); Santosh Vempala (Georgia Tech)

• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation.
  Michael B. Cohen (MIT); Sam Elder (MIT); Cameron Musco (MIT); Christopher Musco (MIT); Madalina Persu (MIT)

• Indistinguishability Obfuscation for Turing Machines with Unbounded Memory.
  Venkata Koppula (University of Texas at Austin); Allison B. Lewko (Columbia University); Brent Waters (University of Texas at Austin)

• Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method.
  Boaz Barak (Microsoft Research); Jonathan Kelner (MIT); David Steurer (Cornell University)

• Exponential Separation of Information and Communication for Boolean Functions.
  Anat Ganor (Weizmann Institute); Gillat Kol (IAS); Ran Raz (Weizmann Institute & IAS)

• Toward a unified theory of sparse dimensionality reduction in Euclidean space.
  Jean Bourgain (IAS), Sjoerd Dirksen (RWTH Aachen University), Jelani Nelson (Harvard)

• Solving the Shortest Vector Problem in 2^n time via Discrete Gaussian Sampling.
  Divesh Aggarwal (École polytechnique fédérale de Lausanne); Daniel Dadush (Centrum Wiskunde & Informatica); Oded Regev (New York University); Noah Stephens-Davidowitz (New York University)

• An improved version of the Random-Facet pivoting rule for the simplex algorithm.
  Thomas Dueholm Hansen (Stanford University); Uri Zwick (Tel Aviv University)

• Forrelation: A Problem that Optimally Separates Quantum from Classical Computing.
  Scott Aaronson (MIT) and Andris Ambainis (University of Latvia)

• Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension.
  Amit Daniely (Hebrew University), Michael Schapira (Hebrew University), Gal Shahaf (Hebrew University)

• Polynomially low error PCPs with $\poly\loglog\n$ queries via modular composition.
  Irit Dinur (Weizman Institute); Prahladh Harsha (TIFR); Guy Kindler (Hebrew University)

• Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates.
  Zeyuan Allen-Zhu (MIT); Zhenyu Liao (Boston University); Lorenzo Orecchia (Boston University)

• Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices.
  Ankur Moitra (MIT)

• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false).
  Arturs Backurs (MIT) and Piotr Indyk (MIT)

• Boolean function monotonicity testing requires (almost) $n^{1/2}$ non-adaptive queries.
  Xi Chen (Columbia University); Anindya De (IAS/DIMACS); Rocco A. Servedio (Columbia University); Li-Yang Tan (Columbia University/Simons Institute)

• The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree.
  Jakub Lacki (University of Warsaw), Jakub Ocwieja (University of Warsaw), Marcin Pilipczuk (University of Warwick and Unviersity of Warsaw), Piotr Sankowski (Univerisity of Warsaw), Anna Zych (University of Warsaw)

• A directed isoperimetric inequality with application to Bregman near neighbor lower bounds.
  Amirali Abdullah (University of Utah), Suresh Venkatasubramanian (University of Utah)

• Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity.
  Ittai Abraham (VMware Research); Danny Dolev (Hebrew University)

• Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions.
  Shachar Lovett (University of California, San Diego); Jiapeng Zhang (University of California, San Diego)

• Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.
  Sayan Bhattacharya (The Institute of Mathematical Sciences, Chennai, India), Monika Henzinger (University of Vienna), Danupon Nanongkai (KTH Royal Institute of Technology), Charalampos E. Tsourakakis (Harvard University)

• Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs.
  Shuchi Chawla (University of Wisconsin-Madison); Konstantin Makarychev (Microsoft Research); Tselil Schramm (UC Berkeley); Grigory Yaroslavtsev (University of Pennsylvania)

• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.
  Monika Henzinger (University of Vienna, Austria); Sebastian Krinninger (University of Vienna, Austria); Danupon Nanongkai (KTH Royal Institute of Technology); Thatchaphol Saranurak (KTH Royal Institute of Technology)

• Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem.
  Siddharth Barma (California Institute of Technology)

• A New, Fully Quantum Notion of Information Complexity, and an Application to Direct Sum for Bounded Round Quantum Communication Complexity.
  Dave Touchette (Université de Montréal)