| 151 |
Fully Dynamic Spectral Vertex Sparsifiers and Applications
David Durfee, Yu Gao, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
47 |
6 years ago |
| 152 |
$O(\log^2k/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm
Fabrizio Grandoni, Bundit Laekhanukit, Shi Li
|
👻
Ghosted
|
cs.DS
|
47 |
7 years ago |
| 153 |
Learning quantum Hamiltonians at any temperature in polynomial time
Ainesh Bakshi, Allen Liu, ... (+2 more)
|
👻
Ghosted
|
quant-ph
|
46 |
2 years ago |
| 154 |
Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles
Mina Dalirrooyfard, Thuy Duong Vuong, Virginia Vassilevska Williams
|
🔮
The Ethereal
|
cs.CC
|
46 |
7 years ago |
| 155 |
Exponential Separations in the Energy Complexity of Leader Election
Yi-Jun Chang, Tsvi Kopelowitz, ... (+3 more)
|
👻
Ghosted
|
cs.DC
|
46 |
9 years ago |
| 156 |
Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders
Shahar Dobzinski
|
👻
Ghosted
|
cs.GT
|
46 |
10 years ago |
| 157 |
Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme
Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
|
👻
Ghosted
|
cs.DS
|
45 |
7 years ago |
| 158 |
Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius
Chong Shangguan, Itzhak Tamo
|
👻
Ghosted
|
cs.IT
|
45 |
6 years ago |
| 159 |
More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
Amir Abboud, Karl Bringmann, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
45 |
7 years ago |
| 160 |
Synchronization Strings: Explicit Constructions, Local Decoding, and Applications
Bernhard Haeupler, Amirbehshad Shahrasbi
|
👻
Ghosted
|
cs.IT
|
45 |
8 years ago |
| 161 |
Pseudodeterministic Constructions in Subexponential Time
Igor C. Oliveira, Rahul Santhanam
|
🔮
The Ethereal
|
cs.CC
|
45 |
9 years ago |
| 162 |
Subquadratic Submodular Function Minimization
Deeparnab Chakrabarty, Yin Tat Lee, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
45 |
9 years ago |
| 163 |
Improved Approximations for Euclidean $k$-means and $k$-median, via Nested Quasi-Independent Sets
Vincent Cohen-Addad, Hossein Esfandiari, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
45 |
4 years ago |
| 164 |
Settling the Robust Learnability of Mixtures of Gaussians
Allen Liu, Ankur Moitra
|
👻
Ghosted
|
cs.DS
|
44 |
5 years ago |
| 165 |
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 |
| 166 |
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 |
| 167 |
The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches
Aris Filos-Ratsikas, Paul W. Goldberg
|
🔮
The Ethereal
|
cs.CC
|
44 |
7 years ago |
| 168 |
Improved Approximation for Tree Augmentation: Saving by Rewiring
Fabrizio Grandoni, Christos Kalaitzis, Rico Zenklusen
|
👻
Ghosted
|
cs.DS
|
44 |
8 years ago |
| 169 |
Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law
Max Simchowitz, Ahmed El Alaoui, Benjamin Recht
|
👻
Ghosted
|
cs.LG
|
44 |
8 years ago |
| 170 |
Improved Stabilizer Estimation via Bell Difference Sampling
Sabee Grewal, Vishnu Iyer, ... (+2 more)
|
👻
Ghosted
|
quant-ph
|
43 |
3 years ago |
| 171 |
Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments
Sitan Chen, Jerry Li, Zhao Song
|
👻
Ghosted
|
cs.DS
|
43 |
6 years ago |
| 172 |
Reducing Path TSP to TSP
Vera Traub, Jens Vygen, Rico Zenklusen
|
🔮
The Ethereal
|
cs.DM
|
43 |
6 years ago |
| 173 |
Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions
Sebastian Forster, Gramoz Goranci
|
👻
Ghosted
|
cs.DS
|
43 |
8 years ago |
| 174 |
The Power of Multiple Choices in Online Stochastic Matching
Zhiyi Huang, Xinkai Shu, Shuyi Yan
|
👻
Ghosted
|
cs.DS
|
43 |
4 years ago |
| 175 |
Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
Mark Bun, Marco Gaboardi, ... (+6 more)
|
👻
Ghosted
|
cs.LG
|
42 |
3 years ago |
| 176 |
A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique
Krzysztof Nowicki
|
👻
Ghosted
|
cs.DS
|
42 |
6 years ago |
| 177 |
Distributed Edge Connectivity in Sublinear Time
Mohit Daga, Monika Henzinger, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
42 |
7 years ago |
| 178 |
An Optimal Space Lower Bound for Approximating MAX-CUT
Michael Kapralov, Dmitry Krachun
|
👻
Ghosted
|
cs.DS
|
42 |
7 years ago |
| 179 |
Submodular Maximization with Matroid and Packing Constraints in Parallel
Alina Ene, Huy L. Nguyen, Adrian Vladu
|
👻
Ghosted
|
cs.DS
|
42 |
7 years ago |
| 180 |
Nearly Work-Efficient Parallel Algorithm for Digraph Reachability
Jeremy T. Fineman
|
👻
Ghosted
|
cs.DS
|
42 |
8 years ago |
| 181 |
Approximate Near Neighbors for General Symmetric Norms
Alexandr Andoni, Huy L. Nguyen, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
42 |
9 years ago |
| 182 |
Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
|
👻
Ghosted
|
cs.DS
|
41 |
5 years ago |
| 183 |
Fast swap regret minimization and applications to approximate correlated equilibria
Binghui Peng, Aviad Rubinstein
|
👻
Ghosted
|
cs.GT
|
39 |
2 years ago |
| 184 |
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 |
| 185 |
Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, ... (+3 more)
|
👻
Ghosted
|
math.ST
|
39 |
6 years ago |
| 186 |
Explicit near-Ramanujan graphs of every degree
Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes
|
👻
Ghosted
|
cs.DS
|
39 |
6 years ago |
| 187 |
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 |
| 188 |
Competitively Chasing Convex Bodies
Sébastien Bubeck, Yin Tat Lee, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
39 |
7 years ago |
| 189 |
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 |
| 190 |
Secretary Problems with Non-Uniform Arrival Order
Thomas Kesselheim, Robert Kleinberg, Rad Niazadeh
|
👻
Ghosted
|
cs.DS
|
39 |
11 years ago |
| 191 |
Towards Tight Bounds for Spectral Sparsification of Hypergraphs
Michael Kapralov, Robert Krauthgamer, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
38 |
5 years ago |
| 192 |
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 |
| 193 |
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 |
| 194 |
Lifting Sum-of-Squares Lower Bounds: Degree-$2$ to Degree-$4$
Sidhanth Mohanty, Prasad Raghavendra, Jeff Xu
|
🔮
The Ethereal
|
cs.CC
|
38 |
6 years ago |
| 195 |
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 |
| 196 |
Efficient Randomized Distributed Coloring in CONGEST
Magnús M. Halldórsson, Fabian Kuhn, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
37 |
5 years ago |
| 197 |
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 |
| 198 |
Unconstrained Submodular Maximization with Constant Adaptive Complexity
Lin Chen, Moran Feldman, Amin Karbasi
|
👻
Ghosted
|
cs.DS
|
37 |
7 years ago |
| 199 |
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 |
| 200 |
Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications
Sitan Chen, Ankur Moitra
|
👻
Ghosted
|
cs.LG
|
37 |
8 years ago |