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): Streaming Chair: Barna Saha	Session 3C (North 225B): Privacy 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)	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 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)	See COLT Program
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)	See COLT Program
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)	See COLT Program
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)	See COLT Program
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)	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 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): Stringology 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): Cryptography Chair: Amos Fiat	Session 8C (North 225B): Algorithms 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