
Compressed .zip file of FOCS program and proceedings
Saturday, October 6
8:30-18:00		Workshops/Tutorials At the Institut Henri Poincaré, 11 rue Pierre et Marie Curie 75005 Paris

19:30-21:30		Reception 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
09:00-09:20	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)
09:25-09:45	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)
09:50-10:10	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)
10:15-10:35	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)
10:35-10:55	Coffee Break
	Session 1.2.A chaired by Piotr Sankowski		Session 1.2.B chaired by Gregory Valiant
10:55-11:15	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)
11:20-11:40	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)
11:45-12:05	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)
12:05-14:00	Lunch (Hall 8)
	Session 1.3.A chaired by Vincent Cohen-Addad		Session 1.3.B chaired by Nikhil Bansal
14:00-14:20	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)
14:25-14:45	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)
14:50-15:10	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)
15:10-15:30	Coffee Break
	Session 1.4.A chaired by Amir Abboud		Session 1.4.B chaired by Nisheeth Vishnoi
15:30-15:50	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
15:55-16:15	Non-black-box Worst-case to Average-case Reductions within NP (best student paper) Shuichi Hirahara (The University of Tokyo)
16:20-16:40	Classical Verification of Quantum Computations (best student paper and best paper) Urmila Mahadev (UC Berkeley)
	Hall 101
16:45-18:45	Business Meeting



Monday, October 8
	Session 2.1.A chaired by Amir Abboud	Session 2.1.B chaired by Nikhil Bansal
09:00-09:20	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)
09:25-09:45	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)
09:50-10:10	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)
10:15-10:35	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)
10:35-10:55	Coffee Break
	Session 2.2.A chaired by Nisheeth Vishnoi	Session 2.2.B chaired by Nikhil Bansal
10:55-11:15	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)
11:20-11:40	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)
11:45-12:05	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)
12:05-14:00	Lunch (on your own)
	Session 2.3.A chaired by Nisheeth Vishnoi	Session 2.3.B chaired by Amir Abboud
14:00-14:20	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)
14:25-14:45	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)
14:50-15:10	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 n^{1/2 + o(1)}-query one-sided tester for minor closed properties Akash Kumar (Purdue University); C. Seshadhri, Andrew Stolman (University of California, Santa Cruz)
15:15-15:35	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)
15:40-16:00	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)
16:00-16:20	Coffee Break
	Session 2.4.A chaired by Ola Svensson	Session 2.4.B chaired by Alexandra Kolla
16:20-16:40	*Perfect L_pSampling 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)
16:45-17:05	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
17:10-17:30	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
17:35-18:35	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
09:00-09:20	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)
09:25-09:45	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)
09:50-10:10	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)
10:15-10:35	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)
10:35-10:55	Coffee Break
	Session 3.2.A chaired by Vincent Cohen-Addad	Session 3.2.B chaired by Alexandra Kolla
10:55-11:15	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)
11:20-11:40	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)
11:45-12:05	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)
12:05-14:00	Lunch (on your own)
	Session 3.3.A chaired by Ola Svensson	Session 3.3.B chaired by Elette Boyle
14:00-14:20	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)
14:25-14:45	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)
14:50-15:10	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)
15:15-15:35	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)
15:40-16:00	*Ɛ-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)
16:00-16:20	Coffee Break
	Session 3.4.A chaired by Ola Svensson	Session 3.4.B chaired by Elette Boyle
16:20-16:40	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)
16:45-17:05	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)
17:10-17:30	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)
17:35-17:55	*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
18:00-18:20	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)