STOC 2017 Program
	Monday June 19
8:00	Continental Breakfast: Grand Salon Opera Foyer
9:00	Tutorials: Grand Salon ABC
11:00	Break: Grand Salon Opera Foyer
	Session 1A: Grand Salon A Chair: Valerie King	Session 1B: Grand Salon B Chair: Eric Price	Session 1C: Grand Salon C Mohit Singh
11:30	Twenty (Simple) Questions Yuval Dagan, Yuval Filmus, Ariel Gabizon, Shay Moran	Learning from Untrusted Data Moses Charikar, Jacob Steinhardt, Gregory Valiant	New Hardness Results for Routing on Disjoint Paths Julia Chuzhoy, David H. K. Kim, Rachit Nimavat
11:50	Kolmogorov Complexity Version of Slepian-Wolf Coding Marius Zimand	Beating 1-1/e for Ordered Prophets Melika Abolhassani, Soheil Ehsani Banafati, Hossein Esfandiari, MohammadTaghi HajiAghayi, Robert Kleinberg, Brendan Lucier	A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization Neil Olver, László A. Végh
12:10	Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound Bernhard Haeupler, Amirbehshad Shahrasbi	Kernel-based Methods for Bandit Convex Optimization Sebastien Bubeck, Ronen Eldan, Yin Tat Lee	Finding Even Cycles Faster via Capped k-walks Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Morten Stöckel
12:30	Lunch (on your own)
	Session 2A: Grand Salon A Chair: Hamed Hatami	Session 2B: Grand Salon B Chair: Allan Borodin	Session 2C: Grand Salon C Chair: Nick Harvey
2:30	Strongly Refuting Random CSPs below the Spectral Threshold Prasad Raghavendra, Satish Rao, Tselil Schramm	Bernoulli Factories and Black-Box Reductions in Mechanism Design Shaddin Dughmi, Jason Hartline, Bobby Kleinberg, Rad Niazadeh	Faster Space-Efficient Algorithms for Subset Sum and k-Sum Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas
2:50	Sum of Squares Lower Bounds for Refuting Any CSP Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer	Simple Mechanisms for Subadditive Buyers via Duality Yang Cai, Mingfei Zhao	Homomorphisms Are a Good Basis for Counting Small Subgraphs Radu Curticapean, Holger Dell, Dániel Marx
3:10	Information-theoretic Thresholds from the Cavity Method Amin Coja-Oghlan, Florent Krzakala, Will Perkins, Lenka Zdeborova	Stability of Service under Time-of-Use Pricing Shuchi Chawla, Nikhil R. Devanur, Alexander E. Holroyd, Anna R. Karlin, James Martin, Balasubramanian Sivan	Lossy Kernelization Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Ramanujan Sridharan
3:30	Break: Grand Salon Opera Foyer
	Session 3: STOC Best Papers: Grand Salon ABC Chairs: Jelani Nelson, Artur Czumaj, Mohit Singh
4:00	Explicit, Almost Optimal, Epsilon-Balanced Codes Amnon Ta-Shma
4:30	Deciding Parity Games in Quasipolynomial Time Cristian Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Frank Stephan
5:00	A Weighted Linear Matroid Parity Algorithm Satoru Iwata, Yusuke Kobayashi
5:30- 7:00	Reception: Grand Salon Opera Foyer
	Tuesday June 20
8:00	Continental Breakfast: Grand Salon Opera Foyer
8:50	Keynote: Avi Wigderson: Grand Salon BC
9:50	Break: Grand Salon Opera Foyer
	Session 4A: Grand Salon A Chair: Pierre McKenzie	Session 4B: Grand Salon B Chair: Nick Harvey	Session 4C: Grand Salon C Chair: Jelani Nelson
