Accepted Papers.

1. Time Hierarchies for Sampling Distributions
   Thomas Watson (UC Berkeley)
2. Learning Mixtures of Spherical Gaussians: Moment Methods and Spectral Decompositions
   Daniel Hsu (Microsoft Research) and Sham M. Kakade (Microsoft Research)
3. Low-Weight Halfspaces for Sparse Boolean Vectors
   Philip M. Long (NEC Labs) and Rocco A. Servedio (Columbia)
4. Learning and Incentives in User-Generated Content: Multi-Armed Bandits with Endogenous Arms
   Arpita Ghosh (Cornell) and Patrick Hummel (Google Inc.)
5. Adversary Lower Bound for the k-sum Problem
   Aleksandrs Belovs (University of Latvia) and Robert Špalek (Google, Inc.)
6. Space-Bounded Communication Complexity
   Joshua Brody (Aarhus), Shiteng Chen (Tsinghua), Periklis Papakonstantinou (Tsinghua), Hao Song, (Tsinghua), and Xiaoming Sun (Chinese Academy of Sciences)
7. Runtime Guarantees for Regression Problems
   Hui Han Chin (CMU), Aleksander Mądry (EPFL), Gary Miller (CMU), and Richard Peng (CMU)
8. Instance-Sensitive Robustness Guarantees for Sequencing with Unknown Packing and Covering Constraints
   Nicole Megow (TU Berlin) and Julián Mestre (University of Sydney)
9. On the Possibilities and Limitations of Pseudodeterministic Algorithms
   Oded Goldreich (Weizmann Institute), Shafi Goldwasser (MIT and Weizmann Institute) , and Dana Ron (Tel-Aviv University)
10. H-wise Independence
    Ishay Haviv (Academic College of Tel Aviv-Yaffo) and Michael Langberg (Open University of Israel)
11. Is Privacy Compatible with Truthfulness?
    David Xiao (LIAFA, CNRS, Université Paris 7)
12. Parametric Digital Auctions
    Pablo Daniel Azar (MIT) and Silvio Micali (MIT)
13. Active Self-Assembly of Algorithmic Shapes and Patterns in Polylogarithmic Time
    Damien Woods (Caltech), Ho-Lin Chen (National Taiwan University), Scott Goodfriend (Caltech), Nadine Dabby (Caltech), Erik Winfree (Caltech), and Peng Yin (Harvard Medical School)
14. Massive Online Teaching to Bounded Learners
    Brendan Juba (Harvard) and Ryan Williams (Stanford)
15. Sparse Extractor Families for All the Entropy
    Andrej Bogdanov (Chinese University of Hong Kong) and Siyao Guo (Chinese University of Hong Kong)
16. On the Power of Conditional Samples in Distribution Testing
    Sourav Chakraborty (Chennai Mathematical Institute), Eldar Fischer (Technion), Yonatan Goldhirsh (Technion), and Arie Matsliah (IBM Haifa Research Labs and Technion)
17. New Affine-Invariant Codes from Lifting
    Alan Guo (MIT), Swastik Kopparty (Rutgers), and Madhu Sudan (Microsoft Research)
18. Barriers in Cryptography with Weak, Correlated and Leaky Sources
    Daniel Wichs (IBM Research)
19. A Characterization of Approximation Resistance for Even k-Partite CSPs
    Per Austrin (Aalto University and KTH Stockholm) and Subhash Khot (NYU and University of Chicago)
20. Reachability in Graph Timelines
    Jakub Łącki (University of Warsaw) and Piotr Sankowski (University of Warsaw)
21. Evasiveness Through Circuit Lens
    Raghav Kulkarni (Center for Quantum Technologies, Singapore)
22. Competing Provers Protocols for Circuit Evaluation
    Gillat Kol (Weizmann Institute) and Ran Raz (Weizmann Institute)
23. Fast Reductions from RAMs to Delegatable Succinct Constraint Satisfaction Problems
    Eli Ben-Sasson (Technion and MIT), Alessandro Chiesa (MIT), Daniel Genkin (Technion), and Eran Tromer (Tel Aviv University)
24. Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete
    Hirotada Kobayashi (National Institute of Informatics), Francois Le Gall (The University of Tokyo), and Harumichi Nishimura (Nagoya University)
25. Characterizing the Sample Complexity of Private Learners
    Amos Beimel (Ben-Gurion University), Kobbi Nissim (Ben-Gurion University and Harvard), and Uri Stemmer (Ben-Gurion University)
26. Pseudo-partitions, Transversality and Locality: A Combinatorial Characterization for the Space Measure in Algebraic Proof Systems
    Ilario Bonacina (Università di Roma La Sapienza) and Nicola Galesi (Università di Roma La Sapienza)
