STOC 2018 Program
  Day 1: Monday June 25
Bunker Hill/Watercourt/Museum/Hershey/Crocker
09:00 3 parallel tutorials
11:00 Coffee Break
  Session 1A
Bunker Hill/Watercourt
(Chair: Giuseppe Italiano)
Session 1B
Museum A/B
(Chair: Eric Allender)
Session 1C
(Chair: Boaz Barak)
11:30 k-server via multiscale entropic regularization
Sebastien Bubeck, Michael B. Cohen, James R. Lee, Yin Tat Lee, Aleksander Madry
A Converse to Banach's Fixed Point Theorem and its CLS Completeness
Constantinos Daskalakis, Christos Tzamos, Manolis Zampetakis
Composable and Versatile Privacy via Truncated CDP
Mark Bun, Cynthia Dwork, Guy N. Rothblum, Thomas Steinke
11:50 How to Match when All Vertices Arrive Online
Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, Xue Zhu
Consensus Halving is PPA-Complete
Aris Filos-Ratsikas, Paul W. Goldberg
Universal Protocols for Information Dissemination using Emergent Signals
Bartlomiej Dudek, Adrian Kosowski
12:10 Online Load balancing on Related Machines
Sungjin Im, Nathaniel Kell, Debmalya Panigrahi, Maryam Shadloo
The Art Gallery Problem is ∃ℝ-complete
Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow
Shape of Diffusion and Size of Monochromatic Region of a Two-Dimensional Spin System
Hamed Omidvar, Massimo Franceschetti
12:30 Lunch
  Session 2A
Bunker Hill/Watercourt
(Chair: Robert Kleinberg)
Session 2B
Museum A/B
(Chair: Sanjeev Arora)
Session 2C
(Chair: Ilias Diakonikolas)
02:30 Stochastic bandits robust to adversarial corruptions
Thodoris Lykouris, Vahab Mirrokni, Renato Paes Leme
An exponential lower bound for Individualization-Refinement algorithms for Graph Isomorphism
Daniel Neuen, Pascal Schweitzer
Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Oliveira, Avi Wigderson
02:50 Bounding the Menu-Size of Approximately Optimal Auctions via Optimal-Transport Duality
Yannai A. Gonczarowski
Cornelius Brand, Holger Dell, Thore Husfeldt
The Paulsen Problem, Continuous Operator Scaling, and Smoothed Analysis
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Akshay Ramachandran
03:10 A Tighter Welfare Guarantee for First-Price Auctions
Darrell Hoy, Sam Taggart, Zihe Wang
The Query Complexity of Graph Isomorphism: Bypassing Distribution Testing Lower Bounds
Krzysztof Onak, Xiaorui Sun
Operator Scaling with Specified Marginals
Cole Franks
03:30 Coffee Break
  STOC Award Papers
Bunker Hill/Watercourt/Museum
04:00 A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
Ola Svensson, Jakub Tarnawski, László Végh
04:30 An almost-linear time algorithm for uniform random spanning tree generation
Aaron Schild
05:00 Invited talk: Sanjoy Dasgupta: A Neural Algorithm for Similarity Search (Science)
05:30 Reception
  Day 2: Tuesday June 26
  Plenary Session
Bunker Hill/Watercourt/Museum
08:50 Keynote
Emmanuel Candes
Sailing through Data: Discoveries and Mirages

Bunker Hill/Watercourt/Museum
09:50 Coffee Break
  Session 3A
