Saturday, October 6 |
|||
8:30-18:00
|
Workshops/Tutorials |
||
|
|
||
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 |
A Short List of
Equalities Induces Large Sign Rank |
|
09:25-09:45 |
Metric Sublinear
Algorithms via Linear Sampling |
Simple Optimal
Hitting Sets for Small-Success RL |
|
09:50-10:10 |
Approximating
the Permanent of a Random Matrix with Vanishing Mean |
Hardness
Magnification for Natural Problems |
|
10:15-10:35 |
Log-Concave
Polynomials, Entropy, and a Deterministic Approximation Algorithm for
Counting Bases of Matroids |
Counting
t-cliques: Worst-Case to Average-Case Reductions and Direct Interactive Proof
Systems |
|
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 |
Delegating
Computations with (almost) Minimal Time and Space Overhead |
|
11:20-11:40 |
Graph Sketching
Against Adaptive Adversaries Applied to the Minimum Degree Algorithm |
Computational
Two-Party Correlation: A Dichotomy for Key-Agreement Protocols |
|
11:45-12:05 |
Faster Exact and
Approximate Algorithms for k-Cut |
PPP-Completeness
with Connections to Cryptography |
|
12:05-14:00 |
Lunch |
||
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 |
MDS matrices
over small fields: A proof of the GM-MDS conjecture |
|
14:25-14:45 |
Near-Optimal
Approximate Decremental All Pairs Shortest Paths |
Deterministic
Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors |
|
14:50-15:10 |
Bloom Filters,
Adaptivity, and the Dictionary Problem |
Improved
decoding of Folded Reed-Solomon and Multiplicity Codes |
|
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 |
The complexity of
general-valued CSPs seen from the other side |
|
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) |
||
16:20-16:40 |
Classical
Verification of Quantum Computations (best student paper and
best paper) |
||
|
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 |
A Cryptographic
Test of Quantumness and Certifiable Randomness from a Single Quantum Device |
09:25-09:45 |
Towards Learning
Sparsely Used Dictionaries with Arbitrary Supports |
Classical
Homomorphic Encryption for Quantum Circuits |
09:50-10:10 |
Learning Sums of
Independent Random Variables with Sparse Collective Support |
Classical lower
bounds from quantum upper bounds |
10:15-10:35 |
Recharging Bandits |
Quantum
algorithm for simulating real time evolution of lattice Hamiltonians |
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 |
Near-Optimal
Communication Lower Bounds for Approximate Nash Equilibria |
11:20-11:40 |
A Matrix
Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers
from a few Random Spanning Trees |
An End-to-end
Argument in Mechanism Design (Prior-independent Auctions for Budgeted Agents) |
11:45-12:05 |
Spectral
Subspace Sparsification |
The Sample
Complexity of Up-to-Ɛ Multi-Dimensional Revenue Maximization |
12:05-14:00 |
Lunch |
|
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 |
Deterministic
Factorization of Sparse Polynomials with Bounded Individual Degree |
14:25-14:45 |
Fusible HSTs and
the randomized k-server conjecture |
Testing Graph
Clusterability: Algorithms and Lower Bounds |
14:50-15:10 |
An ETH-Tight
Exact Algorithm for Euclidean TSP |
Finding
forbidden minors in sublinear time: an n1/2 + o(1)-query
one-sided tester for minor closed properties |
15:15-15:35 |
0/1/all CSPs,
Half-Integral A-path Packing, and Linear-Time FPT Algorithms |
Privacy
Amplification by Iteration |
15:40-16:00 |
On
subexponential parameterized algorithms for Steiner Tree and Directed Subset
TSP on planar graphs |
Revealing
network structure, confidentially: Improved Rates for Node-private Graphon
Estimation |
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 Lp
Sampling in a Data Stream |
EPTAS for Max
Clique on Disks and Unit Balls |
16:45-17: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:10-17:30 |
Pseudorandom
Sets in Grassmann Graph have Near-Perfect Expansion (best paper) |
|
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 |
Planar Graph
Perfect Matching is in NC |
09:25-09:45 |
Efficient
Density Evaluation for Smooth Kernels |
On Derandomizing
Local Distributed Algorithms |
09:50-10:10 |
Efficiently
Learning Mixtures of Mallows Models |
Parallel Graph
Connectivity in Log Diameter Rounds |
10:15-10:35 |
Efficient
Statistics, in High Dimensions, from Truncated Samples |
A Faster
Distributed Single-Source Shortest Paths Algorithm |
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 |
Low-degree
testing for quantum states, and a quantum entangled games PCP for QMA |
11:20-11:40 |
Sublinear
algorithms for local graph centrality estimation |
Constant
overhead quantum fault tolerance with quantum expander codes |
11:45-12:05 |
Efficient
polynomial-time approximation scheme for the genus of dense graphs |
Spatial
Isolation Implies Zero Knowledge Even in a Quantum World |
12:05-14:00 |
Lunch |
|
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 |
Non-Malleable
Codes for Small-Depth Circuits |
14:25-14:45 |
Constant Factor
Approximation Algorithm for Weighted Flow Time on a Single Machine in
Pseudo-polynomial time |
Tighter Bounds
on Multi-Party Coin Flipping via Augmented Weak Martingales and
Differentially Private Sampling |
14:50-15:10 |
Random Order
Contention Resolution Schemes |
Cryptographic
Hashing from Strong One-Way Functions (Or: One-Way Product Functions and
their Applications) |
15:15-15:35 |
Strong Coresets
for k-Median and Subspace Approximation: Goodbye Dimension |
Laconic Function
Evaluation and Applications |
15:40-16:00 |
Ɛ-Coresets for Clustering (with Outliers) in
Doubling Metrics |
PanORAMa:
Oblivious RAM with Logarithmic Overhead |
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 |
A Near-Optimal
Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits |
16:45-17:05 |
Solving Directed
Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations |
Pseudorandom
Generators for Read-Once Branching Programs, in any Order |
17:10-17: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:35-17:55 |
Coordinate
Methods for Accelerating $\ell_\infty$ Regression and Faster
Approximate Maximum Flow |
Near
log-convexity of measured heat in (discrete) time and consequences |
Session 3.5 chaired by Mikkel Thorup |
||
18:00-18:20 |
Approximating
Edit Distance Within Constant Factor in Truly Sub-Quadratic Time (best paper) |
|