| 1 |
Robust Estimators in High Dimensions without the Computational Intractability
Ilias Diakonikolas, Gautam Kamath, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
539 |
10 years ago |
| 2 |
Agnostic Estimation of Mean and Covariance
Kevin A. Lai, Anup B. Rao, Santosh Vempala
|
👻
Ghosted
|
cs.DS
|
361 |
10 years ago |
| 3 |
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
Li Chen, Rasmus Kyng, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
322 |
4 years ago |
| 4 |
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization
Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong
|
👻
Ghosted
|
cs.DS
|
313 |
10 years ago |
| 5 |
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
Karl Bringmann, Marvin Künnemann
|
🔮
The Ethereal
|
cs.CC
|
259 |
11 years ago |
| 6 |
Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs
Charles Bordenave, Marc Lelarge, Laurent Massoulié
|
👻
Ghosted
|
math.PR
|
255 |
11 years ago |
| 7 |
Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms
Sara Ahmadian, Ashkan Norouzi-Fard, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
250 |
9 years ago |
| 8 |
Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
|
👻
Ghosted
|
cs.LG
|
243 |
9 years ago |
| 9 |
Twin-width I: tractable FO model checking
Édouard Bonnet, Eun Jung Kim, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
220 |
5 years ago |
| 10 |
Quantum SDP-Solvers: Better upper and lower bounds
Joran van Apeldoorn, András Gilyén, ... (+2 more)
|
👻
Ghosted
|
quant-ph
|
213 |
8 years ago |
| 11 |
Differentially Private Release and Learning of Threshold Functions
Mark Bun, Kobbi Nissim, ... (+2 more)
|
👻
Ghosted
|
cs.CR
|
210 |
10 years ago |
| 12 |
Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple
Rasmus Kyng, Sushant Sachdeva
|
👻
Ghosted
|
cs.DS
|
206 |
9 years ago |
| 13 |
Privacy Amplification by Iteration
Vitaly Feldman, Ilya Mironov, ... (+2 more)
|
👻
Ghosted
|
cs.LG
|
198 |
7 years ago |
| 14 |
Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling
Vitaly Feldman, Audra McMillan, Kunal Talwar
|
👻
Ghosted
|
cs.LG
|
183 |
5 years ago |
| 15 |
Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs
Paul Dütting, Michal Feldman, ... (+2 more)
|
👻
Ghosted
|
cs.GT
|
180 |
9 years ago |
| 16 |
A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents
Haris Aziz, Simon Mackenzie
|
👻
Ghosted
|
cs.DS
|
178 |
10 years ago |
| 17 |
An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie
|
🔮
The Ethereal
|
cs.CC
|
177 |
10 years ago |
| 18 |
Classical Homomorphic Encryption for Quantum Circuits
Urmila Mahadev
|
👻
Ghosted
|
quant-ph
|
176 |
8 years ago |
| 19 |
Efficient Inverse Maintenance and Faster Algorithms for Linear Programming
Yin Tat Lee, Aaron Sidford
|
👻
Ghosted
|
cs.DS
|
171 |
11 years ago |
| 20 |
Feature Purification: How Adversarial Training Performs Robust Deep Learning
Zeyuan Allen-Zhu, Yuanzhi Li
|
👻
Ghosted
|
cs.LG
|
170 |
5 years ago |
| 21 |
Optimality of the Johnson-Lindenstrauss Lemma
Kasper Green Larsen, Jelani Nelson
|
👻
Ghosted
|
cs.IT
|
167 |
9 years ago |
| 22 |
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
Nima Anari, Kuikui Liu, Shayan Oveis Gharan
|
👻
Ghosted
|
cs.DS
|
161 |
6 years ago |
| 23 |
A Faster Interior Point Method for Semidefinite Programming
Haotian Jiang, Tarun Kathuria, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
149 |
5 years ago |
| 24 |
The power of sum-of-squares for detecting hidden structures
Samuel B. Hopkins, Pravesh K. Kothari, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
149 |
8 years ago |
| 25 |
Approximately Counting Triangles in Sublinear Time
Talya Eden, Amit Levi, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
148 |
11 years ago |
| 26 |
Fully Dynamic Maximal Matching in Constant Update Time
Shay Solomon
|
👻
Ghosted
|
cs.DS
|
144 |
9 years ago |
| 27 |
On Derandomizing Local Distributed Algorithms
Mohsen Ghaffari, David G. Harris, Fabian Kuhn
|
👻
Ghosted
|
cs.DS
|
142 |
8 years ago |
| 28 |
Local Conflict Coloring
Pierre Fraigniaud, Marc Heinrich, Adrian Kosowski
|
👻
Ghosted
|
cs.DS
|
142 |
10 years ago |
| 29 |
Faster Matrix Multiplication via Asymmetric Hashing
Ran Duan, Hongxun Wu, Renfei Zhou
|
👻
Ghosted
|
cs.DS
|
142 |
3 years ago |
| 30 |
Constant overhead quantum fault-tolerance with quantum expander codes
Omar Fawzi, Antoine Grospellier, Anthony Leverrier
|
👻
Ghosted
|
quant-ph
|
138 |
7 years ago |
| 31 |
Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics
Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu
|
👻
Ghosted
|
cs.DS
|
137 |
10 years ago |
| 32 |
Local Search Yields a PTAS for k-Means in Doubling Metrics
Zachary Friggstad, Mohsen Rezapour, Mohammad R. Salavatipour
|
👻
Ghosted
|
cs.DS
|
134 |
10 years ago |
| 33 |
Adversarial Bandits with Knapsacks
Nicole Immorlica, Karthik Abinav Sankararaman, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
129 |
7 years ago |
| 34 |
If the Current Clique Algorithms are Optimal, so is Valiant's Parser
Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
|
🔮
The Ethereal
|
cs.CC
|
129 |
11 years ago |
| 35 |
Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time
Danupon Nanongkai, Thatchaphol Saranurak, Christian Wulff-Nilsen
|
👻
Ghosted
|
cs.DS
|
126 |
8 years ago |
| 36 |
Polynomial-time Tensor Decompositions with Sum-of-Squares
Tengyu Ma, Jonathan Shi, David Steurer
|
👻
Ghosted
|
cs.DS
|
125 |
9 years ago |
| 37 |
Computing Maximum Flow with Augmenting Electrical Flows
Aleksander Madry
|
👻
Ghosted
|
cs.DS
|
125 |
9 years ago |
| 38 |
Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing
Elizabeth Crosson, Aram W. Harrow
|
👻
Ghosted
|
quant-ph
|
124 |
10 years ago |
| 39 |
Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods
Michael B. Cohen, Aleksander Madry, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
121 |
9 years ago |
| 40 |
Quantum Expander Codes
Anthony Leverrier, Jean-Pierre Tillich, Gilles Zémor
|
👻
Ghosted
|
quant-ph
|
121 |
11 years ago |
| 41 |
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
Julia Chuzhoy, Yu Gao, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
120 |
6 years ago |
| 42 |
Much Faster Algorithms for Matrix Scaling
Zeyuan Allen-Zhu, Yuanzhi Li, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
119 |
9 years ago |
| 43 |
Probabilistic Polynomials and Hamming Nearest Neighbors
Josh Alman, Ryan Williams
|
👻
Ghosted
|
cs.DS
|
119 |
10 years ago |
| 44 |
Learning Graphical Models Using Multiplicative Weights
Adam Klivans, Raghu Meka
|
👻
Ghosted
|
cs.LG
|
118 |
8 years ago |
| 45 |
Optimal Quantile Approximation in Streams
Zohar Karnin, Kevin Lang, Edo Liberty
|
👻
Ghosted
|
cs.DS
|
114 |
10 years ago |
| 46 |
Lower bounds for maximal matchings and maximal independent sets
Alkida Balliu, Sebastian Brandt, ... (+4 more)
|
👻
Ghosted
|
cs.DC
|
110 |
7 years ago |
| 47 |
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
|
👻
Ghosted
|
cs.DS
|
109 |
10 years ago |
| 48 |
Which Regular Expression Patterns are Hard to Match?
Arturs Backurs, Piotr Indyk
|
🔮
The Ethereal
|
cs.CC
|
109 |
10 years ago |
| 49 |
A Time Hierarchy Theorem for the LOCAL Model
Yi-Jun Chang, Seth Pettie
|
👻
Ghosted
|
cs.DC
|
108 |
9 years ago |
| 50 |
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
Jan van den Brand, Yin-Tat Lee, ... (+6 more)
|
👻
Ghosted
|
cs.DS
|
106 |
5 years ago |