| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Elad Hazan, Tomer Koren |
The computational power of optimization in online learning.  |
STOC  |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Bansal 0001, Aravind Srinivasan, Ola Svensson |
Lift-and-round to improve weighted completion time on unrelated machines. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Benny Applebaum, Shachar Lovett |
Algebraic attacks against random local functions and their countermeasures. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Aviad Rubinstein |
Beyond matroids: secretary problem and prophet inequality with general constraints. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Roee David, Uriel Feige |
On the effect of randomness on planted 3-coloring models. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan, Daniel Wichs |
Watermarking cryptographic capabilities. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk |
Efficiently decoding Reed-Muller codes from random errors. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Dmitry Gavinsky |
Entangled simultaneity versus classical interactivity in communication complexity. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Aaron Bernstein, Shiri Chechik |
Deterministic decremental single source shortest paths: beyond the o(mn) bound. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, David Meierfrankenfeld |
Approximating connectivity domination in weighted bounded-genus graphs. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai |
New deterministic approximation algorithms for fully dynamic matching. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Ankur Moitra, William Perry, Alexander S. Wein |
How robust are reconstruction thresholds for community detection? |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Aleksandrs Belovs, Eric Blais |
A polynomial lower bound for testing monotonicity. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Omer Reingold, Guy N. Rothblum, Ron D. Rothblum |
Constant-round interactive proofs for delegating computation. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Yang Cai 0001, Nikhil R. Devanur, S. Matthew Weinberg |
A duality based unified approach to Bayesian mechanism design. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Surender Baswana, Keerti Choudhary, Liam Roditty |
Fault tolerant subgraph for single source reachability: generic and optimal. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Sitan Chen |
Basis collapse for holographic algorithms over all domain sizes. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai |
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Sasoglu, Rüdiger L. Urbanke |
Reed-Muller codes achieve capacity on erasure channels. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Ehsan Emamjomeh-Zadeh, David Kempe 0001, Vikrant Singhal |
Deterministic and probabilistic binary search in graphs. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Neeraj Kayal, Chandan Saha 0001, Sébastien Tavenas |
On the size of homogeneous and of depth four formulas with low individual degree. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, Daniel A. Spielman |
Sparsified Cholesky and multigrid solvers for connection laplacians. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman, Ankit Garg, Tengyu Ma 0001, Huy L. Nguyen, David P. Woodruff |
Communication lower bounds for statistical estimation problems via a distributed data processing inequality. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil R. Devanur, Zhiyi Huang 0002, Christos-Alexandros Psomas |
The sample complexity of auctions with side information. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Haris Aziz 0001, Simon Mackenzie |
A discrete and bounded envy-free cake cutting protocol for four agents. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, Maxwell Young |
Contention resolution with log-logstar channel accesses. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Chris Hall, Doron Puder, William F. Sawin |
Ramanujan coverings of graphs. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilya P. Razenshteyn, Zhao Song 0002, David P. Woodruff |
Weighted low rank approximations with provable guarantees. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel M. Kane, Ryan Williams 0001 |
Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler |
Constant-rate coding for multiparty interactive communication is impossible. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke 0002, Uri Stemmer, Jonathan R. Ullman |
Algorithmic stability for adaptive data analysis. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Pierre Fraigniaud, Amos Korman, Yoav Rodeh |
Parallel exhaustive search without coordination. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Justin Hsu, Jamie Morgenstern, Ryan M. Rogers, Aaron Roth 0001, Rakesh Vohra |
Do prices coordinate markets? |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer |
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Gil Cohen |
Two-source dispersers for polylogarithmic entropy and improved ramsey graphs. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Sebastian Brandt 0002, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, Jara Uitto |
A lower bound for the distributed Lovász local lemma. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart |
The fourier transform of poisson multinomial distributions and its algorithmic applications. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Daniely |
Complexity theoretic limitations on learning halfspaces. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Kapralov |
Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Christos Boutsidis, David P. Woodruff, Peilin Zhong |
Optimal principal component analysis in distributed and streaming models. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Shahar Dobzinski |
Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Jeongwan Haah, Aram W. Harrow, Zheng-Feng Ji, Xiaodi Wu, Nengkun Yu |
Sample-optimal tomography of quantum states. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Huacheng Yu |
Cell-probe lower bounds for dynamic problems via a new communication model. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | David R. Karger |
Enumerating parametric global minimum cuts by random interleaving. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich 0001, Avishay Tal |
Matrix rigidity of random toeplitz matrices. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrea Montanari, Subhabrata Sen |
Semidefinite programs on sparse random graphs and their application to community detection. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Anat Ganor, Gillat Kol, Ran Raz |
Exponential separation of communication and external information. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Alan M. Frieze, Wesley Pegden |
Separating subadditive euclidean functionals. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, David P. Woodruff |
Beating CountSketch for heavy hitters in insertion streams. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký 0001 |
Streaming algorithms for embedding and computing edit distance in the low distance regime. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Ryan Williams 0001 |
Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Aaron Roth 0001, Jonathan R. Ullman, Zhiwei Steven Wu |
Watch and learn: optimizing from revealed preferences feedback. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Mingji Xia |
Base collapse of holographic algorithms. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Eshan Chattopadhyay, Vipul Goyal, Xin Li 0006 |
Non-malleable extractors and codes, with their many tampered extensions. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Eshan Chattopadhyay, David Zuckerman |
Explicit two-source extractors and resilient functions. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Mary Wootters |
Repairing Reed-solomon codes. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | László Babai |
Graph isomorphism in quasipolynomial time [extended abstract]. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Subhash Khot, Dana Moshkovitz |
Candidate hard unique game. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Gilad Asharov, Moni Naor, Gil Segev 0001, Ido Shahaf |
Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Scott Aaronson, Shalev Ben-David, Robin Kothari |
Separations in query complexity using cheat sheets. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan |
Poly-logarithmic Frege depth lower bounds via an expander switching lemma. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Yi Li 0002, David P. Woodruff |
On approximating functions of the singular values in a stream. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Elaine Levey, Thomas Rothvoss |
A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuval Emek, Shay Kutten, Roger Wattenhofer |
Online matching: haste makes waste! |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Gregory Valiant, Paul Valiant |
Instance optimal learning of discrete distributions. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Eshan Chattopadhyay, Xin Li 0006 |
Extractors for sumset sources. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael B. Cohen, Yin Tat Lee, Gary L. Miller, Jakub Pachocki, Aaron Sidford |
Geometric median in nearly linear time. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Gillat Kol |
Interactive compression for product distributions. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Aleksandar Nikolov, Mohit Singh |
Maximizing determinants under partition constraints. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | MohammadHossein Bateni, Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx |
A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan O'Donnell, John Wright 0004 |
Efficient quantum tomography. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Vipul Goyal, Omkant Pandey, Silas Richelson |
Textbook non-malleable commitments. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Sepehr Assadi, Sanjeev Khanna, Yang Li 0025 |
Tight bounds for single-pass streaming complexity of the set cover problem. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Shai Evra, Tali Kaufman |
Bounded degree cosystolic expanders of every dimension. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Xi Chen 0001, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan |
Near-optimal small-depth lower bounds for small distance connectivity. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, Saket Saurabh 0001 |
Exact algorithms via monotone local search. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman, Jieming Mao, S. Matthew Weinberg |
Parallel algorithms for select and partition with noisy comparisons. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Leqi Zhu |
A tight space bound for consensus. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Zhengfeng Ji |
Classical verification of quantum proofs. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Michal Feldman, Nicole Immorlica, Brendan Lucier, Tim Roughgarden, Vasilis Syrgkanis |
The price of anarchy in large games. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Boris Aronov, Micha Sharir |
Almost tight bounds for eliminating depth cycles in three dimensions. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Alina Ene, Gary L. Miller, Jakub Pachocki, Aaron Sidford |
Routing under balance. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf |
Bipartite perfect matching is in quasi-NC. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | David G. Harris 0001, Johannes Schneider 0002, Hsin-Hao Su |
Distributed (∆+1)-coloring in sublogarithmic rounds. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel Wichs, Yishay Mansour (eds.) |
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016 |
STOC |
2016 |
DBLP BibTeX RDF |
|
| 1 | Shaddin Dughmi, Haifeng Xu |
Algorithmic Bayesian persuasion. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Julia Chuzhoy, David H. K. Kim, Shi Li 0001 |
Improved approximation for node-disjoint paths in planar graphs. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs |
Separations in query complexity based on pointer functions. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf |
High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity. |
STOC |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson 0001, David Zuckerman |
Rectangles Are Nonnegative Juntas. |
STOC |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Shiri Chechik |
Approximate Distance Oracles with Improved Bounds. |
STOC |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeyuan Allen Zhu, Lorenzo Orecchia |
Nearly-Linear Time Positive LP Solver with Faster Convergence Rate. |
STOC |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Daniely, Michael Schapira, Gal Shahaf |
Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension. |
STOC |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Elkin, Arnold Filtser, Ofer Neiman |
Prioritized Metric Structures and Embedding. |
STOC |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Aleksandar Nikolov |
Randomized Rounding for the Largest Simplex Problem. |
STOC |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Moritz Hardt, Eric Price 0001 |
Tight Bounds for Learning a Mixture of Two Gaussians. |
STOC |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Jean Bourgain, Sjoerd Dirksen, Jelani Nelson |
Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space. |
STOC |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Nitish Korula, Vahab S. Mirrokni, Morteza Zadimoghaddam |
Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order. |
STOC |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Tobias Christiani, Rasmus Pagh, Mikkel Thorup |
From Independence to Expansion and Back Again. |
STOC |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Irit Dinur, Prahladh Harsha, Guy Kindler |
Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition. |
STOC |
2015 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license