10:20	Exponential Separation between Quantum Communication and Classical Information Anurag Anshu, Dave Touchette, Penghui Yao, Nengkun Yu	Uniform Sampling through the Lovasz Local Lemma Heng Guo, Mark Jerrum, Jingcheng Liu	Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs Michael B. Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, Adrian Vladu
10:40	Compression of Quantum Multi-Prover Interactive Proofs Zhengfeng Ji	Approximate Counting, the Lovasz Local Lemma and Inference in Graphical Models Ankur Moitra	Surviving in Directed Graphs: A Quasi-Polylogarithmic Approximation for Two-Connected Directed Steiner Tree Fabrizio Grandoni, Bundit Laekhanukit
11:00	Hardness Amplification for Entangled Games via Anchoring Mohammad Bavarian, Thomas Vidick, Henry Yuen	Real Stable Polynomials and Matroids: Optimization and Counting Damian Straszak, Nisheeth K. Vishnoi	Local Max-Cut in Smoothed Polynomial Time Omer Angel, Sebastien Bubeck, Yuval Peres, Fan Wei
11:20	The Computational Complexity of Ball Permutations Scott Aaronson, Adam Bouland, Greg Kuperberg, Saeed Mehraban	A Generalization of Permanent Inequalities and Applications in Counting and Optimization Nima Anari, Shayan Oveis Gharan	Algorithms for Stable and Perturbation-Resilient Problems Haris Angelidakis, Konstantin Makarychev, Yury Makarychev
11:40	The Non-cooperative Tile Assembly Model Is Not intrinsically Universal or Capable of Bounded Turing Machine Simulation Pierre-Étienne Meunier, Damien Woods	Algorithmic and Optimization Aspects of Brascamp-Lieb Inequalities, via Operator Scaling Ankit Garg, Leonid Gurvits, Rafael Oliveira, Avi Wigderson	Area-Convexity, l-infinity Regularization, and Undirected Multicommodity Flow Jonah Sherman
12:00	Lunch (on your own)
	Session 5A: Grand Salon A Chair: Russell Impagliazzo	Session 5B: Grand Salon B Chair: Artur Czumaj	Session 5C: Grand Salon C Chair: Allan Borodin
2:00	Pseudorandomness of Ring-LWE for Any Ring and Modulus Chris Peikert, Oded Regev, Noah Stephens-Davidowitz	Removal Lemmas with Polynomial Bounds Asaf Shapira, Lior Gishboliner	The integrality Gap of the Goemans-Linial SDP Relaxation for Sparsest Cut Is at Least a Constant Multiple of √log n Assaf Naor, Robert Young
2:20	Non-Interactive Delegation and Batch NP Verification from Standard Computational Assumptions Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai	Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness Xi Chen, Erik Waingarten, Jinyu Xie	On Independent Sets, 2-to-2 Games and Grassmann Graphs Subhash Khot, Dor Minzer, Muli Safra
2:40	Average-Case Fine-Grained Hardness Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan	Online and Dynamic Algorithms for Set Cover Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Debmalya Panigrahi	Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra
3:00	Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model Ran Canetti, Oxana Poburinnaya, Muthuramakrishnan Venkitasubramaniam	Online Service with Delay Yossi Azar, Arun Ganesh, Rong Ge, Debmalya Panigrahi	How Well Do Local Algorithms Solve Semidefinite Programs? Zhou Fan, Andrea Montanari
3:20	Break: Grand Salon Opera Foyer
3:50	Invited Plenary Talks: Grand Salon BC
5:30	Dinner (on your own)
8:00- 10:30	Poster Session: Soprano AB
	Wednesday June 21
8:00	Continental Breakfast: Grand Salon Opera Foyer
8:50	Panel: TCS the Next Decade: Grand Salon BC
9:50	Break: Grand Salon Opera Foyer
	Session 6A: Grand Salon A Chair: Hamed Hatami	Session 6B: Grand Salon B Chair: Aleksander Mądry	Session 6C: Grand Salon C Chair: Krzysztof Onak
