Saturday June 18
Joint STOC/SoCG Workshops and Tutorials
9:00 - 10:45
Workshop A: Ballroom D Workshop B: William Dawes Rm Workshop C: Thomas Paine Rm Workshop D: Molly Pitcher Rm
1st Intl. Workshop on Geometry and Machine Learning Spanners: Graphs and Geometry Algorithms on Topologically Restricted Graphs Tutorial: Hardness of Learning
10:45 - 11:10 Break
11:10 - 12:10 Invited Talk: Santosh Vempala, The Interplay of Sampling and Optimization in High Dimension, Ballroom D
12:10 - 14:00Lunch (on your own)
14:00 - 15:00 Invited Talk: Timothy Chan, Computational Geometry, from Low to High Dimensions, Ballroom D
15:00 - 15:30Break
15:30 - 18:00
Workshop A: Ballroom D Workshop B: William Dawes Rm Workshop C: Thomas Paine Rm Workshop E: Molly Pitcher Rm
1st Intl. Workshop on Geometry and Machine Learning Spanners: Graphs and Geometry Algorithms on Topologically Restricted Graphs Geometric Representations of Graphs
18:30 - 21:00Registration Desk Open: Lobby Level
19:30 - 21:30STOC Welcome Reception: Empress Room (14th floor)
Sunday June 19
8:00 - 9:00Breakfast
session 1A: Ballroom ABC
chair: Timothy Chan
session 1B: Ballroom D
chair: Avi Wigderson
9:00 - 9:20 Almost Tight Bounds for Eliminating Depth Cycles in Three Dimensions
Boris Aronov and Micha Sharir
Constant-Round Interactive Proofs for Delegating Computation
Omer Reingold, Guy N. Rothblum and Ron D. Rothblum
9:25 - 9:45 Geometric Median in Nearly Linear Time
Michael B. Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki and Aaron Sidford
Candidate Hard Unique Game
Subhash Khot and Dana Moshkovitz
9:50 - 10:10 Separating subadditive Euclidean functionals
Alan Frieze and Wesley Pegden
On the effect of randomness on planted 3-coloring models
Roee David and Uriel Feige
10:15 - 10:35 Bounded Degree Cosystolic Expanders of Every Dimension
Shai Evra and Tali Kaufman
Matrix Rigidity of Random Toeplitz Matrices
Oded Goldreich and Avishay Tal
10:35 - 11:00Break
Session 2A: Ballroom ABC
chair: Sanjeev Arora
Session 2B: Ballroom D
chair: Debmalya Panigrahi
11:00 - 11:20 Complexity theoretic limitations on learning halfspaces
Amit Daniely
Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
Nikhil Bansal, Aravind Srinivasan and Ola Svensson
11:25 - 11:45 A cost function for similarity-based hierarchical clustering
Sanjoy Dasgupta
A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints using LP Hierarchies
Elaine Levey and Thomas Rothvoss
11:50 - 12:10 The Computational Power of Optimization in Online Learning
Elad Hazan and Tomer Koren
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
Samuel B. Hopkins, Tselil Schramm, Jonathan Shi and David Steurer
12:15 - 12:35 Instance Optimal Learning of Discrete Distributions
Gregory Valiant and Paul Valiant
Maximizing Determinants under Partition Constraints
Aleksandar Nikolov and Mohit Singh
12:35 - 14:00Lunch: Riverside Pavilion
Session 3A: Ballroom ABC
chair: Zeev Dvir
Session 3B: Ballroom D
chair: Alexandr Andoni
14:00 - 14:20 High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity
Swastik Kopparty, Or Meir, Noga Ron-Zewi and Shubhangi Saraf
Optimal Principal Component Analysis in Distributed and Streaming Models
Christos Boutsidis, David P. Woodruff and Peilin Zhong
14:25 - 14:45 Repairing Reed-Solomon Codes
Venkatesan Guruswami and Mary Wootters
Weighted Low Rank Approximations with Provable Guarantees
Ilya Razenshteyn, Zhao Song and David P. Woodruff
14:50 - 15:10 Efficiently decoding Reed-Muller codes from random errors
Ramprasad Saptharishi, Amir Shpilka and Ben Lee Volk
Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time
Michael Kapralov
15:10 - 15:30Break
Session 4A: Ballroom ABC
chair: Zeev Dvir
Session 4B: Ballroom D
chair: Fabrizio Grandoni
15:30 - 15:50 Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs
Gil Cohen
Parallel Exhaustive Search without Coordination
Pierre Fraigniaud, Amos Korman and Yoav Rode
15:55 - 16:15 Non-Malleable Extractors and Codes, with their Many Tampered Extensions
Eshan Chattopadhyay, Vipul Goyal and Xin Li
Beyond matroids: secretary problem and prophet inequality with general constraints
Aviad Rubinstein
16:20 - 16:40 Extractors for Sumset Sources
Eshan Chattopadhyay and Xin Li
Online Matching: Haste makes Waste!
Yuval Emek, Shay Kutten and Roger Wattenhofer
16:40 - 17:05Break
Session 5: Ballroom ABCD
chair: Yishay Mansour
17:05 - 17:25 A Tight Space Bound for Consensus
Leqi Zhu
17:25 - 17:45 The 4/3 Additive Spanner Exponent is Tight
Amir Abboud and Greg Bodwin
Monday June 20
8:00 - 9:00Breakfast
session 6A: Ballroom ABC
chair: Konstantin Makarychev
Session 6B: Ballroom D
chair: Éva Tardos
9:00 - 9:20 Cell-probe Lower Bounds for Dynamic Problems via a New Communication Model
Huacheng Yu
Algorithmic Bayesian Persuasion
Shaddin Dughmi and Haifeng Xu
9:25 - 9:45 Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made
Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams and Ryan Williams
The Sample Complexity of Auctions with Side Information
Nikhil R. Devanur, Zhiyi Huang and Christos-Alexandros Psomas
9:50 - 10:10 Deterministic Decremental Single Source Shortest Paths: Beyond the O(mn) Bound
Aaron Bernstein and Shiri Chechik
Do Prices Coordinate Markets?
Justin Hsu, Jamie Morgenstern, Ryan Rogers, Aaron Roth and Ricky Vohra
10:15 - 10:35 New Deterministic Approximation Algorithms for Fully Dynamic Matching
Sayan Bhattacharya, Monika Henzinger and Danupon Nanongkai
A Discrete and Bounded Envy-free Cake Cutting Protocol for Four Agents
Haris Aziz and Simon Mackenzie
10:35 - 11:00Break
Session 7A: Ballroom ABC
chair: Jing Chen
Session 7B: Ballroom D
chair: Debmalya Panigrahi
11:00 - 11:20 Distributed (Delta+1)-Coloring in Sublogarithmic Rounds
David G. Harris, Johannes Schneider and Hsin-Hao Su
Fault Tolerant Subgraph for Single Source Reachability: Generic and Optimal
Baswana Surender, Choudhary Keerti and Roditty Liam
11:25 - 11:45 A Lower Bound for the Distributed Lovász Local Lemma
Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela and Jar Uitto
Deterministic and Probabilistic Binary Search in Graphs
Ehsan Emamjomeh-Zadeh, David Kempe and Vikrant Singhal
11:50 - 12:10 A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
Monika Henzinger, Sebastian Krinninger and Danupon Nanongkai
Ramanujan Coverings of Graphs
Chris Hall, Doron Puder and William F. Sawin
12:15 - 12:35 Contention Resolution with Log-Logstar Channel Accesses
Michael A. Bender, Tsvi Kopelowitz, Seth Pettie and Maxwell Young
Enumerating Parametric Global Minimum Cuts by Random Interleaving
David Karger
12:35 - 14:00Lunch: Riverside Pavilion
Session 8A: Ballroom ABC
chair: Fabrizio Grandoni
Session 8B: Ballroom D
chair: Jakob Nordstrom
14:00 - 14:20 Improved Approximation for Node-Disjoint Paths in Planar Graphs
Julia Chuzhoy, David H. K. Kim and Shi Li
Near-optimal small-depth lower bounds for small distance connectivity
Xi Chen, Igor C. Oliveira, Rocco A. Servedio and Li-Yang Tan
14:25 - 14:45 A PTAS for Planar Group Steiner Tree via Spanner Bootstrapping and Prize Collecting
MohammadHossein Bateni, Erik D. Demaine, MohammadTaghi Hajiaghayi and Daniel Marx
On the size of homogeneous and of depth four formulas with low individual degree
Neeraj Kayal, Chandan Saha and Sebastien Tavenas
14:50 - 15:10 Approximating connectivity domination in weighted bounded-genus graphs
Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu and Davi Meierfrankenfeld
Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits
Daniel M. Kane and Ryan Williams
15:15 - 15:35 Routing under Balance
Alina Ene, Gary Miller, Jakub Pachocki and Aaron Sidford
Poly-logarithmic Frege depth lower bounds via an expander switching lemma
Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio and Li-Yang Tan
15:35 - 16:00Break
Session 9: Ballroom ABCD
chair: Yishay Mansour
16:00 - 16:20 Reed-Muller Codes Achieve Capacity on Erasure Channels
Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Sasoglu and Rudiger Urbanke
16:20 - 16:40 Explicit Two-Source Extractors and Resilient Functions
Eshan Chattopadhyay and David Zuckerman
16:40 - 17:00 Graph Isomorphism in Quasipolynomial Time
Laszlo Babai
20:30 - 22:30Business Meeting: Ballroom D
Tuesday June 21
8:00 - 9:00Breakfast
session 10A: Ballroom ABC
chair: Sofya Raskhodnikova
session 10B: Ballroom D
chair: Mario Szegedy
9:00 - 9:20 Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem
Sepehr Assadi, Sanjeev Khanna and Yang Li
Bipartite Perfect Matching is in quasi-NC
Stephen Fenner, Rohit Gurjar and Thomas Thierauf
9:25 - 9:45 Streaming algorithms for embedding and computing edit distance in the low distance regime
Diptarka Chakraborty, Elazar Goldenberg and Michal Koucký
Exact Algorithms via Monotone Local Search
Fedor Fomin, Serge Gaspers, Daniel Lokshtanov and Saket Saurabh
9:50 - 10:10 On Approximating Functions of the Singular Values in a Stream
Yi Li and David Woodruff
Basis Collapse for Holographic Algorithms Over All Domain Sizes
Sitan Chen

