

Saturday, October 6 

8:3018:00 
Workshops/Tutorials 




19:3021:30 
Reception At
the "patio" of the Jussieu campus, 4 place Jussieu 75005 Paris 

Main Program 

Asessions
and plenary sessions are held in the Lavoisier amphitheater. Bsessions
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:0009:20 
Balancing
Vectors in Any Norms 
A Short List of
Equalities Induces Large Sign Rank 

09:2509:45 
Metric Sublinear
Algorithms via Linear Sampling. 
Simple Optimal Hitting
Sets for SmallSuccess RL 

09:5010:10 
Approximating the
Permanent of a Random Matrix with Vanishing Mean 
Hardness Magnification
for Natural Problems 

10:1510:35 
LogConcave Polynomials,
Entropy, and a Deterministic Approximation Algorithm for Counting Bases of
Matroids 
Counting tcliques:
WorstCase to AverageCase Reductions and Direct Interactive Proof Systems 

10:3510:55 
Coffee Break 

Session 1.2.A chaired by
Piotr Sankowski 
Session 1.2.B chaired by
Gregory Valiant 

10:5511:15 
A Faster Isomorphism Test
for Graphs of Small Degree 
Delegating Computations
with (almost) Minimal Time and Space Overhead 

11:2011:40 
Graph Sketching Against
Adaptive Adversaries Applied to the Minimum Degree Algorithm 
Computational TwoParty
Correlation: A Dichotomy for KeyAgreement Protocols 

11:4512:05 
Faster Exact and
Approximate Algorithms for kCut 
PPPCompleteness with
Connections to Cryptography 

12:0514:00 
Lunch 

Session 1.3.A chaired by
Vincent CohenAddad 
Session 1.3.B chaired by
Nikhil Bansal 

14:0014:20 
Holder Homeomorphisms and
Approximate Nearest Neighbors 
MDS matrices over small
fields: A proof of the GMMDS conjecture 

14:2514:45 
NearOptimal Approximate
Decremental All Pairs Shortest Paths 
Deterministic Document
Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors 

14:5015:10 
Bloom Filters,
Adaptivity, and the Dictionary Problem 
Improved decoding of
Folded ReedSolomon and Multiplicity Codes 

15:1015:30 
Coffee Break 

Session 1.4.A chaired by
Amir Abboud 
Session 1.4.B chaired by
Nisheeth Vishnoi 

15:3015:50 
An Improved Bound for
Weak EpsilonNets in the Plane 
The complexity of
generalvalued CSPs seen from the other side 

Session 1.5 chaired by
Mikkel Thorup 

15:5516:15 
Nonblackbox Worstcase
to Averagecase Reductions within NP (best student paper) 

16:2016:40 
Classical Verification of
Quantum Computations (best
student paper and best paper) 


Hall 101 

16:4518:45 
Business Meeting 





Monday, October 8 

Session 2.1.A chaired by
Amir Abboud 
Session 2.1.B chaired by
Nikhil Bansal 

09:0009:20 
Contextual Search via
Intrinsic Volumes 
A Cryptographic Test of
Quantumness and Certifiable Randomness from a Single Quantum Device 
09:2509:45 
Towards Learning Sparsely
Used Dictionaries with Arbitrary Supports 
Classical Homomorphic
Encryption for Quantum Circuits 
09:5010:10 
Learning Sums of
Independent Random Variables with Sparse Collective Support 
Classical lower bounds
from quantum upper bounds 
10:1510:35 
Recharging Bandits 
Quantum algorithm for
simulating real time evolution of lattice Hamiltonians 
10:3510:55 
Coffee Break 

Session 2.2.A chaired by
Nisheeth Vishnoi 
Session 2.2.B chaired by
Nikhil Bansal 

10:5511:15 
Graph Sparsification,
Spectral Sketches, and Faster Resistance Computation, via Short Cycle
Decompositions 
NearOptimal
Communication Lower Bounds for Approximate Nash Equilibria 
11:2011:40 
A Matrix Chernoff Bound
for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few
Random Spanning Trees 
An Endtoend Argument in
Mechanism Design (Priorindependent Auctions for Budgeted Agents) 
11:4512:05 
Spectral Subspace
Sparsification 
The Sample Complexity of
UptoƐ MultiDimensional Revenue Maximization 
12:0514:00 
Lunch 

Session 2.3.A chaired by
Nisheeth Vishnoi 
Session 2.3.B chaired by
Amir Abboud 

