| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, Rico Zenklusen |
The one-way communication complexity of submodular maximization with applications to streaming and robustness.  |
STOC  |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Václav Rozhon, Mohsen Ghaffari 0001 |
Polylogarithmic-time deterministic network decomposition and distributed derandomization. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Anupam Gupta 0001, Amit Kumar 0001, Debmalya Panigrahi |
Caching with time windows. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath 0001, Julia Chuzhoy (eds.) |
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020 |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Lijie Chen 0001, Ce Jin 0001, R. Ryan Williams |
Sharp threshold results for computational complexity. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Sepehr Assadi, Chen Wang 0027 |
Exploration with limited memory: streaming algorithms for coin tossing, noisy comparisons, and multi-armed bandits. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes 0002 |
Explicit near-Ramanujan graphs of every degree. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret |
Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative? |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Michal Koucký 0001, Michael E. Saks |
Constant factor approximations to edit distance on far input pairs in nearly linear time. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | David R. Karger |
A phase transition and a quadratic time unbiased estimator for network reliability. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Rong Ge 0001, Holden Lee, Jianfeng Lu 0001 |
Estimating normalizing constants for log-concave distributions: algorithms and lower bounds. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Jaroslaw Byrka, Fabrizio Grandoni 0001, Afrouz Jabal Ameli |
Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | James Cook, Ian Mertz |
Catalytic approaches to the tree evaluation problem. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Jonathan Leake, Nisheeth K. Vishnoi |
On the computability of continuous maximum entropy distributions with applications. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Wenzheng Li, Paul Liu 0001, Jan Vondrák |
A polynomial lower bound on adaptive complexity of submodular maximization. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Lijie Chen 0001, Hanlin Ren |
Strong average-case lower bounds from non-trivial derandomization. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Shachar Lovett, Kewen Wu 0001, Jiapeng Zhang |
Decision list compression by mild random restrictions. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander Edmonds, Aleksandar Nikolov, Jonathan R. Ullman |
The power of factorization mechanisms in local and central differential privacy. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Jesper Nederlof |
Detecting and counting small patterns in planar graphs in subexponential parameterized time. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena |
Interactive error resilience beyond 2/7. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | John Kallaugher, Eric Price 0001 |
Separations and equivalences between turnstile streaming and linear sketching. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Vedat Levi Alev, Lap Chi Lau |
Improved analysis of higher order random walks and applications. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel Dadush, Sophie Huiberts, Bento Natura, László A. Végh |
A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Balkanski, Yaron Singer |
A lower bound for parallel submodular minimization. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Xue Chen 0001, Anindya De, Rocco A. Servedio |
Testing noisy linear functions for sparsity. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein |
New algorithms and hardness for incremental single-source shortest paths in directed graphs. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Matthew Coudron, Sanketh Menda |
Computations with greater quantum depth are strictly more powerful (relative to an oracle). |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Dmitry Sokolov 0001 |
(Semi)Algebraic proofs over ±1 variables. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Dhiraj Holden, Yael Tauman Kalai |
Non-signaling proofs with o(√ log n) provers are in PSPACE. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuval Dagan, Vitaly Feldman |
Interaction is necessary for distributed learning with privacy or communication constraints. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Bansal 0001, Haotian Jiang, Sahil Singla 0001, Makrand Sinha |
Online vector balancing and geometric discrepancy. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, Chunhao Wang |
Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Elazar Goldenberg, Aviad Rubinstein, Barna Saha |
Does preprocessing help in fast sequence comparisons? |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Dmitry Gavinsky |
Bare quantum simultaneity versus classical interactivity in communication complexity. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexandr Andoni, Clifford Stein 0001, Peilin Zhong |
Parallel approximate undirected shortest paths via low hop emulators. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Haotian Jiang, Yin Tat Lee, Zhao Song 0002, Sam Chiu-wai Wong |
An improved cutting plane method for convex optimization, convex-concave games, and its applications. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel Lokshtanov, Pranabendu Misra, Michal Pilipczuk, Saket Saurabh 0001, Meirav Zehavi |
An exponential time parameterized algorithm for planar disjoint paths. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Shiri Chechik, Sarel Cohen |
Distance sensitivity oracles with subcubic preprocessing time and fast query time. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Jacob Holm, Eva Rotenberg |
Fully-dynamic planarity testing in polylogarithmic time. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Sidhanth Mohanty, Prasad Raghavendra, Jeff Xu |
Lifting sum-of-squares lower bounds: degree-2 to degree-4. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Anders Aamand, Jakob Bæk Tejs Knudsen, Mathias Bæk Tejs Knudsen, Peter Michael Reichstein Rasmussen, Mikkel Thorup |
Fast hashing with strong concentration bounds. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Christian Borgs, Jennifer T. Chayes, Tyler Helmuth, Will Perkins 0001, Prasad Tetali |
Efficient sampling and counting algorithms for the Potts model on ℤᵈ at all temperatures. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Ronen Eldan, Renan Gross |
Concentration on the Boolean hypercube via pathwise stochastic analysis. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Saurabh Sawlani, Junxing Wang |
Near-optimal fully dynamic densest subgraph. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Bartlomiej Dudek 0001, Pawel Gawrychowski, Tatiana Starikovskaya |
All non-trivial variants of 3-LDT are equivalent. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Abboud, Vincent Cohen-Addad, Philip N. Klein |
New hardness results for planar graph problems in p and an algorithm for sparsest cut. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Kai-Yuan Lai 0001, Hsueh-I Lu, Mikkel Thorup |
Three-in-a-tree in near linear time. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Nai-Hui Chia, Kai-Min Chung, Ching-Yi Lai |
On the need for large quantum depth. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Huacheng Yu |
Nearly optimal static Las Vegas succinct dictionary. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan |
Fooling Gaussian PTFs via local hyperconcentration. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Sitan Chen, Jerry Li 0001, Ankur Moitra |
Efficiently learning structured distributions from untrusted batches. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Vitaly Feldman |
Does learning require memorization? a short tale about a long tail. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Joshua Brakensiek, Aviad Rubinstein |
Constant-factor approximation of near-linear edit distance in near-linear time. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Anurag Anshu, Itai Arad, David Gosset |
Entanglement subvolume law for 2d frustration-free spin systems. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, Vinod Vaikuntanathan |
Data structures meet cryptography: 3SUM with preprocessing. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Shuichi Hirahara |
Unexpected hardness results for Kolmogorov complexity under uniform reductions. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi |
Optimally resilient codes for list-decoding from insertions and deletions. |
STOC |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Thomas C. Bohdanowicz, Elizabeth Crosson, Chinmay Nirkhe, Henry Yuen |
Good approximate quantum LDPC codes from spacetime circuit Hamiltonians. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Hsin-Hao Su, Hoa T. Vu |
Towards the locality of Vizing's theorem. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai |
Breaking quadratic time for small vertex connectivity and an approximation scheme. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Yehudayoff |
Separating monotone VP and VNP. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael A. Bekos, Henry Förster, Martin Gronemann, Tamara Mchedlidze, Fabrizio Montecchiani, Chrysanthi N. Raftopoulou, Torsten Ueckerdt |
Planar graphs of bounded degree have bounded queue number. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Moses Charikar, Kirankumar Shiragur, Aaron Sidford |
Efficient profile maximum likelihood for universal symmetric property estimation. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Ankur Moitra, Alexander S. Wein |
Spectral methods from tensor networks. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Lin Chen 0003, Moran Feldman, Amin Karbasi |
Unconstrained submodular maximization with constant adaptive complexity. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Julia Chuzhoy, Sanjeev Khanna |
A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | János Pach, Natan Rubin, Gábor Tardos |
Planar point sets determine many pairwise crossing segments. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Yakov Babichenko, Shahar Dobzinski, Noam Nisan |
The communication complexity of local search. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Constantinos Daskalakis, Nishanth Dikkala, Ioannis Panageas |
Regression from dependent observations. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Vatsal Sharan, Aaron Sidford, Gregory Valiant |
Memory-sample tradeoffs for linear regression with small error. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Alireza Farhadi 0001, MohammadTaghi Hajiaghayi, Kasper Green Larsen, Elaine Shi |
Lower bounds for external memory integer sorting via network coding. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Pascal Schweitzer, Daniel Wiebking |
A unifying method for the design of algorithms canonizing combinatorial objects. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Mohit Daga, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak |
Distributed edge connectivity in sublinear time. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Anupam Gupta 0001, Euiwoong Lee, Jason Li 0006 |
The number of minimum k-cuts: improving the Karger-Stein bound. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Shyam Narayanan, Jelani Nelson |
Optimal terminal dimensionality reduction in Euclidean space. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Akash Kumar 0003, C. Seshadhri 0001, Andrew Stolman |
Random walks and forbidden minors II: a poly(d ε-1)-query tester for minor-closed properties of bounded degree graphs. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilias Diakonikolas, Daniel M. Kane |
Degree-푑 chow parameters robustly determine degree-푑 PTFs (and algorithmic applications). |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Moses Charikar, Edith Cohen (eds.) |
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019. |
STOC |
2019 |
DBLP BibTeX RDF |
|
| 1 | Daniel Dadush |
On approximating the covering radius and finding dense lattice subspaces. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Bartlomiej Dudek 0001, Pawel Gawrychowski |
Computing quartet distance is equivalent to counting 4-cycles. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | András Gilyén, Yuan Su, Guang Hao Low, Nathan Wiebe |
Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Chenghao Guo, Zhiyi Huang 0002, Xinzhi Zhang 0002 |
Settling the sample complexity of single-parameter revenue maximization. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Raghu Meka, Omer Reingold, Avishay Tal |
Pseudorandom generators for width-3 branching programs. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | László Babai |
Canonical form for graphs in quasipolynomial time: preliminary report. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Shachar Lovett, Jiapeng Zhang |
DNF sparsification beyond sunflowers. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant |
Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Lior Gishboliner, Asaf Shapira |
Testing graphs against an unknown distribution. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, Uri Zwick |
Faster k-SAT algorithms using biased-PPSZ. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni 0001, Debmalya Panigrahi, Barna Saha |
Dynamic set cover: improved algorithms and lower bounds. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Uri Hadar, Jingbo Liu, Yury Polyanskiy, Ofer Shayevitz |
Communication complexity of estimating correlations. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Weiming Feng 0001, Nisheeth K. Vishnoi, Yitong Yin |
Dynamic sampling from graphical models. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Clément L. Canonne, Gautam Kamath 0001, Audra McMillan, Adam D. Smith, Jonathan R. Ullman |
The structure of optimal private tests for simple hypotheses. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal |
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Neeraj Kayal, Chandan Saha 0001 |
Reconstruction of non-degenerate homogeneous depth three circuits. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann |
Almost optimal distance oracles for planar graphs. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Jakub Bulín, Andrei A. Krokhin, Jakub Oprsal |
Algebraic approach to promise constraint satisfaction. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Capalbo |
Explicit N-vertex graphs with maximum degree K and diameter [1+o(1)] logK-1 N for each K-1 a prime power. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich 0001 |
Testing graphs in vertex-distribution-free models. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni 0001, Chris Schwiegelshohn |
Oblivious dimension reduction for k-means: beyond subspaces and the Johnson-Lindenstrauss lemma. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Sitan Chen, Ankur Moitra |
Beyond the low-degree algorithm: mixtures of subcubes and their applications. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license