| 251 |
Almost Polynomial Hardness of Node-Disjoint Paths in Grids
Julia Chuzhoy, David H. K. Kim, Rachit Nimavat
|
👻
Ghosted
|
cs.DS
|
24 |
8 years ago |
| 252 |
On a generalization of iterated and randomized rounding
Nikhil Bansal
|
👻
Ghosted
|
cs.DS
|
24 |
7 years ago |
| 253 |
Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max
Karl Bringmann, Marvin Künnemann, Karol Węgrzycki
|
👻
Ghosted
|
cs.DS
|
24 |
6 years ago |
| 254 |
An Improved Approximation Algorithm for TSP in the Half Integral Case
Anna Karlin, Nathan Klein, Shayan Oveis Gharan
|
👻
Ghosted
|
cs.DS
|
24 |
6 years ago |
| 255 |
Arıkan meets Shannon: Polar codes with near-optimal convergence to channel capacity
Venkatesan Guruswami, Andrii Riazanov, Min Ye
|
👻
Ghosted
|
cs.IT
|
24 |
6 years ago |
| 256 |
The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation
Albert Cheu, Jonathan Ullman
|
👻
Ghosted
|
cs.DS
|
24 |
5 years ago |
| 257 |
Holiest Minimum-Cost Paths and Flows in Surface Graphs
Jeff Erickson, Kyle Fox, Luvsandondov Lkhamsuren
|
👻
Ghosted
|
cs.DS
|
23 |
8 years ago |
| 258 |
Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds
Rong Ge, Holden Lee, Jianfeng Lu
|
👻
Ghosted
|
cs.DS
|
23 |
6 years ago |
| 259 |
Approximating Text-to-Pattern Hamming Distances
Timothy M. Chan, Shay Golan, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
23 |
6 years ago |
| 260 |
Distributed Weighted Min-Cut in Nearly-Optimal Time
Michal Dory, Yuval Efron, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
23 |
6 years ago |
| 261 |
Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors
Jesper Nederlof, Karol Węgrzycki
|
👻
Ghosted
|
cs.DS
|
23 |
5 years ago |
| 262 |
Application of deep learning to large scale riverine flow velocity estimation
Mojtaba Forghani, Yizhou Qian, ... (+5 more)
|
👻
Ghosted
|
cs.LG
|
23 |
5 years ago |
| 263 |
Testing distributional assumptions of learning algorithms
Ronitt Rubinfeld, Arsen Vasilyan
|
👻
Ghosted
|
cs.LG
|
23 |
4 years ago |
| 264 |
Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification
Arun Jambulapati, Yang P. Liu, Aaron Sidford
|
👻
Ghosted
|
cs.DS
|
23 |
3 years ago |
| 265 |
Õptimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization
Edith Cohen, Xin Lyu, ... (+3 more)
|
👻
Ghosted
|
cs.LG
|
23 |
3 years ago |
| 266 |
Understanding the Cluster LP for Correlation Clustering
Nairen Cao, Vincent Cohen-Addad, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
23 |
2 years ago |
| 267 |
Quantum fault tolerance with constant-space and logarithmic-time overheads
Quynh T. Nguyen, Christopher A. Pattison
|
👻
Ghosted
|
quant-ph
|
23 |
1 year ago |
| 268 |
Smooth heaps and a dual view of self-adjusting data structures
László Kozma, Thatchaphol Saranurak
|
👻
Ghosted
|
cs.DS
|
22 |
8 years ago |
| 269 |
Spectral Methods from Tensor Networks
Ankur Moitra, Alexander S. Wein
|
👻
Ghosted
|
cs.DS
|
22 |
7 years ago |
| 270 |
Three-in-a-Tree in Near Linear Time
Kai-Yuan Lai, Hsueh-I Lu, Mikkel Thorup
|
👻
Ghosted
|
cs.DS
|
22 |
6 years ago |
| 271 |
Contention Resolution Without Collision Detection
Michael A. Bender, Tsvi Kopelowitz, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
22 |
6 years ago |
| 272 |
Improved Dynamic Algorithms for Longest Increasing Subsequence
Tomasz Kociumaka, Saeed Seddighin
|
👻
Ghosted
|
cs.DS
|
22 |
5 years ago |
| 273 |
Deterministic, Near-Linear $\varepsilon$-Approximation Algorithm for Geometric Bipartite Matching
Pankaj K. Agarwal, Hsien-Chih Chang, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
22 |
4 years ago |
| 274 |
On Regularity Lemma and Barriers in Streaming and Dynamic Matching
Sepehr Assadi, Soheil Behnezhad, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
22 |
3 years ago |
| 275 |
Approximating Nash Social Welfare by Matching and Local Search
Jugal Garg, Edin Husić, ... (+3 more)
|
👻
Ghosted
|
cs.GT
|
22 |
3 years ago |
| 276 |
Optimal Embedding Dimension for Sparse Subspace Embeddings
Shabarish Chenakkod, Michał Dereziński, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
22 |
2 years ago |
| 277 |
Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation
Sitan Chen, Weiyuan Gong, ... (+2 more)
|
👻
Ghosted
|
quant-ph
|
22 |
1 year ago |
| 278 |
Learning Arbitrary Statistical Mixtures of Discrete Distributions
Jian Li, Yuval Rabani, ... (+2 more)
|
👻
Ghosted
|
cs.LG
|
21 |
11 years ago |
| 279 |
Metric Embedding via Shortest Path Decompositions
Ittai Abraham, Arnold Filtser, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
21 |
8 years ago |
| 280 |
Stronger L2/L2 Compressed Sensing; Without Iterating
Vasileios Nakos, Zhao Song
|
👻
Ghosted
|
cs.DS
|
21 |
7 years ago |
| 281 |
Data Structures Meet Cryptography: 3SUM with Preprocessing
Alexander Golovnev, Siyao Guo, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
21 |
6 years ago |
| 282 |
Smoothed complexity of local Max-Cut and binary Max-CSP
Xi Chen, Chenghao Guo, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
21 |
6 years ago |
| 283 |
On codes decoding a constant fraction of errors on the BSC
Alex Samorodnitsky, Ori Sberlo
|
👻
Ghosted
|
cs.IT
|
21 |
5 years ago |
| 284 |
Low-Rank Approximation with $1/ε^{1/3}$ Matrix-Vector Products
Ainesh Bakshi, Kenneth L. Clarkson, David P. Woodruff
|
👻
Ghosted
|
cs.DS
|
21 |
4 years ago |
| 285 |
(Fractional) Online Stochastic Matching via Fine-Grained Offline Statistics
Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu
|
👻
Ghosted
|
cs.DS
|
21 |
4 years ago |
| 286 |
Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme
Hu Fu, Jiawei Li, Daogao Liu
|
👻
Ghosted
|
cs.DS
|
21 |
3 years ago |
| 287 |
Optimal Bounds for Noisy Sorting
Yuzhou Gu, Yinzhan Xu
|
👻
Ghosted
|
cs.DS
|
21 |
3 years ago |
| 288 |
No distributed quantum advantage for approximate graph coloring
Xavier Coiteux-Roy, Francesco d'Amore, ... (+8 more)
|
👻
Ghosted
|
cs.DC
|
21 |
2 years ago |
| 289 |
Provably learning a multi-head attention layer
Sitan Chen, Yuanzhi Li
|
👻
Ghosted
|
cs.LG
|
21 |
2 years ago |
| 290 |
Combinatorial Correlation Clustering
Vincent Cohen-Addad, David Rasmussen Lolck, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
21 |
2 years ago |
| 291 |
Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards
Alessandro Arlotto, Xinchang Xie
|
👻
Ghosted
|
math.PR
|
20 |
7 years ago |
| 292 |
Why Extension-Based Proofs Fail
Dan Alistarh, James Aspnes, ... (+3 more)
|
👻
Ghosted
|
cs.DC
|
20 |
7 years ago |
| 293 |
Achieving Optimal Backlog in Multi-Processor Cup Games
Michael A. Bender, Martin Farach-Colton, William Kuszmaul
|
👻
Ghosted
|
cs.DS
|
20 |
7 years ago |
| 294 |
Tree Embeddings for Hop-Constrained Network Design
Bernhard Haeupler, D Ellis Hershkowitz, Goran Zuzic
|
👻
Ghosted
|
cs.DS
|
20 |
5 years ago |
| 295 |
Spectral hypergraph sparsification via chaining
James R. Lee
|
👻
Ghosted
|
math.PR
|
20 |
3 years ago |
| 296 |
Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
Václav Rozhoň, Bernhard Haeupler, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
20 |
3 years ago |
| 297 |
A Characterization of List Learnability
Moses Charikar, Chirag Pabbaraju
|
👻
Ghosted
|
stat.ML
|
20 |
3 years ago |
| 298 |
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
Peter Gartland, Daniel Lokshtanov, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
20 |
3 years ago |
| 299 |
An Adaptive Sublinear-Time Block Sparse Fourier Transform
Volkan Cevher, Michael Kapralov, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
19 |
9 years ago |
| 300 |
Fast hashing with Strong Concentration Bounds
Anders Aamand, Jakob B. T. Knudsen, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
19 |
7 years ago |