10:20	A Polynomial Restriction Lemma with Applications Valentine Kabanets, Daniel M. Kane, Zhenjian Lu	An SDP-Based Algorithm for Linear-Sized Spectral Sparsification Yin Tat Lee, He Sun	A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees Gopal Pandurangan, Peter Robinson, Michele Scquizzato
10:40	Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace William M. Hoza, Chris Umans	Low Rank Approximation with Entrywise l1-Norm Error Zhao Song, David P. Woodruff, Peilin Zhong	Distributed Exact Shortest Paths in Sublinear Time Michael Elkin
11:00	Probabilistic Rank and Matrix Rigidity Josh Alman, Ryan Williams	An Adaptive Sublinear-Time Block Sparse Fourier Transform Volkan Cevher, Michael Kapralov, Jonathan Scarlett, Amir Zandieh	Exponential Separations in the Energy Complexity of Leader Election Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, Wei Zhan
11:20	Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds Michael A. Forbes, Amir Shpilka, Ben Lee Volk	Streaming Symmetric Norms via Measure Concentration Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Lin F. Yang	On the Complexity of Local Distributed Graph Problems Mohsen Ghaffari, Fabian Kuhn, Yannic Maus
11:40	Pseudodeterministic Constructions in Subexponential Time Igor Carboni Oliveira, Rahul Santhanam	Sampling Random Spanning Trees Faster than Matrix Multiplication David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, Sushant Sachdeva	Efficient Massively Parallel Methods for Dynamic Programming Sungjin Im, Benjamin Moseley, Xiaorui Sun
12:00	Lunch (on your own)
	Session 7A: Grand Salon A Chair: Russell Impagliazzo	Session 7B: Grand Salon B Chair: Artur Czumaj	Session 7C: Grand Salon C Chair: Jelani Nelson
2:00	Complexity of Short Presburger Arithmetic Danny Nguyen, Igor Pak	Efficient Empirical Revenue Maximization in Single-Parameter Auction Environments Yannai A. Gonczarowski, Noam Nisan	Approximate Near Neighbors for General Symmetric Norms Alexandr Andoni, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten
2:20	Linear Matroid Intersection Is in Quasi-NC Rohit Gurjar, Thomas Thierauf	The Menu-Size Complexity of Revenue Approximation Moshe Babaioff, Yannai A. Gonczarowski, Noam Nisan	Algorithmic Discrepancy Beyond Partial Coloring Nikhil Bansal, Shashwat Garg
2:40	Randomized Polynomial Time Identity Testing for Noncommutative Circuits V. Arvind, Pushkar S Joglekar, Partha Mukhopadhyay, S. Raja	Communication Complexity of Approximate Nash Equilibria Yakov Babichenko, Aviad Rubinstein	Geodesic Walks in Polytopes Yin Tat Lee, Santosh S. Vempala
3:00	Holographic Algorithm with Matchgates Is Universal for Planar #CSP Over Boolean Domain Jin-Yi Cai, Zhiguo Fu	Settling the Complexity of Leontief and PLC Exchange Markets under Exact and Approximate Equilibria Jugal Garg, Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod	A Reverse Minkowski Theorem Oded Regev, Noah Stephens-Davidowitz
3:20	Break: Grand Salon Opera Foyer
	Session 8: Danny Lewin Prize STOC Best Student Paper: Grand Salon BC Chair: Russell Impagliazzo
3:50	Almost-Polynomial Ratio ETH-Hardness of Approximating Densest K-Subgraph Pasin Manurangsi
4:15	Invited Plenary Talks: Grand Salon BC
5:30	Dinner (on your own)
8:00	Gödel Prize Presentation: Grand Salon BC
	Knuth Prize Presentation and Lecture: Oded Goldreich: Grand Salon BC
9:00- 10:30	STOC Business Meeting: Grand Salon A
	Thursday June 22
