|
|
| 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(logn)Ω(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+ϵ)-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: Moses Charikar
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 - 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: Moses Charikar
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 ϵ-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 O~(rank−−−−√) Iterations and Faster Algorithms for Maximum Flow
|
| Yin Tat Lee (MIT) , Aaron Sidford (MIT) |
|
|
|