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:00-12: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:30-14:00  Lunch (West 301)
14:00-17:00  Tutorial: Recent Advances in High Dimensional Robust Statistics Workshop: TCS Women Workshop: New Frontiers of Automated Mechanism Design for Pricing and Auctions
17:15-18:30  Turing Award Lecture: Geoffrey Hinton and Yann LeCun (Symphony Hall)
18:45-21: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 Log-Concave Polynomials II: High-Dimensional 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 Log-Approximate-Rank 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 Urbana-Champaign), 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 Non-Signaling 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
Ken-ichi 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 quantum-inspired 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):
Chair: Barna Saha
Session 3C (North 225B):
Chair: Kunal Talwar
17:00  The Number of Minimum k-Cuts: Improving the Karger-Stein 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 MAX-CUT
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(log2k/loglog k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm.
Fabrizio Grandoni (IDSIA), Bundit Laekhanukit (Shanghai University of Finance and Economics), Shi Li (University at Buffalo)
Stronger L2/L2 Compressed Sensing; Without Iterating
Vasileios Nakos (Harvard University), Zhao Song (UT-Austin)
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:00-22:00  STOC Business Meeting (North 226)
To follow  Wikipedia edit-a-thon (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 All-Pairs Shortest Paths in Near-Linear Time
Aaron Bernstein (Rutgers University), Danupon Nanongkai (KTH Royal Institute of Technology)
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC0
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)

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 non-degenerate 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)

9:40  Towards the Locality of Vizing's Theorem
Hsin-Hao Su (Boston College), Hoa T. Vu (Boston College)
Separating Monotone VP and VNP
Amir Yehudayoff (Technion-IIT)
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)

10:00  Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time
Aaron Bernstein (Rutgers University), Maximilian Probst (University of Copenhagen), Christian Wulff-Nilsen (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)

10:20  Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions
Sebastian Forster (University of Salzburg), Gramoz Goranci (University of Vienna)
A Fixed-Depth Size-Hierarchy Theorem for AC0[⊕] 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)

10:40  A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated 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 fan-in shallow classical circuits
Adam Bene Watts (Massachusetts Institute of Technology), Robin Kothari (Microsoft Research), Luke Schaeffer (Massachusetts Institute of Technology), Avishay Tal (Stanford University)

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):
Algorithmic Game Theory
Chair: Inbal Talgam Cohen
14:00  Testing Graphs in Vertex-Distribution-Free 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), Li-Yang Tan (Stanford University)
14:20  Testing Graphs against an Unknown Distribution
Lior Gishboliner (Tel Aviv University), Asaf Shapira (Tel Aviv University)
Faster k-SAT algorithms using biased-PPSZ
Thomas Dueholm Hansen (University of Copenhagen), Haim Kaplan (Tel Aviv University), Or Zamir (Tel Aviv University), Uri Zwick (Tel Aviv University)
Pseudorandom Generators for Width-3 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 Filos-Ratsikas (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 minor-closed 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):
Chair: Barna Saha
Session 6C (North 225B):
Algorithmic Statistics
Chair: Aviad Rubinstein
16:00  Settling the Sample Complexity of Single-parameter Revenue Maximization
Chenghao Guo (IIIS), Zhiyi Huang (University of Hong Kong), Xinzhi Zhang (IIIS)
Near-Linear Time Insertion-Deletion 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 Distributionally-Robust Stochastic Optimization with Black-Box Distributions
Andre Linhares (University of Waterloo), Chaitanya Swamy (University of Waterloo)
16:20  EC paper:
Sample Complexity for Non-Truthful 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 Multi-Item Auctions with Correlated Values
Christos-Alexandros Psomas, Ariel Schvartzman and S. Matthew Weinberg
Computing Quartet Distance is Equivalent to Counting 4-Cycles
Bartłomiej Dudek (University of Wrocław), Paweł Gawrychowski (University of Wrocław)
Degree-d Chow Parameters Robustly Determine Degree-d PTFs (and Algorithmic Applications)
Ilias Diakonikolas (USC), Daniel Kane (UCSD)
17:20  Optimal (and Benchmark-Optimal) Competition Complexity for Additive Buyers over Independent Items
Hedyeh Beyhaghi (Cornell University), S. Matthew Weinberg (Princeton University)
Local Decodability of the Burrows-Wheeler 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: Sublinear-Time BWT Construction and Optimal LCE Data Structure
Dominik Kempa (University of Warwick), Tomasz Kociumaka (University of Warsaw and Bar-Ilan 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  Non-Gaussian 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 Sub-Packetization 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 Extension-Based 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 Low-Degree 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 & UT-Austin)
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 Min-Plus and Exact Min-Max
Karl Bringmann (Max Planck Institute for Informatics), Marvin Kunnemann (Max Planck Institute for Informatics), Karol Wegrzycki (University of Warsaw)
Algorithmic Pirogov-Sinai Theory
Tyler Helmuth (University of Bristol), Will Perkins (University of Illinois at Chicago), Guus Regts (University of Amsterdam)
10:40  Memory-Sample 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):
Chair: Amos Fiat
Session 8C (North 225B):
Chair: Edith Cohen
14:00  Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering
Konstantin Makarychev (Northwestern University), Yury Makarychev (TTIC), Ilya Razenshteyn (Microsoft Research)

Oblivious Dimension Reduction for k-Means -- Beyond Subspaces and the Johnson-Lindenstrauss Lemma
Luca Becchetti (Sapienza), Marc Bury (Zalando SE), Vincent Cohen-Addad (CNRS), Fabrizio Grandoni (IDSIA), Chris Schwiegelshohn (Sapienza)
Fiat-Shamir: 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 Zero-Knowledge Beyond the Black-Box Barrier
Nir Bitansky (TAU), Dakshita Khurana (MSR), Omer Paneth (MIT)
The Online k-Taxi 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 Fiat-Shamir
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 Multi-Processor Cup Games
Michael A. Bender (Stony Brook University), Martin Farach-Colton (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 (Ben-Gurion 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 non-induced cycles
Mina Dalirrooyfard (MIT), Thuy Duong Vuong (MIT), Virginia Vassilevska Williams (MIT)
Sylvester-Gallai type theorems for quadratic polynomials
Amir Shpilka (Tel-Aviv 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 Resource-Bounded 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 N-vertex graphs with maximum degree K and diameter [1+o(1)]logK-1 N for each K-1 a prime power
Michael Capalbo (CCS)
Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective
Vishesh Jain (MIT), Frederic Koehler (MIT), Andrej Risteski (MIT)
18:00  END