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
(Hall 8) 

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
(on your own) 

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 (on your own) 

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) 
