| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Shir Peleg, Amir Shpilka |
Polynomial time deterministic identity testing algorithm for Σ[3]ΠΣΠ[2] circuits via Edelstein-Kelly type theorem for quadratic polynomials.  |
STOC  |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yair Bartal, Lee-Ad Gottlieb |
Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Lijie Chen 0001, Roei Tell |
Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Oren Mangoubi, Nisheeth K. Vishnoi |
Greedy adversarial equilibrium: an efficient alternative to nonconvex-nonconcave min-max optimization. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Blais, Renato Ferreira Pinto Jr., Nathaniel Harms |
VC dimension and distribution-free sample-based testing. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal |
Degree vs. approximate degree and Quantum implications of Huang's sensitivity theorem. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | András Gilyén, Matthew B. Hastings, Umesh V. Vazirani |
(Sub)Exponential advantage of adiabatic Quantum computation with no sign problem. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Will Perkins 0001, Changji Xu |
Frozen 1-RSB structure of the symmetric Ising perceptron. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu |
An optimal separation of randomized and Quantum query complexity. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Sitan Chen, Ankur Moitra |
Algorithmic foundations for the diffraction limit. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Aaron Bernstein, Aditi Dudeja, Zachary Langley |
A framework for dynamic matching in weighted graphs. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski |
Finding large induced sparse subgraphs in c>t -free graphs in quasipolynomial time. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Christopher Jung 0001, Katrina Ligett, Seth Neel, Aaron Roth 0001, Saeed Sharifi-Malvajerdi, Moshe Shenfeld |
A new analysis of differential privacy's generalization guarantees (invited paper). |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Jason Li 0006, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai |
Vertex connectivity in poly-logarithmic max-flows. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Vishesh Jain, Ashwin Sah, Mehtaab Sawhney |
Perfectly sampling k ≥ (8/3 + o(1))Δ-colorings in graphs. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Federica Cecchetto, Vera Traub, Rico Zenklusen |
Bridging the gap between tree and connectivity augmentation: unified and stronger approaches. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Bansal 0001, Makrand Sinha |
k-forrelation optimally separates Quantum and classical query complexity. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Jugal Garg, Edin Husic, László A. Végh |
Approximating Nash social welfare under rado valuations. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Sally Dong, Yin Tat Lee, Guanghao Ye |
A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Alon Gonen, Elad Hazan, Shay Moran |
Boosting simple learners. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Zander Kelley |
An improved derandomization of the switching lemma. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis |
Efficiently learning halfspaces with Tsybakov noise. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Jason Li 0006 |
Deterministic mincut in almost-linear time. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Allen Liu, Ankur Moitra |
Settling the robust learnability of mixtures of Gaussians. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Abboud, Robert Krauthgamer, Ohad Trabelsi |
Subcubic algorithms for Gomory-Hu tree in unweighted graphs. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Karl Bringmann, Nick Fischer, Vasileios Nakos |
Sparse nonnegative convolution is equivalent to dense nonnegative convolution. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai |
Distributed weighted min-cut in nearly-optimal time. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Gavin Brown 0003, Mark Bun, Vitaly Feldman, Adam D. Smith, Kunal Talwar |
When is memorization of irrelevant training data necessary for high-accuracy learning? |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Seth Pettie, Dingyu Wang |
Information theoretic limits of cardinality estimation: Fisher meets Shannon. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Jonathan Leake, Colin S. McSwiggen, Nisheeth K. Vishnoi |
Sampling matrices from Harish-Chandra-Itzykson-Zuber densities with applications to Quantum inference and differential privacy. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Akshay Krishnamurthy, Thodoris Lykouris, Chara Podimata, Robert E. Schapire |
Contextual search in the presence of irrational agents. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Rahul Santhanam, Iddo Tzameret |
Iterated lower bound formulas: a diagonalization-based approach to proof complexity. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich |
Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Ján Pich, Rahul Santhanam |
Strong co-nondeterministic lower bounds for NP cannot be proved feasibly. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Bingkai Lin |
Constant approximating k-clique is w[1]-hard. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Rad Niazadeh, Renato Paes Leme, Jon Schneider |
Combinatorial Bernoulli factories: matchings, flows, and other polytopes. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, Eylon Yogev |
Adversarial laws of large numbers and optimal regret in online classification. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Leonid Gurvits, Jonathan Leake |
Capacity lower bounds via productization. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Mohsen Ghaffari 0001, Bernhard Haeupler, Goran Zuzic |
Hop-constrained oblivious routing. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Susanna F. de Rezende, Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov 0001 |
Automating algebraic proof systems is NP-hard. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Haitao Wang 0001 |
A new algorithm for Euclidean shortest paths in the plane. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, John Peebles, Eric Price 0001 |
Optimal testing of discrete distributions with high probability. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song 0002, Di Wang 0005 |
Minimum cost flows, MDPs, and ℓ1-regression in nearly linear time for dense instances. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | C. J. Argue, Anupam Gupta 0001, Guru Guruganesh, Ziye Tang |
Chasing convex bodies with linear competitive ratio (invited paper). |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Aviad Rubinstein, Junyao Zhao 0001 |
The randomized communication complexity of randomized auctions. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Constantinos Daskalakis, Stratis Skoulakis, Manolis Zampetakis |
The complexity of constrained min-max optimization. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Ray Li |
Settling SETH vs. approximate sparse directed unweighted diameter (up to (NU)NSETH). |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Leonid A. Levin |
Climbing algorithms (invited talk). |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Julia Chuzhoy |
Decremental all-pairs shortest paths in deterministic near-linear time. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Antonio Blanca, Pietro Caputo, Daniel Parisi, Alistair Sinclair, Eric Vigoda |
Entropy decay in the Swendsen-Wang dynamics on ℤd. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Mitali Bafna, Boaz Barak, Pravesh K. Kothari, Tselil Schramm, David Steurer |
Playing unique games on certified small-set expanders. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yakov Babichenko, Aviad Rubinstein |
Settling the complexity of Nash equilibrium in congestion games. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Fernando Granha Jeronimo, Shashank Srivastava, Madhur Tulsiani |
Near-linear time decoding of Ta-Shma's codes via splittable regularity. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Vijay Bhattiprolu, Euiwoong Lee, Assaf Naor |
A framework for quadratic form maximization over convex sets through nonconvex relaxations. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Arnold Filtser, Hung Le 0001 |
Clan embeddings into trees, and low treewidth graphs. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Mingda Qiao, Gregory Valiant |
Stronger calibration lower bounds via sidestepping. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Zachary Chase 0001 |
Separating words and trace reconstruction. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Lijie Chen 0001, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song 0002, Huacheng Yu |
Almost optimal super-constant-pass streaming lower bounds for reachability. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yanyi Liu, Rafael Pass |
Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Pawel Gawrychowski, Wojciech Janczewski |
Fully dynamic approximation of LIS in polylogarithmic time. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena |
Optimal error resilience of adaptive message exchange. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Ainesh Bakshi, Adarsh Prasad |
Robust linear regression: optimal rates in polynomial time. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Romain Gay, Rafael Pass |
Indistinguishability obfuscation from circular security. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Lars Rohwedder, Andreas Wiese |
A (2 + ε)-approximation algorithm for preemptive weighted flow time on a single machine. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, Cristian Riveros |
When is approximate counting for conjunctive queries tractable? |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Gal Beniamini, Noam Nisan |
Bipartite perfect matching as a real polynomial. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Jason Li 0006, Debmalya Panigrahi |
Approximate Gomory-Hu tree is faster than n - 1 max-flows. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman, Dor Minzer |
New separations results for external information. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Weiming Feng 0001, Kun He 0011, Yitong Yin |
Sampling constraint satisfaction solutions in the local lemma regime. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yossi Azar, Stefano Leonardi 0001, Noam Touitou |
Flow time scheduling with uncertain processing time. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Maria-Florina Balcan, Dan F. DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, Ellen Vitercik |
How much data is sufficient to learn high-performing algorithms? generalization guarantees for data-driven algorithm design. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Josh Alman |
Kronecker products, low-depth circuits, and matrix rigidity. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Isaac Grosof, Ziv Scully, Mor Harchol-Balter |
Load balancing guardrails: keeping your heavy traffic on the road to low response times (invited paper). |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Natan Rubin |
Stronger bounds for weak epsilon-nets in higher dimensions. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas, S. Matthew Weinberg, Junyao Zhao 0001 |
Exponential communication separations between notions of selfishness. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Shahar Dobzinski, Shiri Ron |
The communication complexity of payment computation. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Nima Anari, Cynthia Vinzant |
Log-concave polynomials in theory and applications (tutorial). |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Justin Holmgren, Alex Lombardi, Ron D. Rothblum |
Fiat-Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge). |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida |
Towards tight bounds for spectral sparsification of hypergraphs. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Nike Sun |
Statistical physics of random CSPs (tutorial). |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Samir Khuller, Virginia Vassilevska Williams (eds.) |
STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Jiayu Zhang |
Succinct blind Quantum computation using a random oracle. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan 0002 |
Log-rank and lifting for AND-functions. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Arnab Bhattacharyya 0001, Sutanu Gayen, Eric Price 0001, N. V. Vinodchandran |
Near-optimal learning of tree-structured distributions by Chow-Liu. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Arthur Jacot, Franck Gabriel, Clément Hongler |
Neural tangent kernel: convergence and generalization in neural networks (invited paper). |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan Alweiss, Yang P. Liu, Mehtaab Sawhney |
Discrepancy minimization via a self-balancing walk. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yiding Feng, Jason D. Hartline, Yingkai Li |
Revelation gap for pricing from samples. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, Cristian Riveros |
A polynomial-time approximation algorithm for counting words accepted by an NFA (invited paper). |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Alex Cohen, Guy Moshkovitz |
Structure vs. randomness for bilinear maps. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | William Kuszmaul |
How asymmetry helps buffer management: achieving optimal tail size in cup games. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Bernhard Haeupler, David Wajc, Goran Zuzic |
Universally-optimal distributed algorithms for known topologies. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Gil Cohen, Noam Peri, Amnon Ta-Shma |
Expander random walks: a Fourier-analytic approach. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Shunhua Jiang, Zhao Song 0002, Omri Weinstein, Hengjie Zhang |
A faster algorithm for solving general LPs. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Eddie Aamari, Alexander Knop |
Statistical query complexity of manifold estimation. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Anders Aamand, Jakob Bæk Tejs Knudsen, Mikkel Thorup |
Load balancing with dynamic set of balls and bins. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Amey Bhangale, Subhash Khot |
Optimal inapproximability of satisfiable k-LIN over non-abelian groups. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, Tigran Tonoyan |
Efficient randomized distributed coloring in CONGEST. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Albert Cheu, Jonathan R. Ullman |
The limits of pan privacy and shuffle privacy for learning and estimation. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Badih Ghazi, Noah Golowich, Ravi Kumar 0001, Pasin Manurangsi |
Sample-efficient proper PAC learning with approximate differential privacy. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Nachum Dershowitz, Rotem Oshman, Tal Roth |
The communication complexity of multiparty set disjointness under product distributions. |
STOC |
2021 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license