| 51 |
Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
Yin Tat Lee, He Sun
|
👻
Ghosted
|
cs.DS
|
105 |
10 years ago |
| 52 |
Parallel Graph Connectivity in Log Diameter Rounds
Alexandr Andoni, Clifford Stein, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
104 |
7 years ago |
| 53 |
First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate
Zeyuan Allen-Zhu, Yuanzhi Li
|
👻
Ghosted
|
math.OC
|
103 |
9 years ago |
| 54 |
Hashing-Based-Estimators for Kernel Density in High Dimensions
Moses Charikar, Paris Siminelakis
|
👻
Ghosted
|
cs.DS
|
101 |
7 years ago |
| 55 |
Eldan's Stochastic Localization and the KLS Conjecture: Isoperimetry, Concentration and Mixing
Yin Tat Lee, Santosh S. Vempala
|
👻
Ghosted
|
math.FA
|
98 |
9 years ago |
| 56 |
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning
Ran Raz
|
👻
Ghosted
|
cs.LG
|
97 |
10 years ago |
| 57 |
How to refute a random CSP
Sarah R. Allen, Ryan O'Donnell, David Witmer
|
🔮
The Ethereal
|
cs.CC
|
95 |
10 years ago |
| 58 |
Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors
Kuan Cheng, Zhengzhong Jin, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
93 |
8 years ago |
| 59 |
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time
Diptarka Chakraborty, Debarati Das, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
92 |
7 years ago |
| 60 |
Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization
Ahmed El Alaoui, Andrea Montanari, Mark Sellke
|
👻
Ghosted
|
math.PR
|
92 |
4 years ago |
| 61 |
Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension
Christian Sohler, David P. Woodruff
|
👻
Ghosted
|
cs.DS
|
91 |
7 years ago |
| 62 |
Polynomial Representations of Threshold Functions and Algorithmic Applications
Josh Alman, Timothy M. Chan, Ryan Williams
|
👻
Ghosted
|
cs.DS
|
89 |
9 years ago |
| 63 |
A New Framework for Distributed Submodular Maximization
Rafael da Ponte Barbosa, Alina Ene, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
89 |
10 years ago |
| 64 |
Max-Information, Differential Privacy, and Post-Selection Hypothesis Testing
Ryan Rogers, Aaron Roth, ... (+2 more)
|
👻
Ghosted
|
cs.LG
|
88 |
10 years ago |
| 65 |
Constrained Submodular Maximization: Beyond 1/e
Alina Ene, Huy L. Nguyen
|
👻
Ghosted
|
cs.DS
|
87 |
9 years ago |
| 66 |
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths
Michael Elkin, Ofer Neiman
|
👻
Ghosted
|
cs.DS
|
86 |
9 years ago |
| 67 |
An Equivalence Between Private Classification and Online Prediction
Mark Bun, Roi Livni, Shay Moran
|
👻
Ghosted
|
cs.LG
|
85 |
6 years ago |
| 68 |
Resolving the Optimal Metric Distortion Conjecture
Vasilis Gkatzelis, Daniel Halpern, Nisarg Shah
|
👻
Ghosted
|
cs.GT
|
85 |
6 years ago |
| 69 |
Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching
Manuela Fischer, Mohsen Ghaffari, Fabian Kuhn
|
👻
Ghosted
|
cs.DS
|
85 |
9 years ago |
| 70 |
Heavy hitters via cluster-preserving clustering
Kasper Green Larsen, Jelani Nelson, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
85 |
10 years ago |
| 71 |
Planting Undetectable Backdoors in Machine Learning Models
Shafi Goldwasser, Michael P. Kim, ... (+2 more)
|
👻
Ghosted
|
cs.LG
|
85 |
4 years ago |
| 72 |
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
Zongchen Chen, Kuikui Liu, Eric Vigoda
|
👻
Ghosted
|
cs.DS
|
82 |
6 years ago |
| 73 |
Tight Lower Bounds for Differentially Private Selection
Thomas Steinke, Jonathan Ullman
|
👻
Ghosted
|
cs.DS
|
82 |
9 years ago |
| 74 |
Optimal repair of Reed-Solomon codes: Achieving the cut-set bound
Itzhak Tamo, Min Ye, Alexander Barg
|
👻
Ghosted
|
cs.IT
|
82 |
8 years ago |
| 75 |
Verifiable Quantum Advantage without Structure
Takashi Yamakawa, Mark Zhandry
|
👻
Ghosted
|
quant-ph
|
82 |
4 years ago |
| 76 |
$\varepsilon$-Coresets for Clustering (with Outliers) in Doubling Metrics
Lingxiao Huang, Shaofeng H. -C. Jiang, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
81 |
8 years ago |
| 77 |
Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization
Maria-Florina Balcan, Travis Dick, Ellen Vitercik
|
👻
Ghosted
|
cs.LG
|
81 |
8 years ago |
| 78 |
On Fully Dynamic Graph Sparsifiers
Ittai Abraham, David Durfee, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
81 |
10 years ago |
| 79 |
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow
Jan van den Brand, Li Chen, ... (+6 more)
|
👻
Ghosted
|
cs.DS
|
78 |
2 years ago |
| 80 |
Edge-Weighted Online Bipartite Matching
Matthew Fahrbach, Zhiyi Huang, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
78 |
5 years ago |
| 81 |
Computationally-secure and composable remote state preparation
Alexandru Gheorghiu, Thomas Vidick
|
👻
Ghosted
|
quant-ph
|
77 |
7 years ago |
| 82 |
Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes
Peter Bürgisser, Cole Franks, ... (+4 more)
|
👻
Ghosted
|
math.OC
|
77 |
6 years ago |
| 83 |
Input Sparsity and Hardness for Robust Subspace Approximation
Kenneth L. Clarkson, David P. Woodruff
|
👻
Ghosted
|
cs.DS
|
76 |
10 years ago |
| 84 |
Online Matching with General Arrivals
Buddhima Gamlath, Michael Kapralov, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
75 |
7 years ago |
| 85 |
On Learning Mixtures of Well-Separated Gaussians
Oded Regev, Aravindan Vijayaraghavan
|
👻
Ghosted
|
cs.DS
|
75 |
8 years ago |
| 86 |
Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product
Karl Bringmann, Fabrizio Grandoni, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
75 |
8 years ago |
| 87 |
Learning in Auctions: Regret is Hard, Envy is Easy
Constantinos Daskalakis, Vasilis Syrgkanis
|
👻
Ghosted
|
cs.GT
|
75 |
10 years ago |
| 88 |
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time
Soheil Behnezhad, Mahsa Derakhshan, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
74 |
6 years ago |
| 89 |
The Kikuchi Hierarchy and Tensor PCA
Alexander S. Wein, Ahmed El Alaoui, Cristopher Moore
|
👻
Ghosted
|
cs.DS
|
74 |
7 years ago |
| 90 |
Modified log-Sobolev inequalities for strongly log-concave distributions
Mary Cryan, Heng Guo, Giorgos Mousa
|
👻
Ghosted
|
math.PR
|
74 |
7 years ago |
| 91 |
Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds
Jan van den Brand, Danupon Nanongkai, Thatchaphol Saranurak
|
👻
Ghosted
|
cs.DS
|
73 |
6 years ago |
| 92 |
Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms
Amir Abboud, Søren Dahlgaard
|
👻
Ghosted
|
cs.DS
|
73 |
9 years ago |
| 93 |
Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition
Mohsen Ghaffari, Fabian Kuhn
|
👻
Ghosted
|
cs.DS
|
71 |
5 years ago |
| 94 |
Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions
Timothy Chu, Yu Gao, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
71 |
7 years ago |
| 95 |
Learning Multi-item Auctions with (or without) Samples
Yang Cai, Constantinos Daskalakis
|
👻
Ghosted
|
cs.GT
|
71 |
8 years ago |
| 96 |
Active classification with comparison queries
Daniel M. Kane, Shachar Lovett, ... (+2 more)
|
👻
Ghosted
|
cs.LG
|
71 |
9 years ago |
| 97 |
Optimal Auctions vs. Anonymous Pricing
Saeed Alaei, Jason Hartline, ... (+3 more)
|
👻
Ghosted
|
cs.GT
|
71 |
10 years ago |
| 98 |
Balancing Straight-Line Programs
Moses Ganardi, Artur Jeż, Markus Lohrey
|
👻
Ghosted
|
cs.DS
|
70 |
7 years ago |
| 99 |
Optimal Document Exchange and New Codes for Insertions and Deletions
Bernhard Haeupler
|
👻
Ghosted
|
cs.DS
|
70 |
8 years ago |
| 100 |
Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators
David P. Woodruff, Samson Zhou
|
👻
Ghosted
|
cs.DS
|
69 |
5 years ago |