49. STOC 2017: Montreal, QC, Canada

• 
  Hamed Hatami, Pierre McKenzie, Valerie King:
  Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017. ACM 2017, ISBN 978-1-4503-4528-6

Invited Talks

• 
  Aviv Zohar:
  Recent trends in decentralized cryptocurrencies (invited talk). 1
• 
  Tim Roughgarden, Inbal Talgam-Cohen:
  Why prices need algorithms (invited talk). 2
• 
  Wim Martens:
  Optimizing tree pattern queries: why cutting is not enough (invited talk). 3
• 
  Atri Rudra:
  Answering FAQs in CSPs, probabilistic graphical models, databases, logic and matrix operations (invited talk). 4
• 
  Vasilis Syrgkanis:
  Fast convergence of learning in games (invited talk). 5
• 
  Orna Kupferman:
  Examining classical graph-theory problems from the viewpoint of formal-verification methods (invited talk). 6
• 
  Nate Foster:
  The next 700 network programming languages (invited talk). 7
• 
  Valeria Nikolaenko:
  Practical post-quantum key agreement from generic lattices (invited talk). 8

Session 1A

• 
  Yuval Dagan, Yuval Filmus, Ariel Gabizon, Shay Moran:
  Twenty (simple) questions. 9-21
• 
  Marius Zimand:
  Kolmogorov complexity version of Slepian-Wolf coding. 22-32
• 
  Bernhard Haeupler, Amirbehshad Shahrasbi:
  Synchronization strings: codes for insertions and deletions approaching the Singleton bound. 33-46

Session 1B

• 
  Moses Charikar, Jacob Steinhardt, Gregory Valiant:
  Learning from untrusted data. 47-60
• 
  Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Robert D. Kleinberg, Brendan Lucier:
  Beating 1-1/e for ordered prophets. 61-71
• 
  Sébastien Bubeck, Yin Tat Lee, Ronen Eldan:
  Kernel-based methods for bandit convex optimization. 72-85

Session 1C

• 
  Julia Chuzhoy, David H. K. Kim, Rachit Nimavat:
  New hardness results for routing on disjoint paths. 86-99
• 
  Neil Olver, László A. Végh:
  A simpler and faster strongly polynomial algorithm for generalized flow maximization. 100-111
• 
  Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Morten Stöckel:
  Finding even cycles faster via capped k-walks. 112-120

Session 2A

• 
  Prasad Raghavendra, Satish Rao, Tselil Schramm:
  Strongly refuting random CSPs below the spectral threshold. 121-131
• 
  Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer:
  Sum of squares lower bounds for refuting any CSP. 132-145
• 
  Amin Coja-Oghlan, Florent Krzakala, Will Perkins, Lenka Zdeborová:
  Information-theoretic thresholds from the cavity method. 146-157

Session 2B

• 
  Shaddin Dughmi, Jason D. Hartline, Robert Kleinberg, Rad Niazadeh:
  Bernoulli factories and black-box reductions in mechanism design. 158-169
• 
  Yang Cai, Mingfei Zhao:
  Simple mechanisms for subadditive buyers via duality. 170-183
• 
  Shuchi Chawla, Nikhil R. Devanur, Alexander E. Holroyd, Anna R. Karlin, James B. Martin, Balasubramanian Sivan:
  Stability of service under time-of-use pricing. 184-197

Session 2C

• 
  Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas:
  Faster space-efficient algorithms for subset sum and k-sum. 198-209
• 
  Radu Curticapean, Holger Dell, Dániel Marx:
  Homomorphisms are a good basis for counting small subgraphs. 210-223
• 
  Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh:
  Lossy kernelization. 224-237

Session 3: STOC Best Papers

• 
  Amnon Ta-Shma:
  Explicit, almost optimal, epsilon-balanced codes. 238-251
• 
  Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Frank Stephan:
  Deciding parity games in quasipolynomial time. 252-263
• 
  Satoru Iwata, Yusuke Kobayashi:
  A weighted linear matroid parity algorithm. 264-276

Session 4A

• 
  Anurag Anshu, Dave Touchette, Penghui Yao, Nengkun Yu:
  Exponential separation of quantum communication and classical information. 277-288
• 
  Zhengfeng Ji:
  Compression of quantum multi-prover interactive proofs. 289-302
• 
  Mohammad Bavarian, Thomas Vidick, Henry Yuen:
  Hardness amplification for entangled games via anchoring. 303-316
• 
  Scott Aaronson, Adam Bouland, Greg Kuperberg, Saeed Mehraban:
  The computational complexity of ball permutations. 317-327
• 
  Pierre-Étienne Meunier, Damien Woods:
  The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation. 328-341

Session 4B

