| 101 |
Near-Optimal Fully Dynamic Densest Subgraph
Saurabh Sawlani, Junxing Wang
|
👻
Ghosted
|
cs.DS
|
63 |
6 years ago |
| 102 |
A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
Ola Svensson, Jakub Tarnawski, László A. Végh
|
👻
Ghosted
|
cs.DS
|
63 |
8 years ago |
| 103 |
Robustness Implies Privacy in Statistical Estimation
Samuel B. Hopkins, Gautam Kamath, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
63 |
3 years ago |
| 104 |
A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path
Sally Dong, Yin Tat Lee, Guanghao Ye
|
👻
Ghosted
|
cs.DS
|
62 |
5 years ago |
| 105 |
Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design
Yufei Ruan, Jiaqi Yang, Yuan Zhou
|
👻
Ghosted
|
cs.LG
|
62 |
5 years ago |
| 106 |
Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators
Alexandr Andoni, Clifford Stein, Peilin Zhong
|
👻
Ghosted
|
cs.DS
|
62 |
6 years ago |
| 107 |
Improved Distributed Algorithms for Exact Shortest Paths
Mohsen Ghaffari, Jason Li
|
👻
Ghosted
|
cs.DC
|
62 |
8 years ago |
| 108 |
A Generalization of Permanent Inequalities and Applications in Counting and Optimization
Nima Anari, Shayan Oveis Gharan
|
👻
Ghosted
|
cs.DS
|
62 |
9 years ago |
| 109 |
New Classes of Distributed Time Complexity
Alkida Balliu, Juho Hirvonen, ... (+4 more)
|
👻
Ghosted
|
cs.DC
|
62 |
8 years ago |
| 110 |
Parallel Algorithms for Select and Partition with Noisy Comparisons
Mark Braverman, Jieming Mao, S. Matthew Weinberg
|
👻
Ghosted
|
cs.DS
|
62 |
10 years ago |
| 111 |
Rounding Dynamic Matchings Against an Adaptive Adversary
David Wajc
|
👻
Ghosted
|
cs.DS
|
61 |
6 years ago |
| 112 |
Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits
Daniel M. Kane, Ryan Williams
|
🔮
The Ethereal
|
cs.CC
|
60 |
10 years ago |
| 113 |
Quantum Cryptography in Algorithmica
William Kretschmer, Luowen Qian, ... (+2 more)
|
👻
Ghosted
|
quant-ph
|
60 |
3 years ago |
| 114 |
The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness
Moran Feldman, Ashkan Norouzi-Fard, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
59 |
6 years ago |
| 115 |
Faster Parallel Algorithm for Approximate Shortest Path
Jason Li
|
👻
Ghosted
|
cs.DS
|
59 |
6 years ago |
| 116 |
A Friendly Smoothed Analysis of the Simplex Method
Daniel Dadush, Sophie Huiberts
|
👻
Ghosted
|
cs.DS
|
58 |
8 years ago |
| 117 |
Random graph matching at Otter's threshold via counting chandeliers
Cheng Mao, Yihong Wu, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
58 |
3 years ago |
| 118 |
Learning shallow quantum circuits
Hsin-Yuan Huang, Yunchao Liu, ... (+5 more)
|
👻
Ghosted
|
quant-ph
|
57 |
2 years ago |
| 119 |
Deterministic Distributed Edge-Coloring with Fewer Colors
Mohsen Ghaffari, Fabian Kuhn, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
57 |
8 years ago |
| 120 |
The Limitations of Optimization from Samples
Eric Balkanski, Aviad Rubinstein, Yaron Singer
|
👻
Ghosted
|
cs.DS
|
57 |
10 years ago |
| 121 |
Discrepancy Minimization via a Self-Balancing Walk
Ryan Alweiss, Yang P. Liu, Mehtaab Sawhney
|
👻
Ghosted
|
cs.DS
|
56 |
5 years ago |
| 122 |
A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
Gopal Pandurangan, Peter Robinson, Michele Scquizzato
|
👻
Ghosted
|
cs.DC
|
56 |
9 years ago |
| 123 |
Towards Optimal Lower Bounds for k-median and k-means Coresets
Vincent Cohen-Addad, Kasper Green Larsen, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
56 |
4 years ago |
| 124 |
Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems
Aram Harrow, Saeed Mehraban, Mehdi Soleimanifar
|
👻
Ghosted
|
quant-ph
|
55 |
6 years ago |
| 125 |
A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems
Julia Chuzhoy, Sanjeev Khanna
|
👻
Ghosted
|
cs.DS
|
55 |
6 years ago |
| 126 |
Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time
Aaron Bernstein, Danupon Nanongkai
|
👻
Ghosted
|
cs.DC
|
55 |
7 years ago |
| 127 |
Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
Arturs Backurs, Liam Roditty, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
55 |
7 years ago |
| 128 |
Online Service with Delay
Yossi Azar, Arun Ganesh, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
55 |
8 years ago |
| 129 |
Exact Algorithms via Monotone Local Search
Fedor V. Fomin, Serge Gaspers, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
55 |
10 years ago |
| 130 |
A Polynomial Lower Bound for Testing Monotonicity
Aleksandrs Belovs, Eric Blais
|
🔮
The Ethereal
|
cs.CC
|
54 |
10 years ago |
| 131 |
Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem
Sepehr Assadi, Sanjeev Khanna, Yang Li
|
👻
Ghosted
|
cs.DS
|
53 |
10 years ago |
| 132 |
Approximation Algorithms for Minimum Norm and Ordered Optimization Problems
Deeparnab Chakrabarty, Chaitanya Swamy
|
👻
Ghosted
|
cs.DS
|
52 |
7 years ago |
| 133 |
Optimal terminal dimensionality reduction in Euclidean space
Shyam Narayanan, Jelani Nelson
|
👻
Ghosted
|
cs.DS
|
52 |
7 years ago |
| 134 |
Approximate Counting, the Lovasz Local Lemma and Inference in Graphical Models
Ankur Moitra
|
👻
Ghosted
|
cs.DS
|
52 |
9 years ago |
| 135 |
Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
Nikhil Bansal, Aravind Srinivasan, Ola Svensson
|
👻
Ghosted
|
cs.DS
|
52 |
10 years ago |
| 136 |
Parallelizing greedy for submodular set function maximization in matroids and beyond
Chandra Chekuri, Kent Quanrud
|
👻
Ghosted
|
cs.DS
|
51 |
7 years ago |
| 137 |
Capacity Upper Bounds for Deletion-Type Channels
Mahdi Cheraghchi
|
👻
Ghosted
|
cs.IT
|
51 |
8 years ago |
| 138 |
Set Similarity Search Beyond MinHash
Tobias Christiani, Rasmus Pagh
|
👻
Ghosted
|
cs.DS
|
51 |
9 years ago |
| 139 |
Real Stable Polynomials and Matroids: Optimization and Counting
Damian Straszak, Nisheeth K. Vishnoi
|
👻
Ghosted
|
cs.DS
|
51 |
9 years ago |
| 140 |
Credible Decentralized Exchange Design via Verifiable Sequencing Rules
Matheus V. X. Ferreira, David C. Parkes
|
👻
Ghosted
|
cs.GT
|
51 |
3 years ago |
| 141 |
A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms
Haim Avron, Michael Kapralov, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
50 |
7 years ago |
| 142 |
Algorithmic Discrepancy Beyond Partial Coloring
Nikhil Bansal, Shashwat Garg
|
👻
Ghosted
|
cs.DS
|
50 |
9 years ago |
| 143 |
Constant-factor approximation of near-linear edit distance in near-linear time
Joshua Brakensiek, Aviad Rubinstein
|
👻
Ghosted
|
cs.DS
|
49 |
7 years ago |
| 144 |
Efficient decoding of random errors for quantum expander codes
Omar Fawzi, Antoine Grospellier, Anthony Leverrier
|
👻
Ghosted
|
quant-ph
|
49 |
8 years ago |
| 145 |
A Unifying Theory of Distance from Calibration
Jarosław Błasiok, Parikshit Gopalan, ... (+2 more)
|
👻
Ghosted
|
cs.LG
|
49 |
3 years ago |
| 146 |
An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model
Eric Balkanski, Aviad Rubinstein, Yaron Singer
|
👻
Ghosted
|
cs.DS
|
48 |
7 years ago |
| 147 |
Local max-cut in smoothed polynomial time
Omer Angel, Sébastien Bubeck, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
48 |
9 years ago |
| 148 |
Geodesic Walks in Polytopes
Yin Tat Lee, Santosh S. Vempala
|
👻
Ghosted
|
cs.DS
|
48 |
9 years ago |
| 149 |
Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time
Michael Kapralov
|
👻
Ghosted
|
cs.DS
|
48 |
10 years ago |
| 150 |
Beating CountSketch for Heavy Hitters in Insertion Streams
Vladimir Braverman, Stephen R. Chestnut, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
48 |
10 years ago |