Bunker Hill/Watercourt
(Chair: Allan Borodin)
Session 3B
Museum A/B
(Chair: Thomas Vidick)
Session 3C
(Chair: Eric Allender)
10:20 (Gap/S)ETH Hardness of SVP
Divesh Aggarwal, Noah Stephens-Davidowitz
Universal points in the asymptotic spectrum of tensors
Matthias Christandl, Péter Vrana, Jeroen Zuiddam
Hitting Sets with Near-Optimal Error for Read-Once Branching Programs
Mark Braverman, Gil Cohen, Sumegha Garg
10:40 Fine-Grained Complexity for Sparse Graphs
Udit Agarwal, Vijaya Ramachandran
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
Mark Bun, Robin Kothari, Justin Thaler
Improved Pseudorandomness for Unordered Branching Programs thorugh Local Monotonicity
Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal
11:00 More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
Amir Abboud, Karl Bringmann, Holger Dell, Jesper Nederlof
Algorithmic Polynomials
Alexander A. Sherstov
Towards a Proof of the 2-to-1 Games Conjecture?
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Shmuel Safra
11:20 Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, Nicole Wein
Shadow Tomography of Quantum States
Scott Aaronson
A Friendly Smoothed Analysis of the Simplex Method
Daniel Dadush, Sophie Huiberts
11:40 Fine-grained reductions from approximate counting to decision
Holger Dell, John Lapinskas
Capacity Approaching Coding for Low Noise Interactive Quantum Communication
Debbie Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, Nengkun Yu
Incomplete Nested Dissection
Rasmus Kyng, Richard Peng, Robert Schwieterman, Peng Zhang
12:00 Lunch / TCS Women: Lunch, Panel, and Research Session (Bradbury/Rose)
  Session 4A
Bunker Hill/Watercourt
(Chair: Danupon Nanongkai)
Session 4B
Museum A/B
(Chair: Thomas Vidick)
Session 4C
(Chair: Monika Henzinger)
02:00 Deterministic Distributed Edge-Coloring with Fewer Colors
Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, Jara Uitto
General Strong Polarization
Jarosław Błasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan
The minimum Euclidean-norm point in a convex polytope: Wolfe's combinatorial algorithm is exponential
Jesus De Loera, Jamie Haddock, Luis Rademacher
02:20 Improved Distributed Algorithms for Exact Shortest Paths
Mohsen Ghaffari, Jason Li
Capacity upper bounds for deletion-type channels
Mahdi Cheraghchi
Near-optimal linear decision trees for k-SUM and related problems
Daniel M. Kane, Shachar Lovett, Shay Moran
02:40 An Optimal Distributed (\Delta+1)-Coloring Algorithm?
Yi-Jun Chang, Wenzheng Li, Seth Pettie
Interactive Coding Over the Noisy Broadcast Channel
Klim Efremenko, Gillat Kol, Raghuvansh Saxena
Fast Fencing
Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, Mikkel Thorup
03:00 Nearly Work-Efficient Parallel Algorithm for Digraph Reachability
Jeremy T. Fineman
Efficient decoding of random errors for quantum expander codes
Omar Fawzi, Antoine Grospellier, Anthony Leverrier
Framework for ETH-tight Algorithms and Lower Bounds in Geometric Intersection Graphs
Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, Tom C. van der Zanden
03:20 Round Compression for Parallel Matching Algorithms
Artur Czumaj, Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, Krzysztof Onak, Piotr Sankowski
Explicit Binary Tree Codes with Polylogarithmic Size Alphabet
Gil Cohen, Bernhard Haeupler, Leonard Schulman
The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett
03:40 Coffee Break
  Plenary Session
Bunker Hill/Watercourt/Museum
04:10 Invited talk:Monia Ghobadi: Programming the Topology of Networks: Technology and Algorithms (SIGCOMM 2016)
04:35 Invited talk: Irene Lo: Dynamic Matching in School Choice: Efficient Seat Reassignment after Late Cancellations (MATCH-UP 2017)
05:00 Invited talk: Vyes Sekar: Rethinking Network Flow Monitoring with UnivMon (SIGCOMM 2016)
05:30 Dinner
  Poster Session
Bradbury/Rose and Hershey/Crocker
08:00 poster sessions with drinks and snacks served
  Day 3: Wednesday June 27
  Plenary Session
Bunker Hill/Watercourt/Museum
08:50 Keynote
Cynthia Dwork
The Emerging Theory of Algorithmic Fairness

Bunker Hill/Watercourt/Museum
09:50 Coffee Break
  Session 5A
