STOC 2018 Program
	Day 1: Monday June 25
	Tutorials 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 Hershey/Crocker (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 Hershey/Crocker (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	Extensor-coding 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 Hershey/Crocker (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 Hershey/Crocker (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 Hershey/Crocker (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 Hershey/Crocker (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 Hershey/Crocker (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 Hershey/Crocker (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