Compressed .zip file of FOCS program and proceedings

Saturday, October 6



At the Institut Henri Poincaré, 11 rue Pierre et Marie Curie 75005 Paris





At the "patio" of the Jussieu campus, 4 place Jussieu 75005 Paris

Main Program

A-sessions and plenary sessions are held in the Lavoisier amphitheater.

B-sessions are held in Hall 101.

Sunday, October 7

Session 1.1.A chaired by Piotr Sankowski

Session 1.1.B chaired by Gregory Valiant


Balancing Vectors in Any Norms
Daniel Dadush (CWI); Aleksandar Nikolov (University of Toronto); Kunal Talwar (Google Brain); Nicole Tomczak-Jaegermann (University of Alberta)

A Short List of Equalities Induces Large Sign Rank
Arkadev Chattopadhyay, Nikhil Mande (TIFR, Mumbai)


Metric Sublinear Algorithms via Linear Sampling
Hossein Esfandiari, Michael Mitzenmacher (Harvard SEAS)

Simple Optimal Hitting Sets for Small-Success RL
William M. Hoza, David Zuckerman (University of Texas at Austin)


Approximating the Permanent of a Random Matrix with Vanishing Mean
Lior Eldar; Saeed Mehraban (MIT)

Hardness Magnification for Natural Problems
Igor Carboni Oliveira, Rahul Santhanam (University of Oxford)


Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids
Nima Anari (Stanford University); Shayan Oveis Gharan (University of Washington); Cynthia Vinzant (North Carolina State University)

Counting t-cliques: Worst-Case to Average-Case Reductions and Direct Interactive Proof Systems
Oded Goldreich, Guy N. Rothblum (Weizmann Institute of Science)


Coffee Break

Session 1.2.A chaired by Piotr Sankowski

Session 1.2.B chaired by Gregory Valiant


A Faster Isomorphism Test for Graphs of Small Degree
Martin Grohe, Daniel Neuen (RWTH Aachen University); Pascal Schweitzer (TU Kaiserslautern)

Delegating Computations with (almost) Minimal Time and Space Overhead
Justin Holmgren (MIT); Ron D. Rothblum (MIT and Northeastern University)


Graph Sketching Against Adaptive Adversaries Applied to the Minimum Degree Algorithm
Matthew Fahrbach (Georgia Tech); Gary L. Miller (Carnegie Mellon University); Richard Peng, Saurabh Sawlani (Georgia Tech); Junxing Wang (Carnegie Mellon University); Shen Chen Xu (Facebook)

Computational Two-Party Correlation: A Dichotomy for Key-Agreement Protocols
Iftach Haitner (Tel Aviv University); Ronen Shaltiel, Jad Silbak (University of Haifa); Kobbi Nissim (Georgetown University); Eran Omri (Ariel University)


Faster Exact and Approximate Algorithms for k-Cut
Anupam Gupta (Carnegie Mellon University); Euiwoong Lee (New York University); Jason Li (Carnegie Mellon University)

PPP-Completeness with Connections to Cryptography
Katerina Sotiraki, Manolis Zampetakis (MIT); Giorgos Zirdelis (Northeastern University)


Lunch (Hall 8)

Session 1.3.A chaired by Vincent Cohen-Addad

Session 1.3.B chaired by Nikhil Bansal


Hölder Homeomorphisms and Approximate Nearest Neighbors
Alexandr Andoni (Columbia University); Assaf Naor (Princeton University); Aleksandar Nikolov (University of Toronto); Ilya Razenshteyn (Microsoft Research Redmond); Erik Waingarten (Columbia University)

MDS matrices over small fields: A proof of the GM-MDS conjecture
Shachar Lovett (UC San Diego)


Near-Optimal Approximate Decremental All Pairs Shortest Paths
Shiri Chechik (Tel-Aviv University)

Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors
Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu (Johns Hopkins University)


Bloom Filters, Adaptivity, and the Dictionary Problem
Michael A. Bender (Stony Brook University); Martin Farach-Colton (Rutgers University); Mayank Goswami (Queens College, CUNY); Rob Johnson (VMware Research); Samuel McCauley (BARC and IT U. Copenhagen); Shikha Singh (Stony Brook University)

Improved decoding of Folded Reed-Solomon and Multiplicity Codes
Swastik Kopparty (Rutgers University); Noga Ron-Zewi (Haifa University); Shubhangi Saraf (Rutgers University); Mary Wootters (Stanford University)