Bunker Hill/Watercourt
(Chair: Allan Borodin)
Session 5B
Museum A/B
(Chair: Boaz Barak)
Session 5C
(Chair: Robert Kleinberg)
10:20 Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency
Yuval Emek, Shay Kutten, Ron Lavi, Yangguang Shi
Collusion Resistant Traitor Tracing from Learning with Errors
Rishab Goyal, Venkata Koppula, Brent Waters
On Approximating the Number of k-cliques in Sublinear Time
Talya Eden, Dana Ron, C. Seshadhri
10:40 A (5/3+ϵ)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes
Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, Hang Zhou
Multi-Collision Resistance: A Paradigm for Keyless Hash Functions
Nir Bitansky, Yael Tauman Kalai, Omer Paneth
Testing Conditional Independence of Discrete Distributions
Clement L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
11:00 Constant-Factor Approximation for Ordered k-Median
Jarosław Byrka, Krzysztof Sornat, Joachim Spoerhase
Non-Malleable Secret Sharing
Vipul Goyal, Ashutosh Kumar
Distribution-free Junta Testing
Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, Jinyu Xie
11:20 Improved Approximation for Tree Augmentation: Saving by Rewiring
Fabrizio Grandoni, Christos Kalaitzis, Rico Zenklusen
Breaking the Circuit-Size Barrier in Secret Sharing
Tianren Liu, Vinod Vaikuntanathan
A Generalized Turan Problem and its Applications
Asaf Shapira, Lior Gishboliner
11:40 Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding
Ravishankar Krishnaswamy, Shi Li, Sai Sandeep
Succinct Delegation for Low-Space Non-Deterministic Computation
Saikrishna Badrinarayanan, Yael Tauman Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs
Construction of new local spectral high dimensional expanders
Tali Kaufman, Izhar Oppenheim
12:00 Lunch
  Session 6A
Bunker Hill/Watercourt
(Chair: Monika Henzinger)
Session 6B
Museum A/B
(Chair: Eric Allender)
Session 6C
(Chair: Moses Charikar)
02:00 Data-Dependent Hashing via Nonlinear Spectral Gaps
Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten
Quantified Derandomization of Linear Threshold Circuits
Roei Tell
Sparse Kneser graphs are Hamiltonian
Torsten Mütze, Jerri Nummenpalo, Bartosz Walczak
02:20 Smooth heaps and a dual view of self-adjusting data structures
László Kozma, Thatchaphol Saranurak
Clique Is Hard on Average for Regular Resolution
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander Razborov
A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings
Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber
02:40 Fully Dynamic Maximal Independent Set with Sublinear Update Time
Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon
On the complexity of hazard-free circuits
Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, Karteek Sreenivasaiah
Counting hypergraph colourings in the local lemma regime
Heng Guo, Chao Liao, Pinyan Lu, Chihao Zhang
03:00 At the Roots of Dictionary Compression: String Attractors
Dominik Kempa, Nicola Prezza
Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP
Cody Murray, Ryan Williams
On Non-Optimally Expanding Sets in Grassmann Graphs
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
03:20 Synchronization Strings: Explicit Constructions, Local Decoding, and Applications
Bernhard Haeupler, Amirbehshad Shahrasbi
Monotone Circuit Lower Bounds from Resolution
Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov
Metric Embedding via Shortest Path Decompositions
Ittai Abraham, Arnold Filtser, Anupam Gupta, Ofer Neiman
03:40 Coffee Break
  Plenary Session
Bunker Hill/Watercourt/Museum
04:10 Invited talk: Rong Ge: Optimization Landscape for Matrix Completion (NIPS 2016)
04:35 Invited talk: Sergey Bravyi: Quantum Advantage with Shallow Circuits (QIP 2018)
05:00 Invited talk: Sam Staton: Higher-Order Probability Theory (LICS 2017)
05:30 Dinner
  Business Meeting
Bunker Hill/Watercourt/Museum
08:00 Business Meeting (1.5hrs) and a 30-40min "STOC is 50" celebration
  Day 4: Thursday June 28
  Plenary Session
Bunker Hill/Watercourt/Museum
08:50 Keynote
Bruno Olshausen
Perception in Brain and Machines

Bunker Hill/Watercourt/Museum
09:50 Coffee Break
  Session 7A
Bunker Hill/Watercourt
(Chair: Danupon Nanongkai)
Session 7B
Museum A/B
(Chair: Avrim Blum)
Session 7C
(Chair: Monika Henzinger)
10:20 Interactive Compression to External Information
Mark Braverman, Gillat Kol
Mixture Models, Robustness, and Sum of Squares Proofs
Samuel B. Hopkins, Jerry Li

