Please see the At a Glance page for more information about the schedule, including meals, and breaks. See also program in printable PDF format.
Note: Please note that we are not handing out USB drives with the proceedings at the conference. There will be web access to the papers.
| Session 1 Chair: Kunal Talwar Sunday 10/19, 9:00am-10:10am (Grand Ballroom) |
| 9:00-9:20 Threesomes, Degenerates, and Love Triangles |
| Allan Grønlund (MADALGO, Aarhus University) , Seth Pettie (University of Michigan) |
| 9:25-9:45 Constructive discrepancy minimization for convex sets |
| Thomas Rothvoss (University of Washington) |
| 9:50-10:10 Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(log n)^{\Omega(1)}}$ Colors |
| Subhash Khot (New York University) , Rishi Saket (IBM India Research Lab) |
| Session 2A Chair: Valerie King Sunday 10/19, 10:40am-12:15pm (Grand Ballroom) |
| 10:40-11:00 The Dyck Language Edit Distance Problem in Near-linear Time |
| Barna Saha (University of Massachusetts Amherst) |
| 11:05-11:25 Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs |
| Marcin Pilipczuk (Department of Informatics, University of Bergen, Norway) , Michał Pilipczuk (Department of Informatics, University of Bergen, Norway) , Piotr Sankowski (Institute of Informatics, University of Warsaw, Poland) , Erik Jan van Leeuwen (Max-Planck Institut für Informatik, Saarbrücken, Germany) |
| 11:30-11:50 Popular conjectures imply strong lower bounds for dynamic problems |
| Amir Abboud (Stanford University) , Virginia Vassilevska Williams (Stanford University) |
| 11:55-12:15 Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails |
| Karl Bringmann (Max Planck Institute for Informatics, Saarbrücken, Germany) |
| Session 2B Chair: Robert Kleinberg Sunday 10/19, 10:40am-12:15pm (Crystal Ballroom) |
| 10:40-11:00 ($2+\epsilon$)-SAT is NP-hard |
| Per Austrin (KTH Royal Institute of Technology) , Venkatesan Guruswami (Carnegie Mellon University) , Johan Håstad (KTH Royal Institute of Technology) |
| 11:05-11:25 Parallel Repetition From Fortification |
| Dana Moshkovitz (MIT) |
| 11:30-11:50 Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts |
| Radu Curticapean (Department of Computer Science, Saarland University, Saarbrücken, Germany) , Dániel Marx (Computer and Automation Research Institute, Hungarian Academy of Sciences (MTA SZTAKI), Budapest, Hungary) |
| 11:55-12:15 The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems (Extended Abstract) |
| Jin-Yi Cai (University of Wisconsin-Madison) , Heng Guo (University of Wisconsin-Madison) , Tyson Williams (University of Wisconsin-Madison) |
| Session 3A Chair: Aaron Roth Sunday 10/19, 2:15pm-3:25pm (Grand Ballroom) |
| 2:15-2:35 Achieving Target Equilibria in Network Routing Games without Knowing the Latency Functions |
| Umang Bhaskar (Caltech) , Katrina Ligett (Caltech, MC305-16, Pasadena, CA 91125, USA) , Leonard J. Schulman (Caltech, MC305-16, Pasadena, CA 91125, USA) , Chaitanya Swamy (Dept. of Combinatorics and Optimization, Univ. Waterloo, Waterloo, ON N2L 3G1, Canada) |
| 2:40-3:00 Barriers to Near-Optimal Equilibria |
| Tim Roughgarden (Stanford) |
| 3:05-3:25 A Counter-Example to Karlin’s Strong Conjecture for Fictitious Play |
| Constantinos Daskalakis (EECS, MIT) , Qinxuan Pan (EECS, MIT) |
| Session 3B Chair: Ankur Moitra Sunday 10/19, 2:15pm-3:25pm (Crystal Ballroom) |
| 2:15-2:35 Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time |
| Monika Henzinger (University of Vienna) , Sebastian Krinninger (University of Vienna) , Danupon Nanongkai (University of VIenna) |
| 2:40-3:00 Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search |
| Mihai Patrascu , Mikkel Thorup (University of Copenhagen) |
| 3:05-3:25 Generating k-independent variables in constant time |
| Tobias Christiani (IT University of Copenhagen) , Rasmus Pagh (IT University of Copenhagen) |
| Session 4A Chair: Robert Kleinberg Sunday 10/19, 3:55pm-5:05pm (Grand Ballroom) |
| 3:55-4:15 Ramanujan Complexes and bounded degree topological expanders |
| Tali Kaufman (Bar-Ilan University) , David Kazhdan (Hebrew University) , Alexander Lubotzky (Hebrew University) |
| 4:20-4:40 On the AC0 Complexity of Subgraph Isomorphism |
| Yuan Li (University of Chicago) , Alexander Razborov (University of Chicago) , Benjamin Rossman (National Institute of Informatics) |
| 4:45-5:05 Shrinkage of De Morgan Formulae by Spectral Techniques |
| Avishay Tal (Weizmann Institute) |
| Session 4B Chair: Scott Aaronson Sunday 10/19, 3:55pm-5:05pm (Crystal Ballroom) |
| 3:55-4:15 Local tests for global entanglement and a counterexample to the generalized area law |
| Dorit Aharonov (Hebrew University) , Aram Harrow (MIT) , Zeph Landau (UC Berkeley) , Daniel Nagaj (UC Berkeley) , Mario Szegedy (Rutgers) , Umesh Vazirani (UC Berkeley) |
| 4:20-4:40 Complexity classification of local Hamiltonian problems |
| Toby Cubitt (University of Cambridge) , Ashley Montanaro (University of Bristol) |
| Session 5 Chair: Julia Chuzhoy Sunday 10/19, 5:20pm-6:05pm (Grand Ballroom) |
| 5:20-5:40 LP-Based Algorithms for Capacitated Facility Location |
| Hyung-Chan An (School of Computer and Communication Sciences, EPFL) , Mohit Singh (Microsoft Research) , Ola Svensson (School of Computer and Communication Sciences, EPFL) |
| 5:45-6:05 List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise |
| Mark Braverman (Princeton University) , Klim Efremenko (University of Chicago) |
| Session 6 Chair: Ankur Moitra Monday 10/20, 9:00am-10:10am (Grand Ballroom) |
| 9:00-9:20 Exponential Separation of Information and Communication |
| Anat Ganor (Weizmann Institute) , Gillat Kol (IAS) , Ran Raz (Weizmann Institute & IAS) |
| 9:25-9:45 Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth |
| Daniel Lokshtanov (Department of Informatics, University of Bergen, Norway) , Marcin Pilipczuk (Department of Informatics, University of Bergen, Norway) , Michał Pilipczuk (Department of Informatics, University of Bergen, Norway) , Saket Saurabh (Institute of Mathematical Sciences, India, and Department of Informatics, University of Bergen, Norway) |
| 9:50-10:10 Chasing Ghosts: Competing with Stateful Policies |
| Uriel Feige (Weizmann Institute) , Tomer Koren (Technion) , Moshe Tennenholtz (Microsoft Research and Technion) |
| Session 7A Chair: Kunal Talwar Monday 10/20, 10:40am-12:15pm (Grand Ballroom) |
| 10:40-11:00 Sample-Optimal Fourier Sampling in Any Constant Dimension |
| Piotr Indyk (MIT) , Michael Kapralov (MIT) |
| 11:05-11:25 Spectral Approaches to Nearest Neighbor Search |
| Amirali Abdullah (University of Utah) , Alexandr Andoni (Microsoft Research) , Ravi Kannan (Microsoft Research) , Robert Krauthgamer (Weizmann Institute) |
| 11:30-11:50 Solving Optimization Problems with Diseconomies of Scale via Decoupling |
| Konstantin Makarychev (Microsoft Research) , Maxim Sviridenko (Yahoo! Labs) |
| 11:55-12:15 Settling the APX-hardness Status for Geometric Set Cover |
| Nabil H. Mustafa (ESIEE Paris, France) , Rajiv Raman (Indraprastha Institute of Information Technology (IIIT) Delhi, India.) , Saurabh Ray (Computer Science Department, New York University, Abu Dhabi, U.A.E.) |
| Session 7B Chair: Boaz Barak Monday 10/20, 10:40am-12:15pm (Crystal Ballroom) |
| 10:40-11:00 Outsourcing Private RAM Computation |
| Craig Gentry (IBM Research) , Shai Halevi (IBM Research) , Mariana Raykova (SRI) , Daniel Wichs (Northeastern University) |
| 11:05-11:25 One-Way Functions and (Im)perfect Obfuscation |
| Ilan Komargodski (Weizmann Institute) , Tal Moran (IDC) , Moni Naor (Weizmann Institute) , Rafael Pass (Cornell University) , Alon Rosen (IDC) , Eylon Yogev (Weizmann Institute) |
| 11:30-11:50 Non-Malleable Codes Against Constant Split-State Tampering |
| Eshan Chattopadhyay (University of Texas at Austin) , David Zuckerman (University of Texas at Austin) |
| 11:55-12:15 An Algebraic Approach to Non-Malleability |
| Vipul Goyal (Microsoft Research India) , Silas Richelson (UCLA) , Alon Rosen (IDC Herzliya) , Margarita Vald (Tel Aviv University) |
| Session 8A Chair: Aaron Roth Monday 10/20, 2:15pm-3:25pm (Grand Ballroom) |
| 2:15-2:35 On the Hardness of Signaling |
| Shaddin Dughmi (University of Southern California) |
| 2:40-3:00 Mechanism Design for Crowdsourcing: An Optimal 1-1/e Competitive Budget-Feasible Mechanism for Large Markets |
| Nima Anari (University of California, Berkeley) , Gagan Goel (Google Research) , Afshin Nikzad (Stanford University) |
| 3:05-3:25 A Simple and Approximately Optimal Mechanism for an Additive Buyer |
| Moshe Babaioff (Microsoft Research) , Nicole Immorlica (Microsoft Research) , Brendan Lucier (Microsoft Research) , S. Matthew Weinberg (MIT) |
| Session 8B Chair: Alexander Russell Monday 10/20, 2:15pm-3:25pm (Crystal Ballroom) |
| 2:15-2:35 Novel Polynomial Basis and Its Application to Reed-Solomon Erasure Codes |
| Sian-Jheng Lin (Research Center for Information Technology Innovation, Academia Sinica) , Wei-Ho Chung (Research Center for Information Technology Innovation, Academia Sinica) , Yunghsiang S. Han (Department of Electrical Engineering, National Taiwan University of Science and Technology) |
| 2:40-3:00 Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball |
| Itai Benjamini (Weizmann Institute) , Gil Cohen (Weizmann Institute) , Igor Shinkar (Weizmann Institute) |
| 3:05-3:25 Bounds on the permanent and some applications |
| Leonid Gurvits (The City College of New York) , Alex Samorodnitsky (The Hebrew University) |
| Session 9A Chair: Scott Aaronson Monday 10/20, 3:55pm-5:05pm (Grand Ballroom) |
| 3:55-4:15 Noisy Interactive Quantum Communication |
| Gilles Brassard (Université de Montréal, CIFAR and ETH-ITS) , Ashwin Nayak (University of Waterloo) , Alain Tapp (Université de Montréal) , Dave Touchette (Université de Montréal) , Falk Unger |
| 4:20-4:40 Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments |
| Francois Le Gall (The University of Tokyo) |
| 4:45-5:05 Quantum Attacks on Classical Proof Systems (The Hardness of Quantum Rewinding) |
| Andris Ambainis (University of Latvia and Institute for Advanced Study, Princeton) , Ansis Rosmanis (Institute for Quantum Computing, School of Computer Science, University of Waterloo) , Dominique Unruh (University of Tartu) |
| Session 9B Chair: Aaron Roth Monday 10/20, 3:55pm-5:05pm (Crystal Ballroom) |
| 3:55-4:15 Total space in resolution |
| Ilario Bonacina (Sapienza University of Rome) , Nicola Galesi (Sapienza University of Rome) , Neil Thapen (Academy of Sciences of the Czech Republic) |
| 4:20-4:40 Circuit Complexity, Proof Complexity, and Polynomial Identity Testing |
| Joshua A. Grochow (Santa Fe Institute) , Toniann Pitassi (University of Toronto, Department of Computer Science) |
| 4:45-5:05 Pre-Reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs |
| Parinya Chalermsook (Max-Planck-Institut fur Informatik) , Bundit Laekhanukit (McGill University & Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA)) , Danupon Nanongkai (University of Vienna) |
| Session K (Knuth Prize Lecture: The stories behind the results / Richard Lipton ) Chair: Boaz Barak Monday 10/20, 5:20pm-6:20pm (Grand Ballroom) |
| Session 10 Chair: Julia Chuzhoy Tuesday 10/21, 9:00am-10:10am (Grand Ballroom) |
| 9:00-9:20 Single Pass Spectral Sparsification in Dynamic Streams |
| Michael Kapralov (MIT) , Yin Tat Lee (MIT) , Cameron Musco (MIT) , Christopher Musco (MIT) , Aaron Sidford (MIT) |
| 9:25-9:45 On the power of homogeneous depth 4 arithmetic circuits |
| Mrinal Kumar (Rutgers University) , Shubhangi Saraf (Rutgers University) |
| 9:25-9:45 An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas (joint talk with above paper) |
| Neeraj Kayal (Microsoft Research India) , Nutan Limaye (Indian Institute of Technology Bombay) , Chandan Saha (Indian Institute of Science Bangalore) , Srikanth Srinivasan (Indian Institute of Technology Bombay) |
| 9:50-10:10 An Automatic Inequality Prover and Instance Optimal Identity Testing |
| Gregory Valiant (Stanford) , Paul Valiant (Brown University) |
| Session 11A Chair: Valerie King Tuesday 10/21, 10:30am-12:15pm (Grand Ballroom) |
| 10:30-10:50 Randomized Mutual Exclusion with Constant Amortized RMR Complexity on the DSM |
| George Giakkoupis (INRIA Rennes) , Philipp Woelfel (University of Calgary) |
| 10:55-11:05 Online bipartite matching in offline time |
| Bartlomiej Bosek (Jagiellonian University) , Dariusz Leniowski (University of Warsaw) , Piotr Sankowski (University of Warsaw) , Anna Zych (University of Warsaw) |
| 11:20-11:40 O( log log rank ) Competitive-Ratio for the Matroid Secretary Problem |
| Oded Lachish (Birkbeck, University of London) |
| 11:45-12:05 SelfishMigrate: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors |
| Sungjin Im (University of California at Merced) , Janardhan Kulkarni (Duke University) , Kamesh Munagala (Duke University) , Kirk Pruhs (University of Pittsburgh) |
| Session 11B Chair: Julia Chuzhoy Tuesday 10/21, 10:30am-12:15pm (Crystal Ballroom) |
| 10:30-10:50 On Learning and Testing Dynamic Environments |
| Oded Goldreich (Weizmann Institute) , Dana Ron (Tel-Aviv University) |
| 10:55-11:15 Preventing False Discovery in Interactive Data Analysis is Hard |
| Moritz Hardt (IBM Research Almaden) , Jonathan Ullman (Harvard University SEAS) |
| 11:20-11:40 Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds |
| Raef Bassily (Pennsylvania State University) , Adam Smith (Pennsylvania State University) , Abhradeep Thakurta (Yahoo! Labs) |
| 11:45-12:05 New algorithms and lower bounds for monotonicity testing |
| Xi Chen (Columbia University) , Rocco A. Servedio (Columbia University) , Li-Yang Tan (Columbia University) |
| Session 12A Chair: Scott Aaronson Tuesday 10/21, 2:05pm-3:40pm (Grand Ballroom) |
| 2:05-2:25 Satisfiability and Evolution |
| Adi Livnat (Virginia Tech) , Christos Papadimitriou (University of California at Berkeley) , Aviad Rubinstein (University of California at Berkeley) , Andrew Wan (Simons Institute, UC Berkeley) , Gregory Valiant (Stanford University) |
| 2:30-2:50 Random Walks that Find Perfect Objects and the Lovasz Local Lemma |
| Dimitris Achlioptas (University of California Santa Cruz and RACTI) , Fotis Iliopoulos (National Technical University of Athens) |
| 2:55-3:15 Digital morphogenesis via Schelling segregation |
| George Barmpalias (State Key Lab of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing and School of Mathematics, Statistics and Operations Research, Victoria University, Wellington, New Zealand) , Richard Elwes (Department of Mathematics, University of Leeds, UK) , Andy Lewis-Pye (Department of Mathematics, London School of Economics, UK) |
| 3:20-3:40 Understanding Alternating Minimization for Matrix Completion |
| Moritz Hardt (IBM Research Almaden) |
| Session 12B Chair: Alexander Russell Tuesday 10/21, 2:05pm-3:40pm (Crystal Ballroom) |
| 2:05-2:25 Interactive Channel Capacity Revisited |
| Bernhard Haeupler (Microsoft Research) |
| 2:30-2:50 Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding |
| Mohsen Ghaffari (MIT) , Bernhard Haeupler (Microsoft Research) |
| 2:55-3:15 Topology Matters in Communication |
| Arkadev Chattopadhyay (Tata Institute of Fundamental Research) , Jaikumar Radhakrishnan (Tata Institute of Fundamental Research) , Atri Rudra (University at Buffalo, SUNY) |
| 3:20-3:40 The Communication Complexity of Distributed $\epsilon$-Approximations |
| Zengfeng Huang (MADALGO, Aarhus University) , Ke Yi (HKUST) |
| Session 13 (Best paper) Chair: Boaz Barak Tuesday 10/21, 4:00pm-4:20pm (Grand Ballroom) |
| 4:00-4:20 , Path-Finding Methods for Linear Programming : Solving Linear Programs in $\tilde{O}(\sqrt{rank})$ Iterations and Faster Algorithms for Maximum Flow |
| Yin Tat Lee (MIT) , Aaron Sidford (MIT) |