Coffee Break

Session 1.4.A chaired by Amir Abboud

Session 1.4.B chaired by Nisheeth Vishnoi


An Improved Bound for Weak Epsilon-Nets in the Plane
Natan Rubin (Ben-Gurion University of The Negev)

The complexity of general-valued CSPs seen from the other side
Clement Carbonnel, Miguel Romero, Stanislav Zivny (University of Oxford)

Session 1.5 chaired by Mikkel Thorup


Non-black-box Worst-case to Average-case Reductions within NP (best student paper)
Shuichi Hirahara (The University of Tokyo)


Classical Verification of Quantum Computations (best student paper and best paper)
Urmila Mahadev (UC Berkeley)


Hall 101


Business Meeting




Monday, October 8

Session 2.1.A chaired by Amir Abboud

Session 2.1.B chaired by Nikhil Bansal


Contextual Search via Intrinsic Volumes
Renato Paes Leme (Google Research); Jon Schneider (Princeton University)

A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device
Zvika Brakerski (Weizmann Institute of Science); Paul Christiano (OpenAI); Urmila Mahadev, Umesh Vazirani (UC Berkeley); Thomas Vidick (California Institute of Technology)


Towards Learning Sparsely Used Dictionaries with Arbitrary Supports
Pranjal Awasthi (Rutgers University); Aravindan Vijayaraghavan (Northwestern University)

Classical Homomorphic Encryption for Quantum Circuits
Urmila Mahadev (UC Berkeley)


Learning Sums of Independent Random Variables with Sparse Collective Support
Anindya De (Northwestern University); Philip M. Long (Google); Rocco Servedio (Columbia University)

Classical lower bounds from quantum upper bounds
Shalev Ben-David (University of Maryland); Adam Bouland (University of California, Berkeley); Ankit Garg, Robin Kothari (Microsoft Research)


Recharging Bandits
Robert Kleinberg (Cornell University); Nicole Immorlica (Microsoft Research)

Quantum algorithm for simulating real time evolution of lattice Hamiltonians
Jeongwan Haah, Matthew B. Hastings, Robin Kothari, Guang Hao Low (Microsoft Research)


Coffee Break

Session 2.2.A chaired by Nisheeth Vishnoi

Session 2.2.B chaired by Nikhil Bansal


Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions
Timothy Chu (Carnegie Mellon); Yu Gao, Richard Peng (Georgia Tech); Sushant Sachdeva (University of Toronto); Saurabh Sawlani (Georgia Tech); Junxing Wang (Carnegie Mellon)

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
Mika Goos, Aviad Rubinstein (Harvard)


A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees
Rasmus Kyng (Harvard University); Zhao Song (Harvard University & UT-Austin)

An End-to-end Argument in Mechanism Design (Prior-independent Auctions for Budgeted Agents)
Yiding Feng, Jason D. Hartline (Northwestern University)


Spectral Subspace Sparsification
Huan Li (School of Computer Science, Fudan University); Aaron Schild (Electrical Engineering and Computer Science, University of California, Berkeley)

The Sample Complexity of Up-to-Ɛ Multi-Dimensional Revenue Maximization
Yannai A. Gonczarowski (Hebrew University of Jerusalem, Microsoft Research); S. Matthew Weinberg (Princeton University)


Lunch (on your own)

Session 2.3.A chaired by Nisheeth Vishnoi

Session 2.3.B chaired by Amir Abboud


Improved Online Algorithm for Weighted Flow Time
Yossi Azar, Noam Touitou (Tel Aviv University)

Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree
Vishwas Bhargava, Shubhangi Saraf (Rutgers University); Ilya Volkovich (University of Michigan)


Fusible HSTs and the randomized k-server conjecture
James R. Lee (University of Washington)

Testing Graph Clusterability: Algorithms and Lower Bounds
Ashish Chiplunkar, Michael Kapralov (EPFL); Sanjeev Khanna (University of Pennsylvania); Aida Mousavifar (EPFL); Yuval Peres (Microsoft Research Redmond)


An ETH-Tight Exact Algorithm for Euclidean TSP
Mark de Berg (Eindhoven University of Technology); Hans L. Bodlaender (Utrecht University and Eindhoven University of Technology); Sandor Kisfaludi-Bak, Sudeshna Kolay (Eindhoven University of Technology)

