STOC 2019 Program  
Workshops and Tutorials Day: Sunday June 23  
8:15  Continental Breakfast (Meeting Room Foyers)  
Location: West 212C  Location: West 213A  Location: West 213B  
9:0012:30  Workshop: Data Science through a Geometric Lens  Tutorial: Nash Welfare, Stable Equilibrium and Stable Polynomials  Tutorial: New Frontiers of Automated Mechanism Design for Pricing and Auctions  
12:3014:00  Lunch (West 301)  
14:0017:00  Tutorial: Recent Advances in High Dimensional Robust Statistics  Workshop: TCS Women  Workshop: New Frontiers of Automated Mechanism Design for Pricing and Auctions  
17:1518:30  Turing Award Lecture: Geoffrey Hinton and Yann LeCun (Symphony Hall)  
18:4521:00  STOC Reception (West Foyer 301)  
Day 1: Monday June 24  
8:15  Continental Breakfast (Meeting Room Foyers)  
Session 1 North 226 Chair: Moses Charikar 

9:00 
LogConcave
Polynomials II: HighDimensional Walks and an FPRAS for Counting Bases of a
Matroid Nima Anari (Stanford University), Kuikui Liu (University of Washington), Shayan Oveis Gharan (University of Washington), Cynthia Vinzant (North Carolina State University) 

9:20  Oracle
Separation of BQP and PH Ran Raz (Princeton University), Avishay Tal (Stanford University) 

9:40 
The
Reachability Problem for Petri Nets is Not Elementary Wojciech Czerwinski (University of Warsaw), Slawomir Lasota (University of Warsaw), Ranko Lazic (University of Warwick), Jerome Leroux (CNRS and University of Bordeaux), Filip Mazowiecki (University of Bordeaux) 

10:00 
Bootstrapping
Results for Threshold Circuits Just Beyond Known Lower Bounds Lijie Chen (MIT), Roei Tell (Weizmann Institute of Science) 

10:20 
The
LogApproximateRank Conjecture is False Arkadev Chattopadhyay (School of Technology and Computer Science), Nikhil Mande (School of Technology and Computer Science), Suhail Sherif (School of Technology and Computer Science) 

10:40 
A
Strongly Polynomial Algorithm for Linear Exchange Markets Jugal Garg (University of Illinois at UrbanaChampaign), László A. Végh (London School of Economics and Political Science) 

11:00  Coffee Break (Foyer)  
11:20  FCRC Plenary Talk: James E. Smith (Symphony Hall)  
12:30  Lunch (West 301)/ TCS Women Luncheon+Panel (West 106AB)  
Parallel Sessions 2  
Session
2A (North 226): Discrete Optimization Chair: Aviad Rubinstein 
Session 2B (North 225A):
Planar Graph Algorithms Chair: Ilya Razenshteyn 
Session 2C (North 225B):
Quantum Computing I Chair: Dana Moshkovitz 

