In order of submission.
  1. Settling the Polynomial Learnability of Mixtures of Gaussians
    Authors: Ankur Moitra (MIT) and Gregory Valiant (UC Berkeley)

  2. Solving linear systems through nested dissection
    Authors: Noga Alon (Tel Aviv University) Raphael Yuster (University of Haifa)

  3. Improved Bounds for Geometric Permutations
    Authors: Natan Rubin, Haim Kaplan and Micha Sharir (Tel Aviv University)

  4. Constructive Algorithms for Discrepancy Minimization
    Authors: Nikhil Bansal (IBM Research)

  5. An efficient test for product states, with applications to quantum Merlin-Arthur games
    Authors:Aram W. Harrow: Department of Mathematics, University of Bristol & Departmenty of Computer Science and Engineering, University of Washington and Ashley Montanaro: Department of Computer Science, University of Bristol and Department of Applied Mathematics and Theoretical Physics, University of Cambridge

  6. Replacement Paths via Fast Matrix Multiplication
    Authors: Oren Weimann (Weizmann Institute of Science) Raphael Yuster (University of Haifa)

  7. Logspace Versions of the Theorems of Bodlaender and Courcelle
    Authors: Michael Elberfeld, Andreas Jakoby, Till Tantau, Institute of Theoretical Computer Science, University of Lubeck, Germany.

  8. Impossibility of Differentially Private Universally Optimal Mechanisms
    Authors : Kobbi Nissim (Microsoft AI, Israel, and Dept. of Computer Science, Ben-Gurion University) Hai Brenner (Dept. of Mathematics, Ben-Gurion University)

  9. Determinant Sums for Undirected Hamiltonicity
    Author: Andreas Bjorklund, Lund University, Department of Computer Science, P.O.Box 118, SE-22100 Lund, Sweden

  10. A non-linear lower bound for planar epsilon-nets
    Author: Noga Alon, Tel Aviv University and IAS, Princeton

  11. Pseudorandom generators for CC_0[p] and the Fourier spectrum of low-degree polynomials over finite fields
    Authors: Shachar Lovett, The Weizmann Institute of Science, Partha Mukhopadhyay, Technion - Israel Institute of Technology, Amir Shpilka, Technion - Israel Institute of Technology

  12. A lower bound for dynamic approximate membership data structures
    Authors: Shachar Lovett and Ely Porat

  13. A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights
    Authors: Jin-Yi Cai: University of Wisconsin - Madison Xi Chen: University of Southern California

  14. The Geometry of Manipulation - a Quantitative Proof of the Gibbard Satterthwaite Theorem
    Authors: Marcus Isaksson and Guy Kindler and Elchanan Mossel

  15. Optimal Testing of Reed-Muller Codes
    Authors: Arnab Bhattacharyya (MIT) Swastik Kopparty (MIT) Grant Schoenebeck (UC Berkeley) Madhu Sudan (Microsoft Research New England) David Zuckerman (UT Austin)

  16. Pseudorandom generators for regular branching programs.
    Authors: Mark Braverman (MSR New England and University of Toronto), Anup Rao (University of Washington), Ran Raz (Weizmann Institute of Science) and Amir Yehudayoff (IAS and Technion)

  17. Local list decoding with a constant number of queries
    Authors: Avraham Ben-Aroya and Klim Efremenko and Amnon Ta-Shma

  18. New Constructive Aspects of the Lovasz Local Lemma
    Authors: Bernhard Haeupler (MIT) Barna Saha (University of Maryland) and Aravind Srinivasan (University of Maryland)

  19. Matching vector codes
    Authors: Zeev Dvir, Princeton University Parikshit Gopalan, Microsoft Research Sergey Yekhanin, Microsoft Research

  20. Approximation Algorithms for the Edge-Disjoint Paths Problem via Raecke Decompositions
    Author: Matthew Andrews, Alcatel-Lucent Bell Laboratories, 600-700 Mountain Avenue, Murray Hill, NJ 07974

  21. The complexity of distributions
    Author: Emanuele Viola, Northeastern University

  22. All-Pairs Shortest Paths in $O(n^2)$ Time With High Probability
    Authors: Yuval Peres, Microsoft Research, Redmond, Dmitry Sotnikov, Tel Aviv University, Benny Sudakov, UCLA, Uri Zwick, Tel Aviv University

  23. Computational Transition at the Uniqueness Threshold
    Author: Allan Sly, Microsoft Research, Redmond

  24. Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature
    Authors: David Doty, University of Western Ontario, Matthew J. Patitz, University of Texas -- Pan American, Dustin Reishus, University of Southern California, Robert T. Schweller, University of Texas -- Pan American, Scott M. Summers, University of Wisconsin -- Platteville

  25. Subcubic Equivalences Between Path, Matrix, and Triangle Problems
    Authors: Virginia Vassilevska Williams, UC Berkeley and Ryan Williams, IBM Almaden Research Center

  26. Minimum-Cost Network Design with (Dis)economies of Scale
    Authors: Matthew Andrews and Spyridon Antonakopoulos and Lisa Zhang, Bell Laboratories, 600-700 Mountain Avenue, Murray Hill, NJ 07974

  27. A Unified Framework for Testing Linear-Invariant Properties
    Authors: Arnab Bhattacharyya (MIT), Elena Grigorescu (MIT), Asaf Shapira (Georgia Tech)

  28. Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition
    Authors: Amit Chakrabarti, Dartmouth College, Graham Cormode, AT&T Labs -- Research, Ranganath Kondapally, Dartmouth College, Andrew McGregor, University of Massachusetts, Amherst

  29. Optimal stochastic planarization
    Anastasios Sidiropoulos , Toyota Technological Institute at Chicago

  30. Bounds on Monotone Switching Networks for Directed Connectivity
    Author: Aaron Potechin, MIT

  31. A Fourier-analytic approach to Reed-Muller decoding
    Parikshit Gopalan, Microsoft Research Silicon Valley.

  32. Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
    Authors: Jin-Yi Cai, University of Wisconsin-Madison and Beijing University, Pinyan Lu, Microsoft Research Asia, and Mingji Xia, Institute of Software, Chinese Academy of Sciences

  33. Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation
    Authors: Yuriy Arbitman and Moni Naor and Gil Segev, Weizmann Institute of Science.

  34. Vertex Sparsifiers and Abstract Rounding Algorithms
    Moses Charikar (Princeton University), Tom Leighton (MIT and Akamai Technologies, Inc), Shi Li (Princeton University), Ankur Moitra (MIT)

  35. Deciding first-order properties for sparse graphs
    Authors: Zdenek Dvorak (Charles University, Prague), Daniel Kral (Charles University, Prague), Robin Thomas (Georgia Institute of Technology, Atlanta)

  36. Clustering with Spectral Norm and the k-means Algorithm
    Amit Kumar (IIT Delhi) and Ravindran Kannan (Microsoft Research India Lab, Bangalore)

  37. Testing Properties of Sparse Images
    Authors: Dana Ron and Gilad Tsur, Department of Electrical Engineering - Systems, Tel-Aviv University.

  38. Frugal Mechanism Design via Spectral Techniques
    Authors: Ning Chen and Edith Elkind and Nick Gravin and Fedor Petrov

  39. A separator theorem in minor-closed classes
    Authors Ken-ichi Kawarabayashi (National Institute of Informatics, Japan) and Bruce Reed (McGill University, Canada, and Sophia Antipolis, France)

  40. On the Insecurity of Parallel Repetition for Leakage Resilience
    Allison Lewko (University of Texas at Austin) and Brent Waters (University of Texas at Austin)

  41. Approaching optimality for solving SDD linear systems
    Ioannis Koutis†, Gary L. Miller and Richard Peng, Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15213

  42. The subexponential upper bound for on-line chain partitioning problem
    Authors: Bart\l{}omiej Bosek - Jagiellonian University, Theoretical Computer Science, ul. prof. Stanis\l{}awa \L{}ojasiewicza 6, Krak\'{o}w 30-348, Poland and Tomasz Krawczyk - Jagiellonian University, Theoretical Computer Science, ul. prof. Stanis\l{}awa \L{}ojasiewicza 6, Krak\'{o}w 30-348, Poland.

  43. One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk
    Authors: Ashish Goel (Stanford University) Ian Post (Stanford University)

  44. On the Queue Number of Planar Graphs
    Authors: Giuseppe Di Battista, Roma Tre University, Italy, Fabrizio Frati, Roma Tre University, Italy, J\'anos Pach, EPFL Lausanne, Switzerland

  45. Cryptography Against Continuous Memory Attacks
    AUthors: Yevgeniy Dodis and Kristiyan Haralambiev and Adriana Lopez-Alt and Daniel Wich

  46. Hardness of Finding Independent Sets in Almost 3-Colorable Graphs
    Authors: Irit Dinur and Subhash Khot and Will Perkins and Muli Safra

  47. Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
    Authors: Glencora Borradaile: School of Electrical Engineering and Computer Science, Oregon State University; Piotr Sankowski: Institute of Informatics, University of Warsaw and Department of Computer and System Science, Sapienza University of Rome; Christian Wulff-Nilsen: Department of Computer Science, University of Copenhagen

  48. Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate
    Authors: Venkatesan Guruswami (Carnegie Mellon University) Adam Smith (Pennsylvania State University)

  49. Polynomial Learning of Distribution Families
    Mikhail Belkin (Ohio State University) and Kaushik Sinha (Ohio State University)

  50. Overcoming the Hole in the Bucket: Public-Key Cryptography Resilient to Continual Memory Leakage
    Authors: Zvika Brakerski and Yael Tauman Kalai and Jonathan Katz and Vinod Vaikuntanathan

  51. Sequential Rationality in Cryptographic Protocols
    Authors: Ronen Gradwohl, Kellogg School of Management, Northwestern University; Noam Livne, Weizmann Institute of Science; Alon Rosen, Herzliya IDC

  52. Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures
    Authors: Chandra Chekuri Dept. of Computer Science, Univ. of Illinois; Jan Vondrak IBM Almaden Research Center; Rico Zenklusen Dept. of Mathematics, MIT;

  53. From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits
    Authors: Nitin Saxena, Hausdorff Center for Mathematics, Bonn; C. Seshadhri, IBM Almaden

  54. The Geometry of Scheduling
    Authors: Nikhil Bansal (IBM Research) and Kirk Pruhs (Univ. of Pittsburgh)

  55. Stability yields a PTAS for k-Median and k-Means Clustering
    Authors: Pranjal Awasthi and Avrim Blum and Or Sheffet, Carnegie Mellon University

  56. Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability
    Authors:Konstantin Makarychev (IBM Research) and Yury Makarychev (TTIC).

  57. Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
    Authors: Alexandr Andoni (Princeton University & Center for Computational Intractability) Robert Krauthgamer (Weizmann Institute) Krzysztof Onak (Massachusetts Institute of Technology)

  58. Fast approximation algorithms for flow and cut-based problems in undirected graphs
    Author: Aleksander Madry, MIT

  59. Efficient volume sampling for row/column subset selection
    Amit Deshpande, Microsoft Research India and Luis Rademacher, Computer Science and Engineering, Ohio State University

  60. Estimating the longest increasing sequence in polylogarithmic time
    Authors: Michael Saks, Rutgers University and C. Seshadhri, IBM Almaden

  61. The Monotone Complexity of k-Clique on Random Graphs
    Author: Benjamin Rossman, MIT

  62. Frugal and Truthful Auctions for Vertex Covers, Flows, and Cuts
    Authors: David Kempe and Mahyar Salek and Cristopher Moore

  63. The Coin Problem, and Pseudorandomness for Branching Programs
    Authors: Joshua Brody and Elad Verbin

  64. Agnostically learning under permutation invariant distributions
    Author: Karl Wimmer (Duquesne University)

  65. Approximating Maximum Weight Matching in Near-linear Time
    Ran Duan, University of Michigan and Seth Pettie, University of Michigan

  66. Bounded Independence Fools Degree-2 Threshold Functions
    Authors: Ilias Diakonikolas (Columbia), Daniel M. Kane (Harvard), Jelani Nelson (MIT)

  67. Boosting and Differential Privacy
    Authors: Cynthia Dwork (Microsoft Research), Guy Rothblum (Princeton University), Salil Vadhan (Harvard University

  68. Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability
    Author: Rahul Santhanam, University of Edinburgh

  69. Lower Bounds for Near Neighbor Search via Metric Expansion
    Authors: Rina Panigrahy (Microsoft Research Silicon Valley), Kunal Talwar (Microsoft Research Silicon Valley), Udi Wieder (Microsoft Research Silicon Valley)

  70. Black-Box Randomized Reductions in Algorithmic Mechanism Design
    Authors: Shaddin Dughmi and Tim Roughgarden (Stanford University)

  71. Pure and Bayes-Nash Price of Anarchy for Generalized Second Price Auction
    Authors: Renato Paes Leme and Eva Tardos (Cornell)

  72. Learning Convex Concepts from Gaussian Distributions with PCA
    Authors: Santosh Vempala (Georgia Tech)

  73. Sublinear Optimization for Machine Learning
    Authors: Kenneth L. Clarkson and Elad Hazan and David P. Woodruff (IBM Almaden Research Center)

  74. The Limits of Two-Party Differential Privacy Authors: Andrew McGregor (University of Massachusetts, Amherst) Ilya Mironov (Microsoft Research Silicon Valley) Toniann Pitassi (University of Toronto) Omer Reingold (Microsoft Research Silicon Valley) Kunal Talwar (Microsoft Research Silicon Valley) Salil Vadhan (Harvard)

  75. Distance Oracles Beyond the Thorup-Zwick Bound
    Authors: Mihai Patrascu - AT&T Labs; Liam Roditty - Bar Ilan University

  76. A Multiplicative Weights Mechanism for Interactive Privacy-Preserving Data Analysis
    Authors: Moritz Hardt (Princeton University); Guy Rothblum (Princeton University)

  77. Subexponential Algorithms for Unique Games and Related problems
    Authors: Sanjeev Arora: Princeton University and Center for Computational Intractability; Boaz Barak: Microsoft Research and Princeton University; David Steurer: Princeton University and Center for Computational Intractability.

  78. Budget Feasible Mechanisms
    Author: Yaron Singer, UC Berkeley

  79. Black-Box, Round-Efficient Secure Computation via Non-Malleability Amplification
    Hoeteck Wee (Queens College, CUNY)

  80. On the Computational Complexity of Coin Flipping
    Authors: Hemanta K. Maji (UIUC) Manoj Prabhakaran (UIUC) Amit Sahai (UCLA)

  81. Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions
    Authors: Ran Canetti, Huijia Lin, and Rafael Pass.