Finding forbidden minors in sublinear time: an n1/2 + o(1)-query one-sided tester for minor closed properties
Akash Kumar (Purdue University); C. Seshadhri, Andrew Stolman (University of California, Santa Cruz)


0/1/all CSPs, Half-Integral A-path Packing, and Linear-Time FPT Algorithms
Yoichi Iwata (National Institute of Informatics); Yutaro Yamaguchi (Osaka University); Yuichi Yoshida (National Institute of Informatics)

Privacy Amplification by Iteration
Vitaly Feldman, Ilya Mironov, Kunal Talwar (Google); Abhradeep Thakurta (UC Santa Cruz)


On subexponential parameterized algorithms for Steiner Tree and Directed Subset TSP on planar graphs
Dániel Marx (Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI), Hungary); Marcin Pilipczuk, Michal Pilipczuk (Institute of Informatics, University of Warsaw, Poland)

Revealing network structure, confidentially: Improved Rates for Node-private Graphon Estimation
Christian Borgs, Jennifer Chayes (Microsoft Research); Adam Smith (Boston University); Ilias Zadik (MIT)


Coffee Break

Session 2.4.A chaired by Ola Svensson

Session 2.4.B chaired by Alexandra Kolla


Perfect Lp Sampling in a Data Stream
Rajesh Jayaram, David P. Woodruff (Carnegie Mellon University)

EPTAS for Max Clique on Disks and Unit Balls
Marthe Bonamy (LaBRI, Universite de Bordeaux); Edouard Bonnet (ENS Lyon, LIP); Nicolas Bousquet (G-SCOP laboratory, Grenoble-INP); Pierre Charbit (Universite Paris Diderot, IRIF); Stephan Thomasse (ENS Lyon, LIP)


The Sketching Complexity of Graph and Hypergraph Counting
John Kallaugher (UT Austin); Michael Kapralov (EPFL); Eric Price (UT Austin)

Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
Josh Alman, Virginia Vassilevska Williams (MIT)

Session 2.5 chaired by Mikkel Thorup


Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion (best paper)
Subhash Khot (New York University); Dor Minzer, Muli Safra (Tel-Aviv University)

Session 2.6 chaired by Allan Borodin


Knuth Prize Lecture: On the difficulty of approximating Boolean Max-CSPs

Johan Håstad (KTH)






Tuesday, October 9, 2018

Session 3.1.A chaired by Vincent Cohen-Addad

Session 3.1.B chaired by Alexandra Kolla


Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization
Maria-Florina Balcan, Travis Dick, Ellen Vitercik (Carnegie Mellon University)

Planar Graph Perfect Matching is in NC
Nima Anari (Stanford University); Vijay V. Vazirani (University of California, Irvine)


Efficient Density Evaluation for Smooth Kernels
Arturs Backurs (MIT); Moses Charikar (Stanford University); Piotr Indyk (MIT); Paris Siminelakis (Stanford University)

On Derandomizing Local Distributed Algorithms
Mohsen Ghaffari (ETH Zurich); David Harris (University of Maryland); Fabian Kuhn (University of Freiburg)


Efficiently Learning Mixtures of Mallows Models
Allen Liu, Ankur Moitra (MIT)

Parallel Graph Connectivity in Log Diameter Rounds
Alexandr Andoni (Columbia University); Zhao Song (Harvard University & UT-Austin); Clifford Stein (Columbia University); Zhengyu Wang (Harvard University); Peilin Zhong (Columbia University)


Efficient Statistics, in High Dimensions, from Truncated Samples
Constantinos Daskalakis, Themis Gouleakis (MIT); Christos Tzamos (Microsoft Research); Manolis Zampetakis (MIT)

A Faster Distributed Single-Source Shortest Paths Algorithm
Sebastian Krinninger (University of Salzburg); Danupon Nanongkai (KTH Royal Institute of Technology)


Coffee Break

Session 3.2.A chaired by Vincent Cohen-Addad

Session 3.2.B chaired by Alexandra Kolla


1-factorizations of pseudorandom graphs
Asaf Ferber, Vishesh Jain (MIT)

Low-degree testing for quantum states, and a quantum entangled games PCP for QMA
Anand Natarajan (MIT); Thomas Vidick (Caltech)


Sublinear algorithms for local graph centrality estimation
Marco Bressan (Sapienza University of Rome); Enoch Peserico, Luca Pretto (University of Padova)

Constant overhead quantum fault tolerance with quantum expander codes
Omar Fawzi (ENS de Lyon); Antoine Grospellier, Anthony Leverrier (Inria)