Base collapse of holographic algorithms
Mingji Xia
10:15 - 10:35 Beating CountSketch for Heavy Hitters in Insertion Streams
Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin and David P. Woodruff
Separations in Query Complexity Based on Pointer Functions
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha and Juris Smotrovs
10:35 - 11:00Break
Session 11A: Ballroom ABC
chair: Konstantin Makarychev
Session 11B: Ballroom D
chair: Mario Szegedy
11:00 - 11:20 Semidefinite Programs on Sparse Random Graphs and their Application to Community Detection
Andrea Montanari and Subhabrata Sen
Separations in query complexity using cheat sheets
Scott Aaronson, Shalev Ben-David and Robin Kothari
11:25 - 11:45 How Robust are Reconstruction Thresholds for Community Detection?
Ankur Moitra, William Perry and Alexander S. Wein
Entangled simultaneity versus classical interactivity in communication complexity
Dmitry Gavinsky
11:50 - 12:10 Sparsified Cholesky and Multigrid Solvers for Connection Laplacians
Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva and Daniel A. Spielman
Classical Verification of Quantum Proofs
Zhengfeng Ji
12:15 - 12:35 Parallel Algorithms for Select and Partition with Noisy Comparisons
Mark Braverman, Jieming Mao and S. Matthew Weinberg
Efficient quantum tomography
Ryan O'Donnell and John Wright