Robust Moment Estimation and Improved Clustering via Sum of Squares

Pravesh Kothari, Jacob Steinhardt, David Steurer
A Matrix Expander Chernoff Bound
Ankit Garg, Yin Tat Lee, Zhao Song, Nikhil Srivastava
10:40 Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
Kasper Green Larsen, Omri Weinstein, Huacheng Yu
List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation
Yin Tat Lee, Santosh S. Vempala
11:00 Extractor-Based Time-Space Lower Bounds for Learning
Sumegha Garg, Ran Raz, Avishay Tal
Learning Geometric Concepts with Nasty Noise
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
Stochastic Localization + Stieltjes Barrier = Tight Bound for Log-Sobolev
Yin Tat Lee, Santosh S. Vempala
11:20 Cell-Probe Lower Bounds from Online Communication Complexity
Josh Alman, Joshua R. Wang, Huacheng Yu
Prediction with a Short Memory
Sham Kakade, Percy Liang, Vatsal Sharan, Gregory Valiant
An homotopy method for lp regression provably beyond self-concordance and in input-sparsity time
Sebastien Bubeck, Michael B. Cohen, Yin Tat Lee, Yuanzhi Li
11:40 Simulation Beats Richness: New Data-Structure Lower Bounds
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions
Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, Ilya Razenshteyn
The Adaptive Complexity of Maximizing a Submodular Function
Eric Balkanski, Yaron Singer
12:00 Lunch
  Session 8A
Bunker Hill/Watercourt
(Chair: Ilias Diakonikolas)
Session 8B
Museum A/B
(Chair: Danupon Nanongkai)
Session 8C
(Chair: Robert Kleinberg)
02:00 Discovering the roots: Uniform closure results for algebraic classes under factoring
Pranjal Dutta, Nitin Saxena, Amit Sinhababu
Almost Polynomial Hardness of Node-Disjoint Paths in Grids
Julia Chuzhoy, David H. K. Kim, Rachit Nimavat
Fast Algorithms for Knapsack via Convolution and Prediction
MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Saeed Seddighin, Cliff Stein
02:20 Bootstrapping variables in algebraic circuits
Manindra Agrawal, Sumanta Ghosh, Nitin Saxena
Inapproximability of the independent set polynomial in the complex plane
Ivona Bezakova, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic
On the Parameterized Complexity of Approximating Dominating Set
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi
02:40 A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits
Michael A. Forbes, Amir Shpilka
Sum-of-Squares meets Nash: Non-Enumerative Algorithms and Optimal Lower Bounds
Pravesh Kothari, Ruta Mehta
Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector
Diptarka Chakraborty, Lior Kamma, Kasper Green Larsen
03:00 Generalized matrix completion and algebraic natural proofs
Markus Blaeser, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov
Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law
Max Simchowitz, Ahmed El Alaoui, Benjamin Recht
New Classes of Distributed Time Complexity
Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, Jukka Suomela
03:20 Lifting Nullstellensatz to Monotone Span Programs over Any Field
Toniann Pitassi, Robert Robere
Hardness of Approximate Nearest Neighbor Search
Aviad Rubinstein
Holiest Minimum-Cost Paths and Flows in Surface Graphs
Jeff Erickson, Kyle Fox, Luvsandondov Lkhamsuren
03:40 Coffee Break
  Plenary Session
Bunker Hill/Watercourt/Museum
04:10 Invited talk: Tengyu Ma: Generalization and Equilibrium in Generative Adversarial Nets (GANs) (ICML 2017)
04:35 Invited talk: Dan Suciu: Optimal Query Processing meets Information Theory (PODS 2016)
05:00 Athena Lecture: Lydia E. Kavraki
05:30 Dinner
  Poster Session
Bradbury/Rose and Hershey/Crocker
08:00 poster session with drinks and snacks served
  Day 5: Friday June 29
  Workshop Day
Bunker Hill/Watercourt/Museum/Hershey/Crocker
08:45 Workshop day until 4:00 pm