| 151 |
Constant factor approximations to edit distance on far input pairs in nearly linear time
Michal Koucký, Michael E. Saks
|
👻
Ghosted
|
cs.DS
|
44 |
7 years ago |
| 152 |
Settling the Robust Learnability of Mixtures of Gaussians
Allen Liu, Ankur Moitra
|
👻
Ghosted
|
cs.DS
|
44 |
5 years ago |
| 153 |
Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches
Federica Cecchetto, Vera Traub, Rico Zenklusen
|
👻
Ghosted
|
cs.DS
|
44 |
5 years ago |
| 154 |
Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions
Sebastian Forster, Gramoz Goranci
|
👻
Ghosted
|
cs.DS
|
43 |
8 years ago |
| 155 |
Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments
Sitan Chen, Jerry Li, Zhao Song
|
👻
Ghosted
|
cs.DS
|
43 |
6 years ago |
| 156 |
The Power of Multiple Choices in Online Stochastic Matching
Zhiyi Huang, Xinkai Shu, Shuyi Yan
|
👻
Ghosted
|
cs.DS
|
43 |
4 years ago |
| 157 |
Improved Stabilizer Estimation via Bell Difference Sampling
Sabee Grewal, Vishnu Iyer, ... (+2 more)
|
👻
Ghosted
|
quant-ph
|
43 |
3 years ago |
| 158 |
Approximate Near Neighbors for General Symmetric Norms
Alexandr Andoni, Huy L. Nguyen, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
42 |
9 years ago |
| 159 |
Nearly Work-Efficient Parallel Algorithm for Digraph Reachability
Jeremy T. Fineman
|
👻
Ghosted
|
cs.DS
|
42 |
8 years ago |
| 160 |
Submodular Maximization with Matroid and Packing Constraints in Parallel
Alina Ene, Huy L. Nguyen, Adrian Vladu
|
👻
Ghosted
|
cs.DS
|
42 |
7 years ago |
| 161 |
An Optimal Space Lower Bound for Approximating MAX-CUT
Michael Kapralov, Dmitry Krachun
|
👻
Ghosted
|
cs.DS
|
42 |
7 years ago |
| 162 |
Distributed Edge Connectivity in Sublinear Time
Mohit Daga, Monika Henzinger, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
42 |
7 years ago |
| 163 |
A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique
Krzysztof Nowicki
|
👻
Ghosted
|
cs.DS
|
42 |
6 years ago |
| 164 |
Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
Mark Bun, Marco Gaboardi, ... (+6 more)
|
👻
Ghosted
|
cs.LG
|
42 |
3 years ago |
| 165 |
Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
|
👻
Ghosted
|
cs.DS
|
41 |
5 years ago |
| 166 |
Secretary Problems with Non-Uniform Arrival Order
Thomas Kesselheim, Robert Kleinberg, Rad Niazadeh
|
👻
Ghosted
|
cs.DS
|
39 |
11 years ago |
| 167 |
Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
Andris Ambainis, Martins Kokainis
|
👻
Ghosted
|
quant-ph
|
39 |
9 years ago |
| 168 |
Competitively Chasing Convex Bodies
Sébastien Bubeck, Yin Tat Lee, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
39 |
7 years ago |
| 169 |
Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time
Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen
|
👻
Ghosted
|
cs.DS
|
39 |
7 years ago |
| 170 |
Explicit near-Ramanujan graphs of every degree
Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes
|
👻
Ghosted
|
cs.DS
|
39 |
6 years ago |
| 171 |
Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, ... (+3 more)
|
👻
Ghosted
|
math.ST
|
39 |
6 years ago |
| 172 |
Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue
Zhiyi Huang, Qiankun Zhang
|
👻
Ghosted
|
cs.DS
|
39 |
6 years ago |
| 173 |
Fast swap regret minimization and applications to approximate correlated equilibria
Binghui Peng, Aviad Rubinstein
|
👻
Ghosted
|
cs.GT
|
39 |
2 years ago |
| 174 |
Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective
Vishesh Jain, Frederic Koehler, Andrej Risteski
|
👻
Ghosted
|
cs.LG
|
38 |
7 years ago |
| 175 |
Breaching the 2-Approximation Barrier for Connectivity Augmentation: a Reduction to Steiner Tree
Jarosław Byrka, Fabrizio Grandoni, Afrouz Jabal Ameli
|
👻
Ghosted
|
cs.DS
|
38 |
6 years ago |
| 176 |
New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs
Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein
|
👻
Ghosted
|
cs.DS
|
38 |
6 years ago |
| 177 |
Towards Tight Bounds for Spectral Sparsification of Hypergraphs
Michael Kapralov, Robert Krauthgamer, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
38 |
5 years ago |
| 178 |
Testing Cluster Structure of Graphs
Artur Czumaj, Pan Peng, Christian Sohler
|
👻
Ghosted
|
cs.DS
|
37 |
11 years ago |
| 179 |
New Hardness Results for Routing on Disjoint Paths
Julia Chuzhoy, David H. K. Kim, Rachit Nimavat
|
👻
Ghosted
|
cs.DS
|
37 |
9 years ago |
| 180 |
Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications
Sitan Chen, Ankur Moitra
|
👻
Ghosted
|
cs.LG
|
37 |
8 years ago |
| 181 |
Near-Linear Time Insertion-Deletion Codes and (1+$\varepsilon$)-Approximating Edit Distance via Indexing
Bernhard Haeupler, Aviad Rubinstein, Amirbehshad Shahrasbi
|
👻
Ghosted
|
cs.DS
|
37 |
7 years ago |
| 182 |
Unconstrained Submodular Maximization with Constant Adaptive Complexity
Lin Chen, Moran Feldman, Amin Karbasi
|
👻
Ghosted
|
cs.DS
|
37 |
7 years ago |
| 183 |
Fast sampling and counting k-SAT solutions in the local lemma regime
Weiming Feng, Heng Guo, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
37 |
6 years ago |
| 184 |
Efficient Randomized Distributed Coloring in CONGEST
Magnús M. Halldórsson, Fabian Kuhn, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
37 |
5 years ago |
| 185 |
The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
|
👻
Ghosted
|
cs.DS
|
36 |
10 years ago |
| 186 |
On Approximating Functions of the Singular Values in a Stream
Yi Li, David P. Woodruff
|
👻
Ghosted
|
cs.DS
|
36 |
10 years ago |
| 187 |
Constant-Factor Approximation for Ordered k-Median
Jarosław Byrka, Krzysztof Sornat, Joachim Spoerhase
|
👻
Ghosted
|
cs.DS
|
36 |
8 years ago |
| 188 |
A Strongly Polynomial Algorithm for Linear Exchange Markets
Jugal Garg, László A. Végh
|
👻
Ghosted
|
cs.DS
|
36 |
7 years ago |
| 189 |
Polynomial Pass Lower Bounds for Graph Streaming Algorithms
Sepehr Assadi, Yu Chen, Sanjeev Khanna
|
👻
Ghosted
|
cs.DS
|
36 |
7 years ago |
| 190 |
Online Vector Balancing and Geometric Discrepancy
Nikhil Bansal, Haotian Jiang, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
36 |
6 years ago |
| 191 |
Planar Diameter via Metric Compression
Jason Li, Merav Parter
|
👻
Ghosted
|
cs.DS
|
36 |
6 years ago |
| 192 |
Approximating Nash Social Welfare under Rado Valuations
Jugal Garg, Edin Husic, Laszlo A. Vegh
|
👻
Ghosted
|
cs.GT
|
36 |
5 years ago |
| 193 |
Streaming Symmetric Norms via Measure Concentration
Jaroslaw Blasiok, Vladimir Braverman, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
35 |
10 years ago |
| 194 |
Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions
Sepideh Mahabadi, Konstantin Makarychev, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
35 |
7 years ago |
| 195 |
Flows in Almost Linear Time via Adaptive Preconditioning
Rasmus Kyng, Richard Peng, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
35 |
7 years ago |
| 196 |
Faster Min-Plus Product for Monotone Instances
Shucheng Chi, Ran Duan, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
35 |
4 years ago |
| 197 |
Fine-grained reductions from approximate counting to decision
Holger Dell, John Lapinskas
|
👻
Ghosted
|
cs.DS
|
34 |
9 years ago |
| 198 |
Efficient Two-Sided Markets with Limited Information
Paul Dütting, Federico Fusco, ... (+3 more)
|
👻
Ghosted
|
cs.GT
|
34 |
6 years ago |
| 199 |
An Improved Parameterized Algorithm for Treewidth
Tuukka Korhonen, Daniel Lokshtanov
|
👻
Ghosted
|
cs.DS
|
34 |
3 years ago |
| 200 |
Almost Optimal Distance Oracles for Planar Graphs
Panagiotis Charalampopoulos, Paweł Gawrychowski, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
33 |
7 years ago |