14:0014:20 
Improved Online Algorithm
for Weighted Flow Time 
Deterministic
Factorization of Sparse Polynomials with Bounded Individual Degree 
14:2514:45 
Fusible HSTs and the
randomized kserver conjecture 
Testing Graph
Clusterability: Algorithms and Lower Bounds 
14:5015:10 
An ETHTight Exact
Algorithm for Euclidean TSP 
Finding forbidden minors
in sublinear time: an n^{1/2 + o(1)}query onesided tester for minor closed
properties 
15:1515:35 
0/1/all CSPs,
HalfIntegral Apath Packing, and LinearTime FPT Algorithms 
Privacy Amplification by
Iteration 
15:4016:00 
On subexponential
parameterized algorithms for Steiner Tree and Directed Subset TSP on planar
graphs 
Revealing network
structure, confidentially: Improved Rates for Nodeprivate Graphon Estimation 
16:0016:20 
Coffee Break 

Session 2.4.A chaired by
Ola Svensson 
Session 2.4.B chaired by
Alexandra Kolla 

16:2016:40 
Perfect L_{p }Sampling in a Data
Stream 
EPTAS for Max Clique on
Disks and Unit Balls 
16:4517:05 
The Sketching Complexity
of Graph and Hypergraph Counting 
Limits on All Known (and
Some Unknown) Approaches to Matrix Multiplication 
Session 2.5 chaired by
Mikkel Thorup 

17:1017:30 
Pseudorandom Sets in
Grassmann Graph have NearPerfect Expansion (best paper) 

Session 2.6 chaired by
Allan Borodin 

17:3518:35 
Knuth Prize Lecture: On the difficulty of approximating Boolean
MaxCSPs Johan HŒstad
(KTH) 






Tuesday, October 9, 2018 

Session 3.1.A chaired by
Vincent CohenAddad 
Session 3.1.B chaired by
Alexandra Kolla 

09:0009:20 
Dispersion for
DataDriven Algorithm Design, Online Learning, and Private Optimization 
Planar Graph Perfect
Matching is in NC 
09:2509:45 
Efficient Density
Evaluation for Smooth Kernels 
On Derandomizing Local
Distributed Algorithms 
09:5010:10 
Efficiently Learning
Mixtures of Mallows Models 
Parallel Graph
Connectivity in Log Diameter Rounds 
10:1510:35 
Efficient Statistics, in
High Dimensions, from Truncated Samples 
A Faster Distributed
SingleSource Shortest Paths Algorithm 
10:3510:55 
Coffee Break 

Session 3.2.A chaired by
Vincent CohenAddad 
Session 3.2.B chaired by
Alexandra Kolla 

10:5511:15 
1factorizations of
pseudorandom graphs 
Lowdegree testing for
quantum states, and a quantum entangled games PCP for QMA 
11:2011:40 
Sublinear algorithms for
local graph centrality estimation 
Constant overhead quantum
fault tolerance with quantum expander codes 
11:4512:05 
Efficient polynomialtime
approximation scheme for the genus of dense graphs 
Spatial Isolation Implies
Zero Knowledge Even in a Quantum World 
12:0514:00 
Lunch 

Session 3.3.A chaired by
Ola Svensson 
Session 3.3.B chaired by
Elette Boyle 

14:0014:20 
Beating the integrality
ratio for sttours in graphs 
NonMalleable Codes for
SmallDepth Circuits 
14:2514:45 
Constant Factor
Approximation Algorithm for Weighted Flow Time on a Single Machine in
Pseudopolynomial time 
Tighter Bounds on
MultiParty Coin Flipping via Augmented Weak Martingales and Differentially
Private Sampling 
14:5015:10 
Random Order Contention
Resolution Schemes 
Cryptographic Hashing
from Strong OneWay Functions (Or: OneWay Product Functions and their
Applications) 
15:1515:35 
Strong Coresets for
kMedian and Subspace Approximation: Goodbye Dimension 
Laconic Function Evaluation
and Applications 
15:4016:00 
ƐCoresets for Clustering
(with Outliers) in Doubling Metrics 
PanORAMa: Oblivious RAM
with Logarithmic Overhead 
16:0016:20 
Coffee Break 

Session 3.4.A chaired by
Ola Svensson 
Session 3.4.B chaired by Elette
Boyle 

16:2016:40 
Efficient algorithms for
tensor scaling, quantum marginals, and moment polytopes 
A NearOptimal
DepthHierarchy Theorem for SmallDepth Multilinear Circuits 
16:4517:05 
Solving Directed
Laplacian Systems in NearlyLinear Time through Sparse LU Factorizations 
Pseudorandom Generators
for ReadOnce Branching Programs, in any Order 
17:1017:30 
The diameter of the
fractional matching polytope and its hardness implications 
Indistinguishability by
adaptive procedures with advice, and lower bounds on hardness amplification
proofs 
17:3517:55 
Coordinate Methods for
Accelerating $\ell_\infty$
Regression and Faster Approximate Maximum Flow 
Near logconvexity of
measured heat in (discrete) time and consequences 
Session 3.5 chaired by
Mikkel Thorup 

18:0018:20 
Approximating Edit
Distance Within Constant Factor in Truly SubQuadratic Time (best paper) 
