Accepted papers

Linear time decoding of regular expander codes
Authors: Michael Viderman

On the Degree of Univariate Polynomials Over the Integers
Authors: Gil Cohen, Amir Shpilka, and Avishay Tal

Crowdsourced Bayesian Auctions
Authors: Pablo Azar, Jing Chen, and Silvio Micali

Restriction Access
Authors: Zeev Dvir, Anup Rao, Avi Wigderson, and Amir Yehudayoff

Quantum Strategic Game Theory
Authors: Shengyu Zhang

Approximately Optimal Mechanism Design via Differential Privacy
Authors: Kobbi Nissim, Rann Smorodinsky, and Moshe Tennenholtz

Quantum interactive proofs with weak error bounds
Authors: Tsuyoshi Ito, Hirotada Kobayashi, and John Watrous

Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure
Authors: Bohua Zhan, Shelby Kimmel, and Avinatan Hassidim

No Justified Complaints: On Fair Sharing of Multiple Resources
Authors: Danny Dolev, Dror G. Feitelson, Joseph Y. Halpern, Raz Kupferman, and Nathan Linial

Compressed Matrix Multiplication
Authors: Rasmus Pagh

Mechanism Design with Approximate Valuations
Authors: Alessandro Chiesa, Silvio Micali, and Zeyuan Allen Zhu

Learning Hurdles for Sleeping Experts
Authors: Varun Kanade and Thomas Steinke

Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent
Authors: Maurice Jansen and Rahul Santhanam

On beating the hybrid argument
Authors: Bill Fefferman, Ronen Shaltiel, Christopher Umans, and Emanuele Viola

Dynamics of Prisoner's Dilemma and the Evolution of Cooperation on Networks
Authors: Vahideh H. Manshadi and Amin Saberi

Multicommodity Flows and Cuts in Polymatroidal Networks
Authors: Chandra Chekuri, Sreeram Kannan, Adnan Raja, and Pramod Viswanath

Fairness Through Awareness
Authors: Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel

Targeted Malleability: Homomorphic Encryption for Restricted Computations
Authors: Dan Boneh, Gil Segev, and Brent Waters

Noise vs computational intractability in dynamics
Authors: Mark Braverman, Alexander Grigo, and Cristobal Rojas

Practical Verified Computation with Streaming Interactive Proofs
Authors: Graham Cormode, Michael Mitzenmacher, and Justin Thaler

Sherali-Adams Relaxations and Indistinguishability in Counting Logics
Authors: Albert Atserias and Elitza Maneva

Bounds on Locally Testable Codes with Unique Tests
Authors: Gillat Kol and Ran Raz

Quantum money from knots
Authors: Eddie Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, and Peter Shor

Quantum rejection sampling
Authors: Maris Ozols, Martin Roetteler, and Jeremie Roland

The Curse of Simultaneity
Authors: Renato Paes Leme, Vasilis Syrgkanis, and Eva Tardos

Algorithms on Evolving Graphs
Authors: Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian, Eli Upfal, and Fabio Vandin

Gadgets and Anti-gadgets Leading to a Complexity Dichotomy
Authors: Jin-Yi Cai, Michael Kowalczyk, and Tyson Williams

Paging for Multi-core Shared Caches
Authors: Alejandro López-Ortiz and Alejandro Salinger

Graph Densification
Authors: Moritz Hardt, Nikhil Srivastava, and Madhur Tulsiani

Fully Homomorphic Encryption without Bootstrapping
Authors: Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan

Distribution Free Evolvability of Polynomial Functions over all Convex Loss Functions
Authors: Paul Valiant

Linear programming, width-1 CSPs, and robust satisfaction
Authors: Gabor Kun, Ryan O'Donnell, Suguru Tamaki, Yuichi Yoshida, and Yuan Zhou

List decoding subspace codes from insertions and deletions
Authors: Venkatesan Guruswami, Srivatsan Narayanan, and Carol Wang

On Persistent Homotopy, Knotted Complexes and the Alexander Module
Authors: David Letscher

Towards deterministic tree code constructions
Authors: Mark Braverman

Spectral sparsification via random spanners
Authors: Michael Kapralov and Rina Panigrahy

From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge, and Back Again
Authors: Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer

From Randomizing Polynomials to Parallel Algorithms
Authors: Yuval Ishai, Eyal Kushilevitz, and Anat Paskin-Cherniavsky

High-Confidence Predictions under Adversarial Uncertainty
Authors: Andrew Drucker