Sample-optimal tomography of quantum states
Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu and Nengkun Yu
12:35 - 14:00Lunch: Riverside Pavilion
Session 12A: Ballroom ABC
chair: Jing Chen
Session 12B: Ballroom D
chair: Avi Wigderson
14:00 - 14:20 A Duality Based Unified Approach to Bayesian Mechanism Design
Yang Cai, Nikhil Devanur and S. Matthew Weinberg
Exponential Separation of Communication and External Information
Anat Ganor, Gillat Kol and Ran Raz
14:25 - 14:45 Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders
Shahar Dobzinski
Interactive Compression for Product Distributions
Gillat Kol
14:50 - 15:10 Watch and Learn: Optimizing from Revealed Preferences Feedback
Aaron Roth, Jonathan Ullman and Zhiwei Steven Wu
Constant-rate coding for multiparty interactive communication is impossible
Mark Braverman, Klim Efremenko, Ran Gelles and Bernhard Haeupler
15:15 - 15:35 The Price of Anarchy in Large Games
Michal Feldman, Nicole Immorlica, Brendan Lucier, Tim Roughgarden and Vasilis Syrgkanis
Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality
Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen and David P. Woodruff
15:35 - 16:00Break
Session 13A: Ballroom ABC
chair: Sofya Raskhodnikova
Session 13B: Ballroom D
chair: Huijia (Rachel) Lin
16:00 - 16:20 A Polynomial Lower Bound for Testing Monotonicity
Aleksandrs Belovs and Eric Blais
Algebraic Attacks against Random Local Functions and Their Countermeasures
Benny Applebaum and Shachar Lovett
16:25 - 16:45 Relating Two Property Testing Models for Bounded Degree Directed Graphs
Artur Czumaj, Pan Peng and Christian Sohler
Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations
Gilad Asharov, Moni Naor, Gil Segev and Ido Shahaf
16:50 - 17:10 Algorithmic Stability for Adaptive Data Analysis
Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer and Jonathan Ullman
Watermarking Cryptographic Capabilities
Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan and Daniel Wichs
17:15 - 17:35 The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications
Ilias Diakonikolas, Daniel Kane and Alistair Stewart

A Size-Free CLT for Poisson Multinomials and its Applications
Costis Daskalakis, Anindya De, Gautam Kamath and Christos Tzamos
Textbook Non-Malleable Commitments
Vipul Goyal, Omkant Pandey and Silas Richelson