| 1 |
Graph Isomorphism in Quasipolynomial Time
László Babai
|
👻
Ghosted
|
cs.DS
|
616 |
10 years ago |
| 2 |
Katyusha: The First Direct Acceleration of Stochastic Gradient Methods
Zeyuan Allen-Zhu
|
👻
Ghosted
|
math.OC
|
613 |
10 years ago |
| 3 |
Local, Private, Efficient Protocols for Succinct Histograms
Raef Bassily, Adam Smith
|
👻
Ghosted
|
cs.CR
|
493 |
11 years ago |
| 4 |
Solving Linear Programs in the Current Matrix Multiplication Time
Michael B. Cohen, Yin Tat Lee, Zhao Song
|
👻
Ghosted
|
cs.DS
|
355 |
7 years ago |
| 5 |
User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
Arnak S. Dalalyan, Avetik G. Karagulyan
|
👻
Ghosted
|
math.ST
|
319 |
8 years ago |
| 6 |
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
Monika Henzinger, Sebastian Krinninger, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
313 |
10 years ago |
| 7 |
Optimal Data-Dependent Hashing for Approximate Near Neighbors
Alexandr Andoni, Ilya Razenshteyn
|
👻
Ghosted
|
cs.DS
|
311 |
11 years ago |
| 8 |
Learning from Untrusted Data
Moses Charikar, Jacob Steinhardt, Gregory Valiant
|
👻
Ghosted
|
cs.LG
|
310 |
9 years ago |
| 9 |
Efficient quantum tomography II
Ryan O'Donnell, John Wright
|
👻
Ghosted
|
quant-ph
|
310 |
9 years ago |
| 10 |
Algorithmic Stability for Adaptive Data Analysis
Raef Bassily, Kobbi Nissim, ... (+4 more)
|
👻
Ghosted
|
cs.LG
|
290 |
10 years ago |
| 11 |
Private Stochastic Convex Optimization: Optimal Rates in Linear Time
Vitaly Feldman, Tomer Koren, Kunal Talwar
|
👻
Ghosted
|
cs.LG
|
227 |
5 years ago |
| 12 |
Stochastic bandits robust to adversarial corruptions
Thodoris Lykouris, Vahab Mirrokni, Renato Paes Leme
|
👻
Ghosted
|
cs.LG
|
220 |
8 years ago |
| 13 |
Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization
Václav Rozhoň, Mohsen Ghaffari
|
👻
Ghosted
|
cs.DS
|
213 |
6 years ago |
| 14 |
Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid
Nima Anari, Kuikui Liu, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
212 |
7 years ago |
| 15 |
A cost function for similarity-based hierarchical clustering
Sanjoy Dasgupta
|
👻
Ghosted
|
cs.DS
|
205 |
10 years ago |
| 16 |
Mixture Models, Robustness, and Sum of Squares Proofs
Samuel B. Hopkins, Jerry Li
|
👻
Ghosted
|
cs.DS
|
192 |
8 years ago |
| 17 |
Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality
Mark Braverman, Ankit Garg, ... (+3 more)
|
👻
Ghosted
|
cs.LG
|
184 |
10 years ago |
| 18 |
Geometric Median in Nearly Linear Time
Michael B. Cohen, Yin Tat Lee, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
182 |
9 years ago |
| 19 |
Fiber Bundle Codes: Breaking the $N^{1/2} \operatorname{polylog}(N)$ Barrier for Quantum LDPC Codes
Matthew B. Hastings, Jeongwan Haah, Ryan O'Donnell
|
👻
Ghosted
|
quant-ph
|
168 |
5 years ago |
| 20 |
Kernel-based methods for bandit convex optimization
Sébastien Bubeck, Ronen Eldan, Yin Tat Lee
|
👻
Ghosted
|
cs.LG
|
168 |
9 years ago |
| 21 |
A (Slightly) Improved Approximation Algorithm for Metric TSP
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
|
👻
Ghosted
|
cs.DS
|
165 |
5 years ago |
| 22 |
List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
|
👻
Ghosted
|
cs.DS
|
155 |
8 years ago |
| 23 |
Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
Sayan Bhattacharya, Monika Henzinger, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
153 |
11 years ago |
| 24 |
Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
Nai-Hui Chia, András Gilyén, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
152 |
6 years ago |
| 25 |
Homomorphisms Are a Good Basis for Counting Small Subgraphs
Radu Curticapean, Holger Dell, Dániel Marx
|
👻
Ghosted
|
cs.DS
|
152 |
8 years ago |
| 26 |
On the Complexity of Local Distributed Graph Problems
Mohsen Ghaffari, Fabian Kuhn, Yannic Maus
|
👻
Ghosted
|
cs.DS
|
150 |
9 years ago |
| 27 |
At the Roots of Dictionary Compression: String Attractors
Dominik Kempa, Nicola Prezza
|
👻
Ghosted
|
cs.DS
|
149 |
8 years ago |
| 28 |
Private Selection from Private Candidates
Jingcheng Liu, Kunal Talwar
|
👻
Ghosted
|
cs.DS
|
146 |
7 years ago |
| 29 |
Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering
Konstantin Makarychev, Yury Makarychev, Ilya Razenshteyn
|
👻
Ghosted
|
cs.DS
|
146 |
7 years ago |
| 30 |
Complexity Theoretic Limitations on Learning Halfspaces
Amit Daniely
|
🔮
The Ethereal
|
cs.CC
|
146 |
10 years ago |
| 31 |
Calibrated Language Models Must Hallucinate
Adam Tauman Kalai, Santosh S. Vempala
|
👻
Ghosted
|
cs.CL
|
146 |
2 years ago |
| 32 |
A Lower Bound for the Distributed Lovász Local Lemma
Sebastian Brandt, Orr Fischer, ... (+6 more)
|
👻
Ghosted
|
cs.DC
|
144 |
10 years ago |
| 33 |
Clustered Integer 3SUM via Additive Combinatorics
Timothy M. Chan, Moshe Lewenstein
|
👻
Ghosted
|
cs.DS
|
143 |
11 years ago |
| 34 |
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion
Zongchen Chen, Kuikui Liu, Eric Vigoda
|
🔮
The Ethereal
|
cs.DM
|
142 |
5 years ago |
| 35 |
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
Samuel B. Hopkins, Tselil Schramm, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
142 |
10 years ago |
| 36 |
Learning Mixtures of Gaussians in High Dimensions
Rong Ge, Qingqing Huang, Sham M. Kakade
|
👻
Ghosted
|
cs.LG
|
132 |
11 years ago |
| 37 |
Sparsified Cholesky and Multigrid Solvers for Connection Laplacians
Rasmus Kyng, Yin Tat Lee, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
131 |
10 years ago |
| 38 |
Randomized Composable Core-sets for Distributed Submodular Maximization
Vahab Mirrokni, Morteza Zadimoghaddam
|
👻
Ghosted
|
cs.DS
|
129 |
10 years ago |
| 39 |
Simple Mechanisms for Subadditive Buyers via Duality
Yang Cai, Mingfei Zhao
|
👻
Ghosted
|
cs.GT
|
125 |
9 years ago |
| 40 |
Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made
Amir Abboud, Thomas Dueholm Hansen, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
125 |
10 years ago |
| 41 |
Constant Approximation for $k$-Median and $k$-Means with Outliers via Iterative Rounding
Ravishankar Krishnaswamy, Shi Li, Sai Sandeep
|
👻
Ghosted
|
cs.DS
|
124 |
8 years ago |
| 42 |
Private PAC learning implies finite Littlestone dimension
Noga Alon, Roi Livni, ... (+2 more)
|
👻
Ghosted
|
cs.LG
|
123 |
7 years ago |
| 43 |
When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?
Gavin Brown, Mark Bun, ... (+3 more)
|
👻
Ghosted
|
cs.LG
|
121 |
5 years ago |
| 44 |
Optimal Principal Component Analysis in Distributed and Streaming Models
Christos Boutsidis, David P. Woodruff, Peilin Zhong
|
👻
Ghosted
|
cs.DS
|
121 |
10 years ago |
| 45 |
Sum-of-squares lower bounds for planted clique
Raghu Meka, Aaron Potechin, Avi Wigderson
|
🔮
The Ethereal
|
cs.CC
|
119 |
11 years ago |
| 46 |
Beyond matroids: Secretary Problem and Prophet Inequality with general constraints
Aviad Rubinstein
|
👻
Ghosted
|
cs.DS
|
118 |
10 years ago |
| 47 |
An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications
Haotian Jiang, Yin Tat Lee, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
117 |
6 years ago |
| 48 |
The Sample Complexity of Auctions with Side Information
Nikhil R. Devanur, Zhiyi Huang, Christos-Alexandros Psomas
|
👻
Ghosted
|
cs.GT
|
117 |
10 years ago |
| 49 |
Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation
Yin Tat Lee, Santosh S. Vempala
|
👻
Ghosted
|
cs.DS
|
116 |
8 years ago |
| 50 |
Hardness of Approximate Nearest Neighbor Search
Aviad Rubinstein
|
🔮
The Ethereal
|
cs.CC
|
112 |
8 years ago |