| Saturday June 18 | ||||||||||
| Joint STOC/SoCG Workshops and Tutorials | ||||||||||
| 9:00 - 10:45 |
|
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:00 | Lunch (on your own) | |||||||||
| 14:00 - 15:00 | Invited Talk: Timothy Chan, Computational Geometry, from Low to High Dimensions, Ballroom D | |||||||||
| 15:00 - 15:30 | Break | |||||||||
| 15:30 - 18:00 |
|
|||||||||
| 18:30 - 21:00 | Registration Desk Open: Lobby Level | 19:30 - 21:30 | STOC Welcome Reception: Empress Room (14th floor) | |||||||
| Sunday June 19 | ||||||||||
| 8:00 - 9:00 | Breakfast | |||||||||
| 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:00 | Break | |||||||||
| 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:00 | Lunch: 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:30 | Break | |||||||||
| 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:05 | Break | |||||||||
| 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:00 | Breakfast | |||||||||
| 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:00 | Break | |||||||||
| 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:00 | Lunch: 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:00 | Break | |||||||||
| 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:30 | Business Meeting: Ballroom D | |||||||||
| Tuesday June 21 | ||||||||||
| 8:00 - 9:00 | Breakfast | |||||||||
| 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 and 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:00 | Break | |||||||||
| 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 and Sample-optimal tomography of quantum states Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu and Nengkun Yu | ||||||||
| 12:35 - 14:00 | Lunch: 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:00 | Break | |||||||||
| 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 and 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 | ||||||||