| 51 |
A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
|
👻
Ghosted
|
cs.DC
|
112 |
10 years ago |
| 52 |
Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and $O(n^{1/2-ε})$-Time
Danupon Nanongkai, Thatchaphol Saranurak
|
👻
Ghosted
|
cs.DS
|
107 |
9 years ago |
| 53 |
Fully-Dynamic Minimum Spanning Forest with Improved Worst-Case Update Time
Christian Wulff-Nilsen
|
👻
Ghosted
|
cs.DS
|
104 |
9 years ago |
| 54 |
Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs
Michael B. Cohen, Jonathan Kelner, ... (+5 more)
|
👻
Ghosted
|
cs.DS
|
104 |
9 years ago |
| 55 |
Improved Analysis of Higher Order Random Walks and Applications
Vedat Levi Alev, Lap Chi Lau
|
👻
Ghosted
|
cs.DS
|
103 |
6 years ago |
| 56 |
Round Compression for Parallel Matching Algorithms
Artur Czumaj, Jakub Łącki, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
103 |
8 years ago |
| 57 |
Solving Tall Dense Linear Programs in Nearly Linear Time
Jan van den Brand, Yin Tat Lee, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
100 |
6 years ago |
| 58 |
Quantum state certification
Costin Bădescu, Ryan O'Donnell, John Wright
|
👻
Ghosted
|
quant-ph
|
100 |
8 years ago |
| 59 |
New Deterministic Approximation Algorithms for Fully Dynamic Matching
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai
|
👻
Ghosted
|
cs.DS
|
100 |
10 years ago |
| 60 |
Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates
Zeyuan Allen-Zhu, Zhenyu Liao, Lorenzo Orecchia
|
👻
Ghosted
|
cs.LG
|
96 |
10 years ago |
| 61 |
Lossy Kernelization
Daniel Lokshtanov, Fahad Panolan, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
95 |
10 years ago |
| 62 |
Learning Geometric Concepts with Nasty Noise
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
|
👻
Ghosted
|
cs.LG
|
94 |
8 years ago |
| 63 |
An SDP-Based Algorithm for Linear-Sized Spectral Sparsification
Yin Tat Lee, He Sun
|
👻
Ghosted
|
cs.DS
|
92 |
9 years ago |
| 64 |
Bipartite Perfect Matching is in quasi-NC
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf
|
🔮
The Ethereal
|
cs.CC
|
91 |
10 years ago |
| 65 |
The Complexity of Gradient Descent: CLS = PPAD $\cap$ PLS
John Fearnley, Paul W. Goldberg, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
90 |
5 years ago |
| 66 |
k-server via multiscale entropic regularization
Sebastien Bubeck, Michael B. Cohen, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
90 |
8 years ago |
| 67 |
Online and Dynamic Algorithms for Set Cover
Anupam Gupta, Ravishankar Krishnaswamy, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
89 |
9 years ago |
| 68 |
Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
Zeyuan Allen-Zhu, Ankit Garg, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
88 |
8 years ago |
| 69 |
Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound
Bernhard Haeupler, Amirbehshad Shahrasbi
|
👻
Ghosted
|
cs.IT
|
88 |
9 years ago |
| 70 |
Strongly Refuting Random CSPs Below the Spectral Threshold
Prasad Raghavendra, Satish Rao, Tselil Schramm
|
👻
Ghosted
|
cs.DS
|
88 |
9 years ago |
| 71 |
How Robust are Reconstruction Thresholds for Community Detection?
Ankur Moitra, William Perry, Alexander S. Wein
|
👻
Ghosted
|
cs.DS
|
87 |
10 years ago |
| 72 |
The Structure of Optimal Private Tests for Simple Hypotheses
Clément L. Canonne, Gautam Kamath, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
86 |
7 years ago |
| 73 |
An Optimal Distributed $(Δ+1)$-Coloring Algorithm?
Yi-Jun Chang, Wenzheng Li, Seth Pettie
|
👻
Ghosted
|
cs.DC
|
86 |
8 years ago |
| 74 |
Uniform Sampling through the Lovász Local Lemma
Heng Guo, Mark Jerrum, Jingcheng Liu
|
👻
Ghosted
|
cs.DS
|
86 |
9 years ago |
| 75 |
Beating 1-1/e for Ordered Prophets
Melika Abolhasani, Soheil Ehsani, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
85 |
9 years ago |
| 76 |
Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal
Lingxiao Huang, Nisheeth K. Vishnoi
|
👻
Ghosted
|
cs.CG
|
83 |
6 years ago |
| 77 |
How to Match when All Vertices Arrive Online
Zhiyi Huang, Ning Kang, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
83 |
8 years ago |
| 78 |
Uniformly bounded regret in the multi-secretary problem
Alessandro Arlotto, Itai Gurvich
|
👻
Ghosted
|
math.PR
|
82 |
8 years ago |
| 79 |
Online Matching: Haste makes Waste!
Yuval Emek, Shay Kutten, Roger Wattenhofer
|
👻
Ghosted
|
cs.DS
|
81 |
10 years ago |
| 80 |
Faster Energy Maximization for Faster Maximum Flow
Yang P. Liu, Aaron Sidford
|
👻
Ghosted
|
cs.DS
|
79 |
6 years ago |
| 81 |
Distributed Exact Shortest Paths in Sublinear Time
Michael Elkin
|
👻
Ghosted
|
cs.DS
|
79 |
9 years ago |
| 82 |
Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs
Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra
|
🔮
The Ethereal
|
cs.CC
|
78 |
9 years ago |
| 83 |
Optimal mean-based algorithms for trace reconstruction
Anindya De, Ryan O'Donnell, Rocco Servedio
|
🔮
The Ethereal
|
cs.CC
|
77 |
9 years ago |
| 84 |
Sampling Random Spanning Trees Faster than Matrix Multiplication
David Durfee, Rasmus Kyng, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
76 |
9 years ago |
| 85 |
The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
Nikhil Bansal, Daniel Dadush, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
75 |
8 years ago |
| 86 |
Trace reconstruction with $\exp( O( n^{1/3} ) )$ samples
Fedor Nazarov, Yuval Peres
|
👻
Ghosted
|
math.PR
|
75 |
9 years ago |
| 87 |
Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order
Nitish Korula, Vahab Mirrokni, Morteza Zadimoghaddam
|
👻
Ghosted
|
cs.DS
|
74 |
8 years ago |
| 88 |
Robustly Learning Mixtures of $k$ Arbitrary Gaussians
Ainesh Bakshi, Ilias Diakonikolas, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
72 |
5 years ago |
| 89 |
Fully Dynamic Maximal Independent Set with Sublinear Update Time
Sepehr Assadi, Krzysztof Onak, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
72 |
8 years ago |
| 90 |
The Computational Power of Optimization in Online Learning
Elad Hazan, Tomer Koren
|
👻
Ghosted
|
cs.LG
|
72 |
11 years ago |
| 91 |
A Discrete and Bounded Envy-free Cake Cutting Protocol for Four Agents
Haris Aziz, Simon Mackenzie
|
👻
Ghosted
|
cs.DS
|
72 |
10 years ago |
| 92 |
A Theory of Universal Learning
Olivier Bousquet, Steve Hanneke, ... (+3 more)
|
👻
Ghosted
|
cs.LG
|
71 |
5 years ago |
| 93 |
An almost-linear time algorithm for uniform random spanning tree generation
Aaron Schild
|
👻
Ghosted
|
cs.DS
|
70 |
8 years ago |
| 94 |
The Power of Factorization Mechanisms in Local and Central Differential Privacy
Alexander Edmonds, Aleksandar Nikolov, Jonathan Ullman
|
👻
Ghosted
|
cs.DS
|
69 |
6 years ago |
| 95 |
Quadratic speedup for finding marked vertices by quantum walks
Andris Ambainis, András Gilyén, ... (+2 more)
|
👻
Ghosted
|
quant-ph
|
69 |
7 years ago |
| 96 |
Deterministic and Probabilistic Binary Search in Graphs
Ehsan Emamjomeh-Zadeh, David Kempe, Vikrant Singhal
|
👻
Ghosted
|
cs.DS
|
69 |
11 years ago |
| 97 |
Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
|
👻
Ghosted
|
cs.DS
|
68 |
10 years ago |
| 98 |
String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure
Dominik Kempa, Tomasz Kociumaka
|
👻
Ghosted
|
cs.DS
|
66 |
7 years ago |
| 99 |
Robust Linear Regression: Optimal Rates in Polynomial Time
Ainesh Bakshi, Adarsh Prasad
|
👻
Ghosted
|
stat.ML
|
63 |
5 years ago |
| 100 |
Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms
Sagnik Mukhopadhyay, Danupon Nanongkai
|
👻
Ghosted
|
cs.DS
|
63 |
6 years ago |