Program

FOCS'14 Proceedings Front Matter (foreword, program committee, awards, etc.)


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)

  • Sponsors

    • IEEE Computer Society Technical Committee on Mathematical Foundations of Computing
    • Microsoft Research
    • Bell Labs, Alcatel Lucent
    • DIMACS
    • National Science Foundation (NSF)