List of Accepted Papers

• Separating multilinear branching programs and formulas
  Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff


• $2^{log^{1-\epsilon} n}$ Hardness for Closest Vector Problem with Preprocessing
  Subhash Khot, Preyas Popat, Nisheeth Vishnoi


• Determinism versus Nondeterminism with Arithmetic Tests and Computation
  Miklos Ajtai


• Short Proofs for the Determinant Identities
  Pavel Hrubes, Iddo Tzameret


• The Cell Probe Complexity of Dynamic Range Counting
  Kasper Green Larsen


• Subspace Evasive Sets
  Zeev Dvir, Shachar Lovett


• Monotone expansion
  Jean Bourgain, Amir Yehudayoff


• Solution of the propeller conjecture in $R^3$
  Steven Heilman, Aukosh Jagannath, Assaf Naor


• Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds
  Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf


• On Vertex Sparsifiers with Steiner Nodes
  Julia Chuzhoy


• Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives
  Laszlo A. Vegh


• Routing in Undirected Graphs with Constant Congestion
  Julia Chuzhoy


• Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions
  Benny Applebaum


• Catching the k-NAESAT threshold
  Amin Coja-Oghlan, Konstantinos Panagiotou


• Edge Transitive Ramanujan Graphs and Highly Symmetric LDPC Good Codes
  Tali Kaufman, Alexander Lubotzky


• A quantitative Gibbard-Satterthwaite theorem without neutrality
  Elchanan Mossel, Miklos Z. Racz


• From Irreducible Representations to Locally Decodable Codes
  Klim Efremenko


• Reconstruction of Depth-4 Multlinear circuits with Top Fan-in 2
  Ankit Gupta, Neeraj Kayal, Satya Lokam


• Approximation Algorithms and Hardness of Integral Concurrent Flow
  Parinya Chalermsook, Julia Chuzhoy, Alina Ene, Shi Li


• Interactive Information Complexity
  Mark Braverman


• Finding red balloons with split contracts: robustness to individuals' selfishness
  Manuel Cebrian, Lorenzo Coviello, Andrea Vattani, Panagiotis Voulgaris


• Span Programs for Functions with Constant-Sized 1-certificates
  Aleksandrs Belovs


• Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
  Paul Beame, Chris Beck, Russell Impagliazzo


• Fast Matrix Rank Algorithms and Applications
  Ho Yee Cheung, Tsz Chiu Kwok, Lap Chi Lau


• Nearly Complete Graphs Decomposable into Large Induced Matchings and their Applications
  Noga Alon, Ankur Moitra, Benny Sudakov


• When the Cut Condition is Enough; A Complete Characterization for Multiflow Problems in Series-Parallel Networks
  Amit Chakrabarti, Lisa Fleisher, Christophe Weibel


• Approximating the Exponential, the Lancoz Method and an $\tilde{O}(m)$-Time Spectral Algorithm for Balanced Separator
  Lorenzo Orecchia, Sushant Sachdeva, Nisheeth Vishnoi


• Tight Bounds for Monotone Switching Networks via Fourier Analysis
  Siu Man Chan, Aaron Potechin


• Tight Bounds for Distributed Functional Monitoring
  David P. Woodruff, Qin Zhang


• Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance
  Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, Petar Maymounkov


• Folded Codes from Function Field Towers and Improved List Decoding
  Venkatesan Guruswami, Chaoping Xing


• Improved Smoothed Analysis of Multiobjective Optimization
  Tobias Brunsch, Heiko Roglin


• Improving Chrisofides' Algorithm for the s-t Path TSP
  Hyung-Chan An, Robert Kleinberg, David B. Shmoys


• Probabilistic existence of rigid combinatorial structures
  Greg Kuperberg, Shachar Lovett, Ron Peled


• Quantum Money from Hidden Subspaces
  Scott Aaronson, Paul Christiano


• A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities
  Jugal Garg, Ruta Mehta, Milind Sohoni, Vijay V. Vazirani


• Making Polynomials Robust to Noise
  Alexander A. Sherstov


• Online matching with concave returns
  Nikhil R. Devanur, Kamal Jain


• Learning Poisson Binomial Distributions
  Constantinos Daskalakis, Ilias Diakonikolas, Rocco Servedio


• Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
  Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola


• Polyhedral Clinching Auctions and the Adwords Polytope
  Gagan Goel, Vahab Mirrokni, Renato Paes Leme


• Complexity of Counting CSP with Complex Weights
  Jin-Yi Cai, Xi Chen


• Beating Randomized Response on Incoherent Matrices
  Moritz Hardt, Aaron Roth


• The Multiparty Communication Complexity of Set Disjointness
  Alexander A. Sherstov


• Nearly Optimal Sparse Fourier Transform
  Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price


• Certifiable Quantum Dice -- Or, testable exponential randomness expansion
  Umesh Vazirani, Thomas Vidick


• Prior-Free Auctions with Ordered Bidders
  Stefano Leonardi, Tim Roughgarden


