default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID49th 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 C. 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 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 - 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 S. 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(n1/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(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 - 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 C. 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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-12-04 22:07 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