Efficient polynomial-time approximation scheme for the genus of dense graphs
Yifan Jing, Bojan Mohar (Simon Fraser University)

Spatial Isolation Implies Zero Knowledge Even in a Quantum World
Alessandro Chiesa (UC Berkeley); Michael A. Forbes (University of Illinois at Urbana-Champaign); Tom Gur, Nicholas Spooner (UC Berkeley)


Lunch (on your own)

Session 3.3.A chaired by Ola Svensson

Session 3.3.B chaired by Elette Boyle


Beating the integrality ratio for s-t-tours in graphs
Vera Traub, Jens Vygen (University of Bonn)

Non-Malleable Codes for Small-Depth Circuits
Marshall Ball (Columbia University); Dana Dachman-Soled (University of Maryland); Siyao Guo (Northeastern University); Tal Malkin (Columbia University); Li-Yang Tan (Stanford University)


Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-polynomial time
Jatin Batra, Amit Kumar, Naveen Garg (IIT Delhi)

Tighter Bounds on Multi-Party Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling
Amos Beimel (Ben Gurion University); Iftach Haitner, Nikolaos Makriyannis (Tel Aviv University); Eran Omri (Ariel University)


Random Order Contention Resolution Schemes
Marek Adamczyk, Michal Wlodarczyk (University of Warsaw)

Cryptographic Hashing from Strong One-Way Functions (Or: One-Way Product Functions and their Applications)
Justin Holmgren, Alex Lombardi (MIT)


Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension
Christian Sohler (TU Dortmund); David P. Woodruff (CMU)

Laconic Function Evaluation and Applications
Willy Quach (Northeastern University); Hoeteck Wee (CNRS and ENS); Daniel Wichs (Northeastern University)


Ɛ-Coresets for Clustering (with Outliers) in Doubling Metrics
Lingxiao Huanjag (École polytechnique federale de Lausanne); Shaofeng H.-C. Jiang (The Weizmann Institute of Science); Jian Li, Xuan Wu (Tsinghua University)

PanORAMa: Oblivious RAM with Logarithmic Overhead
Sarvar Patel (Google); Giuseppe Persiano (Google and University of Salerno); Mariana Raykova (Google and Yale University); Kevin Yeo (Google)


Coffee Break

Session 3.4.A chaired by Ola Svensson

Session 3.4.B chaired by Elette Boyle


Efficient algorithms for tensor scaling, quantum marginals, and moment polytopes
Peter Burgisser (Technische Universitet Berlin); Cole Franks (Rutgers University); Ankit Garg (Microsoft Research New England); Rafael Oliveira (University of Toronto); Michael Walter (QuSoft, Korteweg-de Vries Institute for Mathematics, Institute of Physics, and Institute for Logic, Language and Computation, University of Amsterdam); Avi Wigderson (Institute for Advanced Study, Princeton)

A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits
Suryajith Chillara, Christian Engels, Nutan Limaye (Department of CSE, IIT Bombay); Srikanth Srinivasan (Department of Mathematics, IIT Bombay)


Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations
Michael B. Cohen, Jonathan Kelner (MIT); Rasmus Kyng (Yale University); John Peebles (MIT); Richard Peng (Georgia Tech); Anup Rao (Adobe Research); Aaron Sidford (Stanford University)

Pseudorandom Generators for Read-Once Branching Programs, in any Order
Michael A. Forbes, Zander Kelley (University of Illinois at Urbana-Champaign)


The diameter of the fractional matching polytope and its hardness implications
Laura Sanita (University of Waterloo)

Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs
Aryeh Grinberg, Ronen Shaltiel (University of Haifa); Emanuele Viola (Northeastern University)


Coordinate Methods for Accelerating $\ell_\infty$ Regression and Faster Approximate Maximum Flow
Aaron Sidford, Kevin Tian (Stanford University)

Near log-convexity of measured heat in (discrete) time and consequences
Mert Saglam (University of Washington)

Session 3.5 chaired by Mikkel Thorup


Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time (best paper)
Diptarka Chakraborty, Debarati Das (Computer Science Institute of Charles University, Prague); Elazar Goldenberg (The Academic College Of Tel Aviv-Yaffo, School of Computer Science, Tel Aviv-Yaffo); Michal Koucky (Computer Science Institute of Charles University, Prague); Michael Saks (Department of Mathematics, Rutgers University, NJ)