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 SlepianWolf Coding Marius Zimand 
Beating 11/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 
Kernelbased Methods for Bandit Convex Optimization Sebastien Bubeck, Ronen Eldan, Yin Tat Lee 
Finding Even Cycles Faster via Capped kwalks 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 BlackBox Reductions in Mechanism Design
Shaddin Dughmi, Jason Hartline, Bobby Kleinberg, Rad Niazadeh 
Faster SpaceEfficient Algorithms for Subset Sum and kSum 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  Informationtheoretic Thresholds from the Cavity Method Amin CojaOghlan, Florent Krzakala, Will Perkins, Lenka Zdeborova 
Stability of Service under TimeofUse 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, EpsilonBalanced
Codes Amnon TaShma 

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 
AlmostLinearTime
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 MultiProver Interactive Proofs Zhengfeng Ji 
Approximate Counting, the Lovasz Local Lemma and Inference in
Graphical Models Ankur Moitra 
Surviving in Directed Graphs: A QuasiPolylogarithmic
Approximation for TwoConnected 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 MaxCut 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 PerturbationResilient Problems Haris Angelidakis, Konstantin Makarychev, Yury Makarychev 
11:40  The Noncooperative Tile Assembly Model Is Not intrinsically
Universal or Capable of Bounded Turing Machine Simulation PierreÉtienne Meunier, Damien Woods 
Algorithmic and Optimization Aspects of
BrascampLiebIinequalities, 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 RingLWE for Any Ring and Modulus Chris Peikert, Oded Regev, Noah StephensDavidowitz 
Removal Lemmas with Polynomial Bounds Asaf Shapira, Lior Gishboliner 
The integrality Gap of the GoemansLinial SDP Relaxation for
Sparsest Cut Is at Least a Constant Multiple of √log n Assaf Naor, Robert Young 
2:20  NonInteractive 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, 2to2 Games and Grassmann Graphs Subhash Khot, Dor Minzer, Muli Safra 
2:40  AverageCase FineGrained 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 WeaklyExponential Lower
Bounds for LP Relaxations of CSPs Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra 
3:00  Equivocating Yao: ConstantRound 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 SDPBased Algorithm for LinearSized Spectral
Sparsification Yin Tat Lee, He Sun 
Time and MessageOptimal 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 l_{1}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 SublinearTime Block Sparse Fourier Transform Volkan Cevher, Michael Kapralov, Jonathan Scarlett, Amir Zandieh 
Exponential Separations in the Energy Complexity of Leader
Election YiJun 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 SingleParameter
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 QuasiNC Rohit Gurjar, Thomas Thierauf 
The MenuSize 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 JinYi 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 StephensDavidowitz 
3:20  Break  
Session 8: Danny Lewin Prize STOC Best Student Paper  
3:50  AlmostPolynomial Ratio ETHHardness of
Approximating Densest KSubgraph 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 TalgamCohen 
Set Similarity Beyond Minhash Tobias Christiani, Rasmus Pagh 
11:00  Quantum Algorithm for Tree Size Estimation, with Applications to
Backtracking and 2player Games Andris Ambainis, Martins Kokainis 
Trace Reconstruction with exp(O(n^{1/3})) Samples Fedor Nazarov, Yuval Peres Optimal Meanbased Algorithms for Trace Reconstruction Anindya De, Ryan O'Donnell, Rocco A. Servedio 
Decremental SingleSource 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 Noisyor Networks Sanjeev Arora, Rong Ge, Tengyu Ma, Andrej Risteski 
Dynamic Spanning Forest with WorstCase Update Time: Adaptive,
Las Vegas, and O(n^{1/2−ε})Time Danupon Nanongkai, Thatchaphol Saranurak 
11:40  TimeSpace Hardness of Learning Sparse Parities Gillat Kol, Ran Raz, Avishay Tal 
FullyDynamic Minimum Spanning Forest with Improved WorstCase
Update Time Christian WulffNilsen 

12:00  Lunch (on your own)  
Session 10A:  Session 10B:  Session 10C:  
2:00  Improved NonMalleable Extractors, NonMalleable Codes and
Independent Source Extractors Xin Li 
Finding Approximate Local Minima Faster than Gradient
Descent Naman Agarwal, Zeyuan AllenZhu, 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 TwoSource Extractors and Ramsey Graphs Gil Cohen 
Katyusha: The First Direct Acceleration of Stochastic Gradient
Methods Zeyuan AllenZhu 
Strongly Exponential Lower Bounds for Monotone Computation Toniann Pitassi, Robert Robere 
2:40  NonMalleable Codes and Extractors for SmallDepth 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 NonMalleable to TwoSource
Extractors: Achieving Nearlogarithmic MinEntropy Avraham BenAroya, Dean Doron, Amnon TaShma 
Subquadratic Submodular Function Minimization Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sam ChiuWai 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 