27. On the Power of Many One-Bit Provers
    Per Austrin (Aalto University and KTH Stockholm), Johan Håstad (KTH Stockholm), and Rafael Pass (Cornell)
28. Resource-based Corruptions and the Combinatorics of Hidden Diversity
    Juan Garay (AT&T Labs -- Research), David Johnson (AT&T Labs -- Research), Aggelos Kiayias (University of Athens), and Moti Yung (Google Inc.)
29. The Garden-Hose Model
    Harry Buhrman (CWI and University of Amsterdam), Serge Fehr (CWI), Christian Schaffner (University of Amsterdam and CWI), and Florian Speelman (CWI and University of Amsterdam)
30. Sorting Noisy Data with Partial Information
    Konstantin Makarychev (Microsoft Research), Yury Makarychev, (TTI-Chicago), and Aravindan Vijayaraghavan (CMU)
31. Approaching Utopia: Strong Truthfulness and Externality-Resistant Mechanisms
    Amos Fiat (Tel Aviv University), Anna Karlin (University of Washington), Elias Koutsoupias (University of Oxford and University of Athens), and Angelina Vidali (Duke)
32. Towards An Optimal Query Efficient PCP?
    Subhash Khot (NYU and University of Chicago), Muli Safra (Tel Aviv University), and Madhur Tulsiani (TTI-Chicago)
33. Welfare Maximization and the Supermodular Degree
    Uriel Feige (Weizmann Institute) and Rani Izsak (Weizmann Institute)
34. Robust Optimization in the Presence of Uncertainty
    Joachim M. Buhmann (ETH Zurich), Matúš Mihalák (ETH Zurich), Rastislav Šrámek (ETH Zurich), and Peter Widmayer (ETH Zurich)
35. Learnability of DNF with Representation-Specific Queries
    Liu Yang (CMU), Avrim Blum (CMW), and Jaime Carbonell (CMU)
36. Catch Them If You Can: How to Serve Impatient Users
    Marek Cygan (University of Warsaw), Matthias Englert (University of Warwick), Anupam Gupta (CMU), Marcin Mucha (University of Warsaw), and Piotr Sankowski (University of Warsaw)
37. Noninteractive Timestamping and Publicly Verifiable Proofs of Work
    Mohammad Mahmoody (Cornell), Tal Moran (IDC Herzliya), and Salil Vadhan (Harvard)
38. On the Optimality of Relaxations for Average-Case and Generalized Constraint Satisfaction Problems
    Boaz Barak (Microsoft Research), Guy Kindler (Hebrew University), and David Steurer (Cornell)
39. Differentially Private Analysis of Social Networks via Restricted Sensitivity
    Jeremiah Blocki (CMU), Avrim Blum (CMU), Anupam Datta (CMU), and Or Sheffet (CMU)
40. An Energy Complexity Model for Algorithms
    Swapnoneel Roy (University at Buffalo), Atri Rudra (University at Buffalo), and Akshat Verma (IBM Research)
41. An Equational Approach to Secure Multi-Party Computation
    Daniele Micciancio (UC San Diego) and Stefano Tessaro (MIT)
42. Multiplicative Updates in Coordination Games and the Theory of Evolution
    Erick Chastain (Rutgers), Adi Livnat (Virginia Tech), Christos Papadimitriou (UC Berkeley), and Umesh Vazirani (UC Berkeley)
43. Can Theories Be Tested? A Cryptographic Treatment of Forecast Testing
    Kai-Min Chung (Cornell), Edward Lui (Cornell), and Rafael Pass (Cornell)
44. On the Convergence of the Hegselmann-Krause System
    Arnab Bhattacharyya (DIMACS), Mark Braverman (Princeton), Bernard Chazelle (Princeton and Collège de France), and Huy L. Nguyen (Princeton)
45. Streaming Computations With a Loquacious Prover
    Hartmut Klauck (Center for Quantum Technologies, Singapore) and Ved Prakash (Center for Quantum Technologies, Singapore)
46. Properties and Applications of Boolean Function Composition
    Avishay Tal (Weizmann Institute)
47. Making Evolution Rigorous - The Error Threshold
    Nisheeth K. Vishnoi (Microsoft Research)
48. A Classical Leash for a Quantum System: Command of Quantum Systems Via Rigidity of CHSH Games
    Ben Reichardt (USC), Falk Unger (Knight Capital Group), and Umesh Vazirani (UC Berkeley)
49. On the Power of Nonuniformity in Proofs of Security
    Kai-Min Chung (Cornell), Huijia Lin (MIT and Boston University), Mohammad Mahmoody (Cornell), and Rafael Pass (Cornell)