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 
Hölder
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) 