8:00	Continental Breakfast: Grand Salon Opera Foyer
8:50	Keynote: Orna Kupferman: Grand Salon BC
9:50	Break: Grand Salon Opera Foyer
	Session 9A: Grand Salon A Chair: Aleksander Mądry	Session 9B: Grand Salon B Chair: Eric Price	Session 9C: Grand Salon 9 Chair: Valerie King
10:20	Efficient Quantum Tomography II Ryan O'Donnell, John Wright	The Limitations of Optimization from Samples Eric Balkanski, Aviad Rubinstein, Yaron Singer	DecreaseKeys are Expensive for External Memory Priority Queues Kasper Eenberg, Kasper Green Larsen, Huacheng Yu
10:40	Quantum Entanglement, Sum of Squares, and the Log Rank Conjecture Boaz Barak, Pravesh Kothari, David Steurer< /td>	Approximate Modularity Revisited Uriel Feige, Michal Feldman, Inbal Talgam-Cohen	Set Similarity Beyond Minhash Tobias Christiani, Rasmus Pagh
11:00	Quantum Algorithm for Tree Size Estimation, with Applications to Backtracking and 2-player Games Andris Ambainis, Martins Kokainis	Trace Reconstruction with exp(O(n1/3)) Samples Fedor Nazarov, Yuval Peres Optimal Mean-based Algorithms for Trace Reconstruction Anindya De, Ryan O'Donnell, Rocco A. Servedio	Decremental Single-Source Reachability in Planar Digraphs Giuseppe F.Italiano, Adam Karczmarz, Jakub Łacki, Piotr Sankowski
11:20	A Quantum Linearity Test for Robustly Verifying Entanglement Anand Natarajan, Thomas Vidick	Provable Learning of Noisy-or Networks Sanjeev Arora, Rong Ge, Tengyu Ma, Andrej Risteski	Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and O(n1/2−ε)-Time Danupon Nanongkai, Thatchaphol Saranurak
11:40		Time-Space Hardness of Learning Sparse Parities Gillat Kol, Ran Raz, Avishay Tal	Fully-Dynamic Minimum Spanning Forest with Improved Worst-Case Update Time Christian Wulff-Nilsen
12:00	Lunch (on your own)
	Session 10A: Grand Salon A Chair: Russell Impagliazzo	Session 10B: Grand Salon B Chair: Mohit Singh	Session 10C: Grand Salon C Chair: Pierre McKenzie
2:00	Improved Non-Malleable Extractors, Non-Malleable Codes and Independent Source Extractors Xin Li	Finding Approximate Local Minima Faster than Gradient Descent Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, Tengyu Ma	Addition is Exponentially Harder than Counting for Shallow Monotone Circuits Xi Chen, Igor C. Oliveira, Rocco A. Servedio
2:20	Towards Optimal Two-Source Extractors and Ramsey Graphs Gil Cohen	Katyusha: The First Direct Acceleration of Stochastic Gradient Methods Zeyuan Allen-Zhu	Strongly Exponential Lower Bounds for Monotone Computation Toniann Pitassi, Robert Robere
2:40	Non-Malleable Codes and Extractors for Small-Depth Circuits, and Affine Functions Eshan Chattopadhyay, Xin Li	A Strongly Polynomial Algorithm for Bimodular Integer Linear Programming Stephan Artmann, Robert Weismantel, Rico Zenklusen	Formula Lower Bounds via the Quantum Method Avishay Tal
3:00	An Efficient Reduction from Non-Malleable to Two-Source Extractors: Achieving Near-logarithmic Min-Entropy Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma	Subquadratic Submodular Function Minimization Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sam Chiu-Wai Wong
3:20	Break: Grand Salon Opera Foyer
3:50	Invited Plenary Talks: Grand Salon BC
5:30	Dinner (on your own)
8:00- 10:30	Poster Session: Soprano AB
	Friday June 23
9:00- 4:00	Workshops: Grand Salon ABC