Google
Google Scholar
MS Academic
CiteSeerX
CORE
Semantic Scholar49. 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
- Atri Rudra:
Answering FAQs in CSPs, probabilistic graphical models, databases, logic and matrix operations (invited talk). 4 - Orna Kupferman:
Examining classical graph-theory problems from the viewpoint of formal-verification methods (invited talk). 6
Session 1A
- Bernhard Haeupler, Amirbehshad Shahrasbi:
Synchronization strings: codes for insertions and deletions approaching the Singleton bound. 33-46
Session 1B
- 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 - 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
Session 3: STOC Best Papers
- Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Frank Stephan:
Deciding parity games in quasipolynomial time. 252-263
Session 4A
- Anurag Anshu, Dave Touchette, Penghui Yao, Nengkun Yu:
Exponential separation of quantum communication and classical information. 277-288 - 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
- 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
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
- 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
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
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 - 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
- Zhao Song, David P. Woodruff, Peilin Zhong:
Low rank approximation with entrywise l1-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 - 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
- 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
Session 8: Danny Lewin Prize STOC Best Student Paper
Session 9A
- 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 - 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
Session 9C
- Kasper Eenberg, Kasper Green Larsen, Huacheng Yu:
DecreaseKeys are expensive for external memory priority queues. 1081-1093 - 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(n1/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 - 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 - 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
maintained by 
at 
at 
data released under the ODC-BY 1.0 license; see also our legal information page
last updated on 2018-04-19 21:38 CEST by the dblp team