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<
/td>
A Reverse Minkowski Theorem
Oded Regev, Noah Stephens-Davidowitz<
/td>
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<
/td>
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<
/td>
The Limitations of Optimization from Samples
Eric Balkanski, Aviad Rubinstein, Yaron Singer<
/td>
DecreaseKeys are Expensive for External Memory Priority Queues
Kasper Eenberg, Kasper Green Larsen, Huacheng Yu<
/td>
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