STOC 2017 Program
  Monday June 19
8:00 Continental Breakfast
9:00 Tutorials
11:00 Break
  Session 1A: Session 1B: Session 1C:
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 I: 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
Sren Dahlgaard, Mathias Bæk Tejs Knudsen, Morten Stöckel
12:30 Lunch (on your own)
  Session 2A: Session 2B: Session 2C:
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
  Session 3: STOC Best Papers
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
  Tuesday June 20
8:00 Continental Breakfast
8:50 Keynote: Avi Wigderson
9:50 Break
  Session 4A: Session 4B: Session 4C:
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-LiebIinequalities, via Operator Scaling
Ankit Garg, Leonid Gurvits, Rafael Oliveira, Avi Wigderson
12:00 Lunch (on your own)
  Session 5A: Session 5B: Session 5C:
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
3:50 Invited Plenary Talks
5:30 Dinner (on your own)
8:00-
10:30
Poster Session
  Wednesday June 21
8:00 Continental Breakfast
8:50 Panel: TCS the Next Decade
9:50 Break
  Session 6A: Session 6B: Session 6C:
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
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: Session 7B: Session 7C:
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
  Session 8: Danny Lewin Prize STOC Best Student Paper
3:50 Almost-Polynomial Ratio ETH-Hardness of Approximating Densest K-Subgraph
Pasin Manurangsi
4:15 Invited Plenary Talks
5:30 Dinner (on your own)
8:00 Knuth Prize Lecture
9:00-
10:30
STOC Business Meeting
  Thursday June 22
8:00 Continental Breakfast
8:50 Keynote: Orna Kupferman
9:50 Break
  Session 9A: Session 9B: Session 9C:
10:20 Efficient Quantum Tomography II
Ryan O'Donnell, John Wright
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
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: Session 10B: Session 10C:
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
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
3:50 Invited Plenary Talks
5:30 Dinner (on your own)
8:00-
10:30
Poster Session
  Friday June 23
9:00-
4:00
Workshops