| 301 |
The Number of Minimum $k$-Cuts: Improving the Karger-Stein Bound
Anupam Gupta, Euiwoong Lee, Jason Li
|
👻
Ghosted
|
cs.DS
|
19 |
7 years ago |
| 302 |
Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $Δ$-Coloring
Sepehr Assadi, Pankaj Kumar, Parth Mittal
|
👻
Ghosted
|
cs.DS
|
19 |
4 years ago |
| 303 |
Memory Bounds for the Experts Problem
Vaidehi Srinivas, David P. Woodruff, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
19 |
4 years ago |
| 304 |
A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
Aravind Gollakota, Adam R. Klivans, Pravesh K. Kothari
|
👻
Ghosted
|
cs.LG
|
19 |
3 years ago |
| 305 |
0-1 Knapsack in Nearly Quadratic Time
Ce Jin
|
👻
Ghosted
|
cs.DS
|
19 |
2 years ago |
| 306 |
From Independence to Expansion and Back Again
Tobias Christiani, Rasmus Pagh, Mikkel Thorup
|
👻
Ghosted
|
cs.DS
|
18 |
11 years ago |
| 307 |
Dynamic Sampling from Graphical Models
Weiming Feng, Nisheeth K. Vishnoi, Yitong Yin
|
👻
Ghosted
|
cs.DS
|
18 |
8 years ago |
| 308 |
Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
Arun Jambulapati, Yin Tat Lee, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
18 |
6 years ago |
| 309 |
Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits
Sepehr Assadi, Chen Wang
|
👻
Ghosted
|
cs.DS
|
18 |
6 years ago |
| 310 |
On the computability of continuous maximum entropy distributions with applications
Jonathan Leake, Nisheeth K. Vishnoi
|
👻
Ghosted
|
cs.DS
|
18 |
6 years ago |
| 311 |
A Unified Framework for Light Spanners
Hung Le, Shay Solomon
|
👻
Ghosted
|
cs.DS
|
18 |
5 years ago |
| 312 |
Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs
Mina Dalirrooyfard, Nicole Wein
|
👻
Ghosted
|
cs.DS
|
18 |
5 years ago |
| 313 |
On Optimal Coreset Construction for Euclidean $(k,z)$-Clustering
Lingxiao Huang, Jian Li, Xuan Wu
|
👻
Ghosted
|
cs.DS
|
18 |
3 years ago |
| 314 |
New Subset Selection Algorithms for Low Rank Approximation: Offline and Online
David P. Woodruff, Taisuke Yasuda
|
👻
Ghosted
|
cs.DS
|
18 |
3 years ago |
| 315 |
Optimal Eigenvalue Approximation via Sketching
William Swartworth, David P. Woodruff
|
👻
Ghosted
|
cs.DS
|
18 |
3 years ago |
| 316 |
Knapsack with Small Items in Near-Quadratic Time
Karl Bringmann
|
👻
Ghosted
|
cs.DS
|
18 |
2 years ago |
| 317 |
Solving Dense Linear Systems Faster Than via Preconditioning
Michał Dereziński, Jiaming Yang
|
👻
Ghosted
|
cs.DS
|
18 |
2 years ago |
| 318 |
An optimal tradeoff between entanglement and copy complexity for state tomography
Sitan Chen, Jerry Li, Allen Liu
|
👻
Ghosted
|
quant-ph
|
18 |
2 years ago |
| 319 |
Online Edge Coloring is (Nearly) as Easy as Offline
Joakim Blikstad, Ola Svensson, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
18 |
2 years ago |
| 320 |
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Ran Duan, Jiayi Mao, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
18 |
1 year ago |
| 321 |
Routing under Balance
Alina Ene, Gary Miller, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
17 |
10 years ago |
| 322 |
Fully-dynamic Planarity Testing in Polylogarithmic Time
Jacob Holm, Eva Rotenberg
|
👻
Ghosted
|
cs.DS
|
17 |
6 years ago |
| 323 |
Fully Dynamic Approximation of LIS in Polylogarithmic Time
Paweł Gawrychowski, Wojciech Janczewski
|
👻
Ghosted
|
cs.DS
|
17 |
5 years ago |
| 324 |
Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
Sophie Huiberts, Yin Tat Lee, Xinzhi Zhang
|
👻
Ghosted
|
cs.DS
|
17 |
3 years ago |
| 325 |
The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations
Nicolò Cesa-Bianchi, Tommaso Cesari, ... (+3 more)
|
👻
Ghosted
|
cs.GT
|
17 |
3 years ago |
| 326 |
Trickle-Down in Localization Schemes and Applications
Nima Anari, Frederic Koehler, Thuy-Duong Vuong
|
👻
Ghosted
|
math.PR
|
17 |
1 year ago |
| 327 |
Six Candidates Suffice to Win a Voter Majority
Moses Charikar, Alexandra Lassota, ... (+3 more)
|
👻
Ghosted
|
cs.GT
|
17 |
1 year ago |
| 328 |
Exponential Separation of Quantum Communication and Classical Information
Anurag Anshu, Dave Touchette, ... (+2 more)
|
👻
Ghosted
|
quant-ph
|
16 |
9 years ago |
| 329 |
Efficiently Learning Structured Distributions from Untrusted Batches
Sitan Chen, Jerry Li, Ankur Moitra
|
👻
Ghosted
|
cs.DS
|
16 |
6 years ago |
| 330 |
SDPs and Robust Satisfiability of Promise CSP
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
|
👻
Ghosted
|
cs.DS
|
16 |
3 years ago |
| 331 |
A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths
Julia Chuzhoy, Ruimin Zhang
|
👻
Ghosted
|
cs.DS
|
16 |
3 years ago |
| 332 |
Low-Step Multi-Commodity Flow Emulators
Bernhard Haeupler, D Ellis Hershkowitz, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
16 |
2 years ago |
| 333 |
The Online $k$-Taxi Problem
Christian Coester, Elias Koutsoupias
|
👻
Ghosted
|
cs.DS
|
15 |
8 years ago |
| 334 |
Detecting and Counting Small Patterns in Planar Graphs in Subexponential Parameterized Time
Jesper Nederlof
|
👻
Ghosted
|
cs.DS
|
15 |
7 years ago |
| 335 |
VC Dimension and Distribution-Free Sample-Based Testing
Eric Blais, Renato Ferreira Pinto, Nathaniel Harms
|
👻
Ghosted
|
cs.LG
|
15 |
5 years ago |
| 336 |
Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank
Nikhil Bansal, Haotian Jiang, Raghu Meka
|
👻
Ghosted
|
cs.DS
|
15 |
3 years ago |
| 337 |
Fast Algorithms via Dynamic-Oracle Matroids
Joakim Blikstad, Sagnik Mukhopadhyay, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
15 |
3 years ago |
| 338 |
A Nearly Quadratic-Time FPTAS for Knapsack
Lin Chen, Jiayi Lian, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
15 |
2 years ago |
| 339 |
Local Borsuk-Ulam, Stability, and Replicability
Zachary Chase, Bogdan Chornomaz, ... (+2 more)
|
👻
Ghosted
|
cs.LG
|
15 |
2 years ago |
| 340 |
Analysis of a Classical Matrix Preconditioning Algorithm
Leonard J. Schulman, Alistair Sinclair
|
👻
Ghosted
|
cs.DS
|
14 |
11 years ago |
| 341 |
Cell-probe Lower Bounds for Dynamic Problems via a New Communication Model
Huacheng Yu
|
👻
Ghosted
|
cs.DS
|
14 |
10 years ago |
| 342 |
Asymptotics of Reinforcement Learning with Neural Networks
Justin Sirignano, Konstantinos Spiliopoulos
|
👻
Ghosted
|
cs.LG
|
14 |
6 years ago |
| 343 |
Quantum Depth in the Random Oracle Model
Atul Singh Arora, Andrea Coladangelo, ... (+4 more)
|
👻
Ghosted
|
quant-ph
|
14 |
3 years ago |
| 344 |
Weighted Edit Distance Computation: Strings, Trees and Dyck
Debarati Das, Jacob Gilbert, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
14 |
3 years ago |
| 345 |
Subsampling Suffices for Adaptive Data Analysis
Guy Blanc
|
👻
Ghosted
|
cs.LG
|
14 |
3 years ago |
| 346 |
Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
|
👻
Ghosted
|
cs.DS
|
14 |
3 years ago |
| 347 |
Prophet Inequalities Require Only a Constant Number of Samples
Andrés Cristi, Bruno Ziliotto
|
👻
Ghosted
|
cs.DS
|
14 |
2 years ago |
| 348 |
Parallel Exhaustive Search without Coordination
Pierre Fraigniaud, Amos Korman, Yoav Rodeh
|
👻
Ghosted
|
cs.DC
|
13 |
10 years ago |
| 349 |
Kolmogorov complexity version of Slepian-Wolf coding
Marius Zimand
|
👻
Ghosted
|
cs.IT
|
13 |
10 years ago |
| 350 |
The Karger-Stein Algorithm is Optimal for $k$-cut
Anupam Gupta, Euiwoong Lee, Jason Li
|
👻
Ghosted
|
cs.DS
|
13 |
6 years ago |