14:00 
An
Optimal Approximation for Submodular Maximization under a Matroid Constraint
in the Adaptive Complexity Model Eric Balkanski (Harvard University), Aviad Rubinstein (Stanford University), Yaron Singer (Harvard University) Parallelizing greedy for submodular set function maximization in matroids and beyond Chandra Chekuri (UIUC), Kent Quanrud (UIUC) Submodular Maximization with Matroid and Packing Constraints in Parallel Alina Ene (Boston University), Huy L. Nguyen (Northeastern University), Adrian Vladu (Boston University) 
Almost
Optimal Distance Oracles for Planar Graphs Panagiotis Charalampopoulos (King's College), Paweł Gawrychowski (University of Wroclaw), Shay Mozes (IDC Herzliya), Oren Weimann (University of Haifa) 
The
Parallel Repetition of NonSignaling Games: Counterexamples and
Dichotomy Justin Holmgren (Princeton University), Lisa Yang (MIT) 

14:20 
Unconstrained
Submodular Maximization with Constant Adaptive Complexity Lin Chen (Yale University), Moran Feldman (Open University of Israel), Amin Karbasi (Yale University) 
Planar
Diameter via Metric Compression Jason Li (CMU), Merav Parter (Weizmann Institute) 
Quantum
singular value transformation and beyond: exponential improvements for
quantum matrix arithmetics András Gilyén (QuSoft), Yuan Su (QuICS), Guang Hao Low (QuArC), Nathan Wiebe (QuArC) 

14:40 
Dynamic
Set Cover: Improved Algorithms & Lower Bounds Amir Abboud (IBM Almaden Research Center), Raghavendra Addanki (University of Massachusetts Amherst), Fabrizio Grandoni (IDSIA), Debmalya Panigrahi (Duke University), Barna Saha (University of Massachusetts Amherst) 
Polylogarithmic
approximation for Euler genus on bounded degree graphs Kenichi Kawarabayashi (National Institute of Informatics), Anastasios Sidiropoulos (University of Illinois at Chicago) 
Quantum
Weak Coin Flipping Atul Singh Arora (Université libre de Bruxelles), Jérémie Roland (Université libre de Bruxelles), Stephan Weis (Universidade de Coimbra) 

15:00 
Approximation
Algorithms for Minimum Norm and Ordered Optimization Problems Deeparnab Chakrabarty (Dartmouth College), Chaitanya Swamy (University of Waterloo) 
Planar
Graphs of Bounded Degree have Bounded Queue Number Michael Bekos (University of Tübingen), Henry Förster (University of Tübingen), Martin Gronemann (University of Cologne), Tamara Mchedlidze (Karlsruhe Institute of Technology), Fabrizio Montecchiani (University of Perugia), Chrysanthi Raftopoulou (National Technical University of Athens), Torsten Ueckerdt (Karlsruhe Institute of Technology) 
A
quantuminspired classical algorithm for recommendation systems Ewin Tang (University of Texas at Austin) 

15:20  Poster Session I + Coffee Break (West 301CD)  
Parallel Sessions 3  
Session
3A (North 226): Graph Algorithms I Chair: Amir Abboud 
Session
3B (North 225A): Streaming Chair: Barna Saha 
Session
3C (North 225B): Privacy Chair: Kunal Talwar 

17:00 
The
Number of Minimum kCuts: Improving the KargerStein Bound Anupam Gupta (CMU), Euiwoong Lee (NYU), Jason Li (CMU) 
Polynomial
Pass Lower bounds for Graph Streaming Algorithms Sepehr Assadi (Princeton University), Yu Chen (University of Pennsylvania), Sanjeev Khanna (University of Pennsylvania) 
Private
Selection from Private Candidates Jingcheng Liu (UC Berkeley), Kunal Talwar (Google Brain) 

17:20 
Breaking
Quadratic Time for Small Vertex Connectivity and an Approximation
Scheme Danupon Nanongkai (KTH Royal Institute of Technology), Thatchaphol Saranurak (Toyota Technological Institute at Chicago), Sorrachai Yingchareonthawornchai (Michigan State University) 
An
Optimal Space Lower Bound for Approximating MAXCUT Michael Kapralov (EPFL), Dmitry Krachun (University of Geneva) 
The
Structure of Optimal Private Tests for Simple Hypotheses Clement Canonne (Stanford University), Gautam Kamath (Simons Institute for the Theory of Computing), Audra McMillan (Boston University and Northeastern University), Adam Smith (Boston University), Jonathan Ullman (Northeastern University) 

17:40 
O(log^{2}k/loglog
k)Approximation Algorithm for Directed Steiner Tree: A Tight
QuasiPolynomialTime Algorithm. Fabrizio Grandoni (IDSIA), Bundit Laekhanukit (Shanghai University of Finance and Economics), Shi Li (University at Buffalo) 
Stronger
L_{2}/L_{2} Compressed Sensing; Without Iterating Vasileios Nakos (Harvard University), Zhao Song (UTAustin) 
Gentle
Measurement of Quantum States and Differential Privacy Scott Aaronson (University of Texas at Austin), Guy Rothblum (Weizmann Institute of Science) 

18:00  Dinner (on your own)  
20:0022:00  STOC Business Meeting (North 226)  
To follow  Wikipedia editathon (West 104A)  
Day 2: Tuesday June 25  
8:15  Continental Breakfast (Meeting Room Foyers)  
Parallel Sessions 4  
Session
4A (North 226): Graph Algorithms II (Distributed/Dynamic) Chair: Fabrizio Grandoni 
Session
4B (North 225A): Complexity Theory I (circuits) Chair: Dana Moshkovitz 
Session
4C (North 225B): Quantum Computing II Chair: Scott Aaronson 
Session
4D North 231ABC: COLT sister session 

9:00 
Distributed
Exact Weighted AllPairs Shortest Paths in NearLinear Time Aaron Bernstein (Rutgers University), Danupon Nanongkai (KTH Royal Institute of Technology) 
NearOptimal
Lower Bounds on the Threshold Degree and SignRank of AC^{0} Alexander A. Sherstov (UCLA), Pei Wu (UCLA) 
Quantum
Lovász Local Lemma: Shearer's Bound is Tight Kun He (ICT), Qian Li (Alibaba Group), Xiaoming Sun (ICT), Jiapeng Zhang (University of California) 
See COLT Program 
9:20 
Distributed
Edge Connectivity in Sublinear Time Mohit Daga (KTH Royal Institute of Technology), Monika Henzinger (University of Vienna), Danupon Nanongkai (KTH Royal Institute of Technology), Thatchaphol Saranurak (Toyota Technological Institute) 
Reconstruction
of nondegenerate homogeneous depth three circuits Neeraj Kayal (Microsoft Research India), Chandan Saha (Indian Institute of Science) 
Quantum
proof systems for iterated exponential time, and beyond Joseph Fitzsimons (Singapore University of Technology and Design), Zhengfeng Ji (University of Technology Sydney), Thomas Vidick (CalTech), Henry Yuen (University of Toronto) 
See COLT Program 
9:40 
Towards
the Locality of Vizing's Theorem HsinHao Su (Boston College), Hoa T. Vu (Boston College) 
Separating
Monotone VP and VNP Amir Yehudayoff (TechnionIIT) 
Good
approximate quantum LDPC codes from spacetime circuit Hamiltonians Thomas C. Bohdanowicz (California Institute of Technology), Elizabeth Crosson (University of New Mexico), Chinmay Nirkhe (University of California), Henry Yuen (University of Toronto) 
See COLT Program 
10:00 
Decremental
StronglyConnected Components and SingleSource Reachability in NearLinear
Time Aaron Bernstein (Rutgers University), Maximilian Probst (University of Copenhagen), Christian WulffNilsen (University of Copenhagen) 
On
the Approximation Resistance of Balanced Linear Threshold Functions Aaron Potechin (University of Chicago) 
Hamiltonian
simulation with nearly optimal dependence on spectral norm Guang Hao Low (Microsoft Research) 
See COLT Program 
10:20 
Dynamic
LowStretch Trees via Dynamic LowDiameter Decompositions Sebastian Forster (University of Salzburg), Gramoz Goranci (University of Vienna) 
A
FixedDepth SizeHierarchy Theorem for AC^{0}[⊕] via the Coin
Problem Nutan Limaye (IIT Bombay), Karteek Sreenivasaiah (IIT Hyderabad), Srikanth Srinivasan (IIT Bombay), Utkarsh Tripathi (IIT Bombay), S. Venkitesh (IIT Bombay) 
Quantum
state certification Costin Bădescu (Carnegie Mellon University), Ryan O'Donnell (Carnegie Mellon University), John Wright (Massachusetts Institute of Technology) 
See COLT Program 
10:40 
A
New Algorithm for Decremental SingleSource Shortest Paths with Applications
to VertexCapacitated Flow and Cut Problems Julia Chuzhoy (Toyota Technological Institute at Chicago), Sanjeev Khanna (University of Pennsylvania) 
DNF
sparsification beyond sunflowers Shachar Lovett (UC San Diego), Jiapeng Zhang (UC San Diego) 
Exponential
separation between shallow quantum circuits and unbounded fanin shallow
classical circuits Adam Bene Watts (Massachusetts Institute of Technology), Robin Kothari (Microsoft Research), Luke Schaeffer (Massachusetts Institute of Technology), Avishay Tal (Stanford University) 
See COLT Program 
11:00  Coffee Break (Foyer)  
11:20  FCRC Plenary Talk: Cynthia Dwork (Symphony Hall)  
12:30  Lunch (West 301)  
Parallel Sessions 5  
Session
5A (North 226): Property Testing Chair: Sofya Raskhodnikova 
Session
5B (North 225A): Constraint Satisfaction Chair: Amir Abboud 
Session
5C (North 225B): Pseudorandomness/ Algorithmic Game Theory Chair: Inbal Talgam Cohen 

14:00 
Testing
Graphs in VertexDistributionFree Models Oded Goldreich (Weizmann Institute of Science) 
Bridging
between 0/1 and Linear Programming via Random Walks Joshua Brakensiek (Stanford University), Venkatesan Guruswami (Carnegie Mellon University) 
Fooling
Polytopes Ryan O'Donnell (Carnegie Mellon University), Rocco A. Servedio (Columbia University), LiYang Tan (Stanford University) 

14:20 
Testing
Graphs against an Unknown Distribution Lior Gishboliner (Tel Aviv University), Asaf Shapira (Tel Aviv University) 
Faster
kSAT algorithms using biasedPPSZ Thomas Dueholm Hansen (University of Copenhagen), Haim Kaplan (Tel Aviv University), Or Zamir (Tel Aviv University), Uri Zwick (Tel Aviv University) 
Pseudorandom
Generators for Width3 Branching Programs Raghu Meka (UCLA), Omer Reingold (Stanford University), Avishay Tal (Stanford University) 

14:40 
Testing
Unateness Nearly Optimally Xi Chen (Columbia University), Erik Waingarten (Columbia University) 
CSPs
with Global Modular Constraints: Algorithms and Hardness via Polynomial
Representations Joshua Brakensiek (Stanford University), Sivakanth Gopi (Microsoft Research), Venkatesan Guruswami (Carnegie Mellon University) 
The
Complexity of Splitting Necklaces and Bisecting Ham Sandwiches Aris FilosRatsikas (Ecole Polytechnique Federale de Lausanne), Paul W. Goldberg (University of Oxford) 

15:00 
Random
walks and forbidden minors II: a poly(d ε^{1})query tester for
minorclosed properties of bounded degree graphs Akash Kumar (Purdue University), C. Seshadhri (University of California), Andrew Stolman (University of California) 
Algebraic
approach to promise constraint satisfaction Jakub Bulín (Charles University), Andrei Krokhin (University of Durham), Jakub Opršal (University of Durham) 
The
Communication Complexity of Local Search Yakov Babichenko (Technion), Shahar Dobzinski (Weizmann Institute), Noam Nisan (Hebrew University of Jerusalem) 

15:20  Coffee Break (Foyer)  
Parallel Sessions 6  
Session 6A (North 226):
EC joint session Chair: Michal Feldman 
Session
6B (North 225A): Stringology Chair: Barna Saha 
Session 6C (North 225B):
Algorithmic Statistics Chair: Aviad Rubinstein 

16:00 
Settling
the Sample Complexity of Singleparameter Revenue Maximization Chenghao Guo (IIIS), Zhiyi Huang (University of Hong Kong), Xinzhi Zhang (IIIS) 
NearLinear
Time InsertionDeletion Codes and (1+ε)Approximating Edit
Distance via Indexing Bernhard Haeupler (Carnegie Mellon University), Aviad Rubinstein (Stanford University), Amirbehshad Shahrasbi (Carnegie Mellon University) 
Approximation
Algorithms for DistributionallyRobust Stochastic Optimization with BlackBox
Distributions Andre Linhares (University of Waterloo), Chaitanya Swamy (University of Waterloo) 

16:20  EC paper: Sample Complexity for NonTruthful Mechanisms Samuel Taggart and Jason Hartline 
1+ε
Approximation of Tree Edit Distance in Quadratic Time Mahdi Boroujeni (Sharif University of Technology), Mohammad Ghodsi (Sharif University of Technology & IPM), MohammadTaghi HajiAghayi (University of Maryland), Saeed Seddighin (University of Maryland) 
Efficient
Profile Maximum Likelihood for Universal Symmetric Property Estimation Moses Charikar (Stanford University), Kirankumar Shiragur (Stanford University), Aaron Sidford (Stanford University) 

16:40 
Tight
Approximation Ratio of Anonymous Pricing Yaonan Jin (Hong Kong University of Science and Technology), Pinyan Lu (Shanghai University of Finance and Economics), Qi Qi (Hong Kong University of Science and Technology), Zhihao Gavin Tang (University of Hong Kong), Tao Xiao (Shanghai Jiao Tong University) 
Optimal
Sequence Length Requirements for Phylogenetic Tree Reconstruction with
Indels Arun Ganesh (UC Berkeley), Qiuyi (Richard) Zhang (UC Berkeley) 
Communication
Complexity of Estimating Correlations Uri Hadar (Tel Aviv University), Jingbo Liu (MIT), Yury Polyanskiy (MIT), Ofer Shayevitz (Tel Aviv University) 

17:00  EC paper: Smoothed Analysis of MultiItem Auctions with Correlated Values ChristosAlexandros Psomas, Ariel Schvartzman and S. Matthew Weinberg 
Computing
Quartet Distance is Equivalent to Counting 4Cycles Bartłomiej Dudek (University of Wrocław), Paweł Gawrychowski (University of Wrocław) 
Degreed
Chow Parameters Robustly Determine Degreed PTFs (and Algorithmic
Applications) Ilias Diakonikolas (USC), Daniel Kane (UCSD) 

17:20 
Optimal
(and BenchmarkOptimal) Competition Complexity for Additive Buyers over
Independent Items Hedyeh Beyhaghi (Cornell University), S. Matthew Weinberg (Princeton University) 
Local
Decodability of the BurrowsWheeler Transform Sandip Sinha (Columbia University), Omri Weinstein (Columbia University) 
Capacity
lower bound for the Ising perceptron Jian Ding (University of Pennsylvania), Nike Sun (Massachusetts Institute of Technology) 

17:40  EC paper: The Vickrey Auction with a Single Duplicate Bidder Approximates the Optimal Revenue Hu Fu, Christopher Liaw and Sikander Randhawa 
String
Synchronizing Sets: SublinearTime BWT Construction and Optimal LCE Data
Structure Dominik Kempa (University of Warwick), Tomasz Kociumaka (University of Warsaw and BarIlan University) 
Learning
Restricted Boltzmann Machines via Influence Maximization Guy Bresler (MIT), Frederic Koehler (MIT), Ankur Moitra (MIT) 

18:15  Knuth Prize Lecture: Avi Wigderson (North 226) Optimization, Complexity and Math (or, can we prove P!=NP by gradient descent?) 

19:15  Dinner (on your own)  
Day 3: Wednesday June 26  
8:15  Continental Breakfast (Meeting Room Foyers)  
Parallel Sessions 7  
Session 7A (North 226):
COLT sister session Foundations of ML Chair: Vitaly Feldman 
Session 7B (North 225A):
Matrix Methods Chair: Inbal Talgam Cohen 
Session 7C (North 225B):
Lower Bounds/Metric Algs Chair: Aviad Rubinstein 

9:00 
NonGaussian
Component Analysis using Entropy Methods Navin Goyal (Microsoft Research India), Abhishek Shetty (Microsoft Research India) 
Flows
in Almost Linear Time via Adaptive Preconditioning Rasmus Kyng (Harvard), Richard Peng (Georgia Tech), Sushant Sachdeva (University of Toronto), Di Wang (Georgia Tech) 
Static
Data Structure Lower Bounds Imply Rigidity Zeev Dvir (Princeton University), Alexander Golovnev (Harvard University), Omri Weinstein (Columbia University) 

9:20 
Private
PAC learning implies finite Littlestone Dimension Noga Alon (Princeton University), Roi Livni (Tel Aviv University), Maryanthe Malliaris (Chicago University), Shay Moran (Princeton University) 
Fully
Dynamic Spectral Vertex Sparsifiers and Applications David Durfee (Georgia Tech), Yu Gao (Georgia Tech), Gramoz Goranci (University of Vienna), Richard Peng (Georgia Tech) 
An
Exponential Lower Bound on the SubPacketization of MSR Codes Omar Alrabiah (Carnegie Mellon University), Venkatesan Guruswami (Carnegie Mellon University) 

9:40 
Competitively
Chasing Convex Bodies Sebastien Bubeck (Microsoft Research), Yin Tat Lee (University of Washington), Yuanzhi Li (Stanford University), Mark Sellke (Stanford University) 
Spectral
Methods from Tensor Networks Ankur Moitra (MIT), Alexander S. Wein (Courant Institute) 
Why
ExtensionBased Proofs Fail Dan Alistarh (IST Austria), James Aspnes (Yale University), Faith Ellen (University of Toronto), Rati Gelashvili (University of Toronto), Leqi Zhu (University of Toronto) 

10:00 
Beyond
the LowDegree Algorithm: Mixtures of Subcubes and Their Applications Sitan Chen (MIT), Ankur Moitra (MIT) 
Solving
Linear Programs in the Current Matrix Multiplication Time Michael Cohen (MIT), Yin Tat Lee (University of Washington), Zhao Song (University of Washington & UTAustin) 
Lower Bounds for External Memory Integer Sorting via Network Coding Alireza Farhadi (University of Maryland), MohammadTaghi Hajiaghayi (University of Maryland), Kasper Green Larsen (Aarhus University), Elaine Shi (Cornell University) 

10:20 
Regression
from Dependent Observations Constantinos Daskalakis (MIT), Nishanth Dikkala (MIT), Ioannis Panageas (SUTD) 
Approximating
APSP without Scaling: Equivalence of Approximate MinPlus and Exact
MinMax Karl Bringmann (Max Planck Institute for Informatics), Marvin Kunnemann (Max Planck Institute for Informatics), Karol Wegrzycki (University of Warsaw) 
Algorithmic
PirogovSinai Theory Tyler Helmuth (University of Bristol), Will Perkins (University of Illinois at Chicago), Guus Regts (University of Amsterdam) 

10:40 
MemorySample
Tradeoffs for Linear Regression with Small Error Vatsal Sharan (Stanford University), Aaron Sidford (Stanford University), Gregory Valiant (Stanford University) 
Optimal
Succinct Rank Data Structure via Approximate Nonnegative Tensor
Decomposition Huacheng Yu (Harvard University) 
On
Approximating the Covering Radius and Finding Dense Lattice Subspaces Daniel Dadush (CWI) 

11:00  Coffee Break (Foyer)  
11:20  FCRC Plenary Talk: Shriram Krishnamurthi (Symphony Hall)  
12:30  Lunch (West 301)  
Parallel Sessions 8  
Session
8A (North 226): ML foundations II Chair: Ilya Razenshteyn 
Session
8B (North 225A): Cryptography Chair: Amos Fiat 
Session
8C (North 225B): Algorithms Chair: Edith Cohen 

14:00 
Performance
of JohnsonLindenstrauss Transform for kMeans and kMedians Clustering Konstantin Makarychev (Northwestern University), Yury Makarychev (TTIC), Ilya Razenshteyn (Microsoft Research) Oblivious Dimension Reduction for kMeans  Beyond Subspaces and the JohnsonLindenstrauss Lemma Luca Becchetti (Sapienza), Marc Bury (Zalando SE), Vincent CohenAddad (CNRS), Fabrizio Grandoni (IDSIA), Chris Schwiegelshohn (Sapienza) 
FiatShamir:
From Practice to Theory Ran Canetti (BU), Yilei Chen (Visa Research), Justin Holmgren (Princeton), Alex Lombardi (MIT), Guy N. Rothblum (Weizmann Institute of Science), Ron D. Rothblum (Technion), Daniel Wichs (Northeastern) 
On
a generalization of iterated and randomized rounding Nikhil Bansal (CWI and TU Eindhoven) 

14:20 
A
Universal Sampling Method for Reconstructing Signals with Simple Fourier
Transforms Haim Avron (Tel Aviv University), Michael Kapralov (École Polytechnique Fédérale de Lausanne), Cameron Musco (Microsoft Research), Christopher Musco (Princeton University), Ameya Velingker (École Polytechnique Fédérale de Lausanne), Amir Zandieh (École Polytechnique Fédérale de Lausanne) 
Weak
ZeroKnowledge Beyond the BlackBox Barrier Nir Bitansky (TAU), Dakshita Khurana (MSR), Omer Paneth (MIT) 
The
Online kTaxi Problem Christian Coester (University of Oxford), Elias Koutsoupias (University of Oxford) 

14:40 
Optimal
terminal dimensionality reduction in Euclidean space Shyam Narayanan (Harvard University), Jelani Nelson (Harvard University) 
Finding
a Nash Equilibrium is No Easier than Breaking FiatShamir Arka Rai Choudhuri (Johns Hopkins University), Pavel Hubacek (Charles University), Chethan Kamath (IST Austria), Krzysztof Pietrzak (IST Austria), Alon Rosen (IDC Herzliya), Guy N. Rothblum (Weizmann Institute of Science) 
Achieving
Optimal Backlog in MultiProcessor Cup Games Michael A. Bender (Stony Brook University), Martin FarachColton (Rutgers University), William Kuszmaul (Massachusetts Institute of Technology) 

15:00 
Dynamic
Sampling from Graphical Models Weiming Feng (Nanjing University), Nisheeth K. Vishnoi (Yale University), Yitong Yin (Nanjing University) 
How
to Delegate Computations Publicly Yael Tauman Kalai (Microsoft Research), Omer Paneth (MIT), Lisa Yang (MIT) 
Planar point
sets determine many pairwise crossing segments János Pach (EPFL), Natan Rubin (BenGurion University), Gábor Tardos (Renyi Institute) 

15:20  Poster Session II + Coffee Break (West 301CD)  
Parallel Sessions 9  
Session 9A (North 226):
Graph Algorithms II Chair: Amir Abboud 
Session 9B (North 225A):
Complexity Theory II Chair: Avishay Tal 
Session 9C (North 225B):
Graph Canonization Chair: Ilya Razenshteyn 

17:00 
Graph
pattern detection: Hardness for all induced patterns and faster noninduced
cycles Mina Dalirrooyfard (MIT), Thuy Duong Vuong (MIT), Virginia Vassilevska Williams (MIT) 
SylvesterGallai
type theorems for quadratic polynomials Amir Shpilka (TelAviv University) 
Canonical
form for graphs in quasipolynomial time Laszlo Babai (University of Chicago) 

17:20 
New
Polynomial Delay Bounds for Maximal Subgraph Enumeration by Proximity
Search Alessio Conte (National Institute of Informatics), Takeaki Uno (National Institute of Informatics) 
Weak
Lower Bounds on ResourceBounded Compression Imply Strong Separations of
Complexity Classes Dylan McKay (Massachusetts Institute of Technology), Cody Murray (Simons Institute), Ryan Williams (Massachusetts Institute of Technology) 
A
unifying method for the design of algorithms canonizing combinatorial
objects Pascal Schweitzer (TU Kaiserslautern), Daniel Wiebking (RWTH Aachen University) 

17:40 
Explicit
Nvertex graphs with maximum
degree K and diameter [1+o(1)]log_{K1} N for each K1 a prime
power Michael Capalbo (CCS) 
Meanfield
approximation, convex hierarchies, and the optimality of correlation
rounding: a unified perspective Vishesh Jain (MIT), Frederic Koehler (MIT), Andrej Risteski (MIT) 

18:00  END  