• 
  Heng Guo, Mark Jerrum, Jingcheng Liu:
  Uniform sampling through the Lovasz local lemma. 342-355
• 
  Ankur Moitra:
  Approximate counting, the Lovasz local lemma, and inference in graphical models. 356-369
• 
  Damian Straszak, Nisheeth K. Vishnoi:
  Real stable polynomials and matroids: optimization and counting. 370-383
• 
  Nima Anari, Shayan Oveis Gharan:
  A generalization of permanent inequalities and applications in counting and optimization. 384-396
• 
  Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson:
  Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling. 397-409

Session 4C

• 
  Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, Adrian Vladu:
  Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs. 410-419
• 
  Fabrizio Grandoni, Bundit Laekhanukit:
  Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree. 420-428
• 
  Omer Angel, Sébastien Bubeck, Yuval Peres, Fan Wei:
  Local max-cut in smoothed polynomial time. 429-437
• 
  Haris Angelidakis, Konstantin Makarychev, Yury Makarychev:
  Algorithms for stable and perturbation-resilient problems. 438-451
• 
  Jonah Sherman:
  Area-convexity, l_∞ regularization, and undirected multicommodity flow. 452-460

Session 5A

• 
  Chris Peikert, Oded Regev, Noah Stephens-Davidowitz:
  Pseudorandomness of ring-LWE for any ring and modulus. 461-473
• 
  Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai:
  Non-interactive delegation and batch NP verification from standard computational assumptions. 474-482
• 
  Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan:
  Average-case fine-grained hardness. 483-496
• 
  Ran Canetti, Oxana Poburinnaya, Muthuramakrishnan Venkitasubramaniam:
  Equivocating Yao: constant-round adaptively secure multiparty computation in the plain model. 497-509

Session 5B

• 
  Lior Gishboliner, Asaf Shapira:
  Removal lemmas with polynomial bounds. 510-522
• 
  Xi Chen, Erik Waingarten, Jinyu Xie:
  Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness. 523-536
• 
  Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Debmalya Panigrahi:
  Online and dynamic algorithms for set cover. 537-550
• 
  Yossi Azar, Arun Ganesh, Rong Ge, Debmalya Panigrahi:
  Online service with delay. 551-563

Session 5C

• 
  Assaf Naor, Robert Young:
  The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n. 564-575
• 
  Subhash Khot, Dor Minzer, Muli Safra:
  On independent sets, 2-to-2 games, and Grassmann graphs. 576-589
• 
  Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra:
  Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. 590-603
• 
  Zhou Fan, Andrea Montanari:
  How well do local algorithms solve semidefinite programs? 604-614

Session 6A

• 
  Valentine Kabanets, Daniel M. Kane, Zhenjian Lu:
  A polynomial restriction lemma with applications. 615-628
• 
  William M. Hoza, Chris Umans:
  Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace. 629-640
• 
  Josh Alman, R. Ryan Williams:
  Probabilistic rank and matrix rigidity. 641-652
• 
  Michael A. Forbes, Amir Shpilka, Ben Lee Volk:
  Succinct hitting sets and barriers to proving algebraic circuits lower bounds. 653-664
• 
  Igor Carboni Oliveira, Rahul Santhanam:
  Pseudodeterministic constructions in subexponential time. 665-677

Session 6B

• 
  Yin Tat Lee, He Sun:
  An SDP-based algorithm for linear-sized spectral sparsification. 678-687
• 
  Zhao Song, David P. Woodruff, Peilin Zhong:
  Low rank approximation with entrywise l₁-norm error. 688-701
• 
  Volkan Cevher, Michael Kapralov, Jonathan Scarlett, Amir Zandieh:
  An adaptive sublinear-time block sparse fourier transform. 702-715
• 
  Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Lin F. Yang:
  Streaming symmetric norms via measure concentration. 716-729
• 
  David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, Sushant Sachdeva:
  Sampling random spanning trees faster than matrix multiplication. 730-742

Session 6C

• 
  Gopal Pandurangan, Peter Robinson, Michele Scquizzato:
  A time- and message-optimal distributed algorithm for minimum spanning trees. 743-756
• 
  Michael Elkin:
  Distributed exact shortest paths in sublinear time. 757-770
• 
  Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, Wei Zhan:
  Exponential separations in the energy complexity of leader election. 771-783
• 
  Mohsen Ghaffari, Fabian Kuhn, Yannic Maus:
  On the complexity of local distributed graph problems. 784-797
• 
  Sungjin Im, Benjamin Moseley, Xiaorui Sun:
  Efficient massively parallel methods for dynamic programming. 798-811

Session 7A

• 
  Danny Nguyen, Igor Pak:
  Complexity of short Presburger arithmetic. 812-820
• 
  Rohit Gurjar, Thomas Thierauf:
  Linear matroid intersection is in quasi-NC. 821-830
