Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
1 | Julia Chuzhoy, David H. K. Kim, Rachit Nimavat |
New hardness results for routing on disjoint paths. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Gopal Pandurangan, Peter Robinson 0002, Michele Scquizzato |
A time- and message-optimal distributed algorithm for minimum spanning trees. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Stephan Artmann, Robert Weismantel, Rico Zenklusen |
A strongly polynomial algorithm for bimodular integer linear programming. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Damian Straszak, Nisheeth K. Vishnoi |
Real stable polynomials and matroids: optimization and counting. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Robert D. Kleinberg, Brendan Lucier |
Beating 1-1/e for ordered prophets. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, Piotr Sankowski |
Decremental single-source reachability in planar digraphs. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Sungjin Im, Benjamin Moseley, Xiaorui Sun |
Efficient massively parallel methods for dynamic programming. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson |
Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Sanjeev Arora, Rong Ge 0001, Tengyu Ma 0001, Andrej Risteski |
Provable learning of noisy-OR networks. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Nikhil Bansal 0001, Shashwat Garg |
Algorithmic discrepancy beyond partial coloring. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Yin Tat Lee, Santosh S. Vempala |
Geodesic walks in polytopes. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Haris Angelidakis, Konstantin Makarychev, Yury Makarychev |
Algorithms for stable and perturbation-resilient problems. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Moshe Babaioff, Yannai A. Gonczarowski, Noam Nisan |
The menu-size complexity of revenue approximation. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Anindya De, Ryan O'Donnell, Rocco A. Servedio |
Optimal mean-based algorithms for trace reconstruction. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong |
Subquadratic submodular function minimization. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Yakov Babichenko, Aviad Rubinstein |
Communication complexity of approximate Nash equilibria. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Volkan Cevher, Michael Kapralov, Jonathan Scarlett, Amir Zandieh |
An adaptive sublinear-time block sparse fourier transform. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Nate Foster |
The next 700 network programming languages (invited talk). |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Zhou Fan, Andrea Montanari |
How well do local algorithms solve semidefinite programs? |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Scott Aaronson, Adam Bouland, Greg Kuperberg, Saeed Mehraban |
The computational complexity of ball permutations. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Orna Kupferman |
Examining classical graph-theory problems from the viewpoint of formal-verification methods (invited talk). |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Marius Zimand |
Kolmogorov complexity version of Slepian-Wolf coding. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Nikhil Bansal 0001, Shashwat Garg, Jesper Nederlof, Nikhil Vyas 0001 |
Faster space-efficient algorithms for subset sum and k-sum. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Xi Chen 0001, Igor C. Oliveira, Rocco A. Servedio |
Addition is exponentially harder than counting for shallow monotone circuits. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Michael Elkin |
Distributed exact shortest paths in sublinear time. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Ankur Moitra |
Approximate counting, the Lovasz local lemma, and inference in graphical models. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Ryan O'Donnell, John Wright 0004 |
Efficient quantum tomography II. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Shuchi Chawla 0001, Nikhil R. Devanur, Alexander E. Holroyd, Anna R. Karlin, James B. Martin, Balasubramanian Sivan |
Stability of service under time-of-use pricing. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Zeyuan Allen Zhu |
Katyusha: the first direct acceleration of stochastic gradient methods. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Jonah Sherman |
Area-convexity, l∞ regularization, and undirected multicommodity flow. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Danupon Nanongkai, Thatchaphol Saranurak |
Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, Wei Zhan |
Exponential separations in the energy complexity of leader election. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Gil Cohen |
Towards optimal two-source extractors and Ramsey graphs. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Toniann Pitassi, Robert Robere |
Strongly exponential lower bounds for monotone computation. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Lior Gishboliner, Asaf Shapira |
Removal lemmas with polynomial bounds. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Jin-Yi Cai, Zhiguo Fu |
Holographic algorithm with matchgates is universal for planar #CSP over boolean domain. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | 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. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Prasad Raghavendra, Satish Rao, Tselil Schramm |
Strongly refuting random CSPs below the spectral threshold. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Hamed Hatami, Pierre McKenzie, Valerie King (eds.) |
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017 |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Radu Curticapean, Holger Dell, Dániel Marx |
Homomorphisms are a good basis for counting small subgraphs. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Rohit Gurjar, Thomas Thierauf |
Linear matroid intersection is in quasi-NC. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Anand Natarajan, Thomas Vidick |
A quantum linearity test for robustly verifying entanglement. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Danny Nguyen, Igor Pak |
Complexity of short Presburger arithmetic. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Sébastien Bubeck, Yin Tat Lee, Ronen Eldan |
Kernel-based methods for bandit convex optimization. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Michael A. Forbes 0001, Amir Shpilka, Ben Lee Volk |
Succinct hitting sets and barriers to proving algebraic circuits lower bounds. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Amin Coja-Oghlan, Florent Krzakala, Will Perkins 0001, Lenka Zdeborová |
Information-theoretic thresholds from the cavity method. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Xin Li 0006 |
Improved non-malleable extractors, non-malleable codes and independent source extractors. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Aviv Zohar |
Recent trends in decentralized cryptocurrencies (invited talk). |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan |
Average-case fine-grained hardness. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Vasilis Syrgkanis |
Fast convergence of learning in games (invited talk). |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Chris Peikert, Oded Regev 0001, Noah Stephens-Davidowitz |
Pseudorandomness of ring-LWE for any ring and modulus. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Ran Canetti, Oxana Poburinnaya, Muthuramakrishnan Venkitasubramaniam |
Equivocating Yao: constant-round adaptively secure multiparty computation in the plain model. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Tim Roughgarden, Inbal Talgam-Cohen |
Why prices need algorithms (invited talk). |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Satoru Iwata 0001, Yusuke Kobayashi 0001 |
A weighted linear matroid parity algorithm. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Yannai A. Gonczarowski, Noam Nisan |
Efficient empirical revenue maximization in single-parameter auction environments. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai |
Non-interactive delegation and batch NP verification from standard computational assumptions. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Tobias Christiani, Rasmus Pagh |
Set similarity search beyond MinHash. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Lin F. Yang |
Streaming symmetric norms via measure concentration. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Pierre-Étienne Meunier, Damien Woods |
The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Fedor Nazarov, Yuval Peres |
Trace reconstruction with exp(O(n1/3)) samples. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Igor C. Oliveira, Rahul Santhanam |
Pseudodeterministic constructions in subexponential time. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra |
Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Amnon Ta-Shma |
Explicit, almost optimal, epsilon-balanced codes. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Eric Balkanski, Aviad Rubinstein, Yaron Singer |
The limitations of optimization from samples. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Cristian S. Calude, Sanjay Jain 0001, Bakhadyr Khoussainov, Wei Li 0050, Frank Stephan 0001 |
Deciding parity games in quasipolynomial time. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Yossi Azar, Arun Ganesh, Rong Ge 0001, Debmalya Panigrahi |
Online service with delay. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer |
Sum of squares lower bounds for refuting any CSP. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Jugal Garg, Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod |
Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Zhengfeng Ji |
Compression of quantum multi-prover interactive proofs. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Omer Angel, Sébastien Bubeck, Yuval Peres, Fan Wei |
Local max-cut in smoothed polynomial time. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan 0001, Saket Saurabh 0001 |
Lossy kernelization. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Heng Guo 0001, Mark Jerrum, Jingcheng Liu 0001 |
Uniform sampling through the Lovasz local lemma. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Eshan Chattopadhyay, Xin Li 0006 |
Non-malleable codes and extractors for small-depth circuits, and affine functions. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Anurag Anshu, Dave Touchette, Penghui Yao, Nengkun Yu |
Exponential separation of quantum communication and classical information. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, S. Raja 0001 |
Randomized polynomial time identity testing for noncommutative circuits. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Nima Anari, Shayan Oveis Gharan |
A generalization of permanent inequalities and applications in counting and optimization. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Morten Stöckel |
Finding even cycles faster via capped k-walks. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Kasper Eenberg, Kasper Green Larsen, Huacheng Yu |
DecreaseKeys are expensive for external memory priority queues. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Yuval Dagan, Yuval Filmus, Ariel Gabizon, Shay Moran |
Twenty (simple) questions. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Yin Tat Lee, He Sun 0001 |
An SDP-based algorithm for linear-sized spectral sparsification. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Mohsen Ghaffari 0001, Fabian Kuhn, Yannic Maus |
On the complexity of local distributed graph problems. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten |
Approximate near neighbors for general symmetric norms. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Naman Agarwal, Zeyuan Allen Zhu, Brian Bullins, Elad Hazan, Tengyu Ma 0001 |
Finding approximate local minima faster than gradient descent. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Subhash Khot, Dor Minzer, Muli Safra |
On independent sets, 2-to-2 games, and Grassmann graphs. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Zhao Song 0002, David P. Woodruff, Peilin Zhong |
Low rank approximation with entrywise l1-norm error. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Neil Olver, László A. Végh |
A simpler and faster strongly polynomial algorithm for generalized flow maximization. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Bernhard Haeupler, Amirbehshad Shahrasbi |
Synchronization strings: codes for insertions and deletions approaching the Singleton bound. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Shaddin Dughmi, Jason D. Hartline, Robert Kleinberg, Rad Niazadeh |
Bernoulli factories and black-box reductions in mechanism design. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Xi Chen 0001, Erik Waingarten, Jinyu Xie |
Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Gillat Kol, Ran Raz, Avishay Tal |
Time-space hardness of learning sparse parities. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Andris Ambainis, Martins Kokainis |
Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Fabrizio Grandoni 0001, Bundit Laekhanukit |
Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Valeria Nikolaenko |
Practical post-quantum key agreement from generic lattices (invited talk). |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Valentine Kabanets, Daniel M. Kane, Zhenjian Lu |
A polynomial restriction lemma with applications. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Pasin Manurangsi |
Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Uriel Feige, Michal Feldman, Inbal Talgam-Cohen |
Approximate modularity revisited. |
STOC |
2017 |
DBLP DOI BibTeX RDF |
|
1 | Constantinos Daskalakis, Anindya De, Gautam Kamath 0001, Christos Tzamos |
A size-free CLT for poisson multinomials and its applications. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
1 | Artur Czumaj, Pan Peng 0001, Christian Sohler |
Relating two property testing models for bounded degree directed graphs. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
1 | Sanjoy Dasgupta |
A cost function for similarity-based hierarchical clustering. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
1 | Amir Abboud, Greg Bodwin |
The 4/3 additive spanner exponent is tight. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|