• Using Petal-Decompositions to Build a Low Stretch Spanning Tree
  Ittai Abraham, Ofer Neiman


• On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing
  Michael A. Forbes, Amir Shpilka


• The traveling salesman problem: low dimensionality implies a polynomial time approximation scheme
  Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer


• Competitive Contagion in Networks
  Sanjeev Goyal, Michael Kearns


• Jacobian hit circuits: Hitting sets, lower bounds for depth-D occur-k formulas and depth-3 transcendence degree-k circuits
  Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena


• A new point of NP-hardness for Unique Games
  Ryan O'Donnell, John Wright


• Approximation Algorithms for Semi-random Graph Partitioning Problems
  Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan


• Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
  Martin Grohe, Daniel Marx


• On the limits of black-box reductions in mechanism design
  Shuchi Chawla, Nicole Immorlica, Brendan Lucier


• Fully Dynamic Approximate Distance Oracles for Planar Graphs via Forbidden-Set Distance labels
  Ittai Abraham, Shiri Chechik, Cyril Gavoille


• Affine Projections of Polynomials
  Neeraj Kayal


• From Query Complexity to Computational Complexity
  Shahar Dobzinski, Jan Vondrak


• Multiparty Computation Secure Against Continual Memory Leakage
  Elette Boyle, Shafi Goldwasser, Abhishek Jain, Yael Tauman Kalai


• Multiway spectral partitioning and higher-order Cheeger inequalities
  Shayan Oveis Gharan, James R. Lee, Luca Trevisan


• Budget Feasible Mechanism Design: From Prior-Free to Bayesian
  Xiaohui Bei, Ning Chen, Nick Gravin, Pinyan Lu


• Nearly optimal solutions for the Chow Parameters Problem and low- weight approximation of halfspaces
  Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio


• The freezing threshold for k-colourings of a random graph
  Michael Molloy


• Tight lower bounds for the online labelling problem
  Jan Bulanek, Michal Koucky, Michael Saks


• Computing a Nonnegative Matrix Factorization - Provably
  Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra


• Many Sparse Cuts via Higher Eigenvalues
  Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh Vempala


• A Rigorous Analyis of One-Dimensional Schelling Segregation
  Christina Brandt, Nicole Immorlica, Gautam Kamath, Robert Kleinberg


• A Near-Linear Time $\eps$-Approximation Algorithm for Geometric Bipartite Matching
  R. Sharathkumar, Pankaj K. Agarwal


• Matroid Prophet Inequalities
  Robert Kleinberg, Matthew Weinberg


• Rational Proofs
  Pablo Azar, Silvio Micali


• Robust satisfiability of constraint satisfaction problems
  Libor Barto, Marcin Kozik


• On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption
  Adriana Lopez-Alt, Eran Tromer, Vinod Vaikuntanathan


• Polynomial Time Algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars
  Kousha Etessami, Alistair Stewart, Mihalis Yannakakis


• Unconditionally Differentially Private Mechanisms for Linear Queries
  Aditya Bhaskara, Daniel Dadush, Ravishankar Krishnaswamy, Kunal Talwar


• Multiplying Matrices Faster Than Coppersmith-Winograd
  Virginia Vassilevska Williams


• Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations
  Michel X. Goemans, Neil Olver, Thomas Rothvoss, Rico Zenklusen


• Minimax Option Pricing Meets Black-Scholes in the Limit
  Jacob Abernethy, Rafael Frongillo, Andre Wibisono


• Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions
  Salil Vadhan, Colin Jia Zheng


• Optimal Online Buffer Scheduling for Block Devices
  Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Raecke


• On the Virtue of Succinct Proofs: Amplifying Communication Complexity Hardness to Time-Space Trade-offs in Proof Complexity
  Trinh Huynh, Jacob Nordstrom


• Strict Fibonacci Heaps
  Gerth Stolting Brodal, George Lagogiannis, Robert E. Tarjan


• Design Extractors, Non-Malleable Condensers and Privacy Amplification
  Xin Li


• Optimal Private Halfspace Counting via Discrepancy
  S. Muthukrishnan, Aleksandar Nikolov


• Beyond Laplacians: Faster Approximations of Multicommodity Flow in Undirected Graphs Using Quadratically Coupled Electrical Flows
  Jonathan A. Kelner, Gary L. Miller, Richard Peng


• An Algorithmic Characterization of Multi-Dimensional Mechanisms
  Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg


• Tight Time-Space Tradeoff for Mutual Exclusion
  Nikhil Bansal, Vibhor Bhatt, Prasad Jayanti, Ranganath Kondapally


• Hypercontractivity, Sum-of-Squares Proofs, and their Applications
  Boaz Barak, Aram W. Harrow, Jonathan Kelner, David Steurer, Yuan Zhou


• Tight RMR Lower Bounds for Randomized Mutual Exclusion
  George Giakkoupis, Philipp Woelfel