• 
  Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, S. Raja:
  Randomized polynomial time identity testing for noncommutative circuits. 831-841
• 
  Jin-Yi Cai, Zhiguo Fu:
  Holographic algorithm with matchgates is universal for planar #CSP over boolean domain. 842-855

Session 7B

• 
  Yannai A. Gonczarowski, Noam Nisan:
  Efficient empirical revenue maximization in single-parameter auction environments. 856-868
• 
  Moshe Babaioff, Yannai A. Gonczarowski, Noam Nisan:
  The menu-size complexity of revenue approximation. 869-877
• 
  Yakov Babichenko, Aviad Rubinstein:
  Communication complexity of approximate Nash equilibria. 878-889
• 
  Jugal Garg, Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod:
  Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria. 890-901

Session 7C

• 
  Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten:
  Approximate near neighbors for general symmetric norms. 902-913
• 
  Nikhil Bansal, Shashwat Garg:
  Algorithmic discrepancy beyond partial coloring. 914-926
• 
  Yin Tat Lee, Santosh Srinivas Vempala:
  Geodesic walks in polytopes. 927-940
• 
  Oded Regev, Noah Stephens-Davidowitz:
  A reverse Minkowski theorem. 941-953

Session 8: Danny Lewin Prize STOC Best Student Paper

• 
  Pasin Manurangsi:
  Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph. 954-961

Session 9A

• 
  Ryan O'Donnell, John Wright:
  Efficient quantum tomography II. 962-974
• 
  Boaz Barak, Pravesh K. Kothari, David Steurer:
  Quantum entanglement, sum of squares, and the log rank conjecture. 975-988
• 
  Andris Ambainis, Martins Kokainis:
  Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. 989-1002
• 
  Anand Natarajan, Thomas Vidick:
  A quantum linearity test for robustly verifying entanglement. 1003-1015

Session 9B

• 
  Eric Balkanski, Aviad Rubinstein, Yaron Singer:
  The limitations of optimization from samples. 1016-1027
• 
  Uriel Feige, Michal Feldman, Inbal Talgam-Cohen:
  Approximate modularity revisited. 1028-1041
• 
  Fedor Nazarov, Yuval Peres:
  Trace reconstruction with exp(O(n^1/3)) samples. 1042-1046
• 
  Anindya De, Ryan O'Donnell, Rocco A. Servedio:
  Optimal mean-based algorithms for trace reconstruction. 1047-1056
• 
  Sanjeev Arora, Rong Ge, Tengyu Ma, Andrej Risteski:
  Provable learning of noisy-OR networks. 1057-1066
• 
  Gillat Kol, Ran Raz, Avishay Tal:
  Time-space hardness of learning sparse parities. 1067-1080

Session 9C

• 
  Kasper Eenberg, Kasper Green Larsen, Huacheng Yu:
  DecreaseKeys are expensive for external memory priority queues. 1081-1093
• 
  Tobias Christiani, Rasmus Pagh:
  Set similarity search beyond MinHash. 1094-1107
• 
  Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, Piotr Sankowski:
  Decremental single-source reachability in planar digraphs. 1108-1121
• 
  Danupon Nanongkai, Thatchaphol Saranurak:
  Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n^{1/2 - ε})-time. 1122-1129
• 
  Christian Wulff-Nilsen:
  Fully-dynamic minimum spanning forest with improved worst-case update time. 1130-1143

Session 10A

• 
  Xin Li:
  Improved non-malleable extractors, non-malleable codes and independent source extractors. 1144-1156
• 
  Gil Cohen:
  Towards optimal two-source extractors and Ramsey graphs. 1157-1170
• 
  Eshan Chattopadhyay, Xin Li:
  Non-malleable codes and extractors for small-depth circuits, and affine functions. 1171-1184
• 
  Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma:
  An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy. 1185-1194

Session 10B

• 
  Naman Agarwal, Zeyuan Allen Zhu, Brian Bullins, Elad Hazan, Tengyu Ma:
  Finding approximate local minima faster than gradient descent. 1195-1199
• 
  Zeyuan Allen Zhu:
  Katyusha: the first direct acceleration of stochastic gradient methods. 1200-1205
• 
  Stephan Artmann, Robert Weismantel, Rico Zenklusen:
  A strongly polynomial algorithm for bimodular integer linear programming. 1206-1219
• 
  Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong:
  Subquadratic submodular function minimization. 1220-1231

Session 10C

• 
  Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio:
  Addition is exponentially harder than counting for shallow monotone circuits. 1232-1245
• 
  Toniann Pitassi, Robert Robere:
  Strongly exponential lower bounds for monotone computation. 1246-1255
• 
  Avishay Tal:
  Formula lower bounds via the quantum method. 1256-1268