| 451 |
Online List Labeling: Breaking the $\log^2n$ Barrier
Michael A. Bender, Alex Conway, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
7 |
4 years ago |
| 452 |
List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
Shashank Srivastava, Madhur Tulsiani
|
👻
Ghosted
|
cs.DS
|
6 |
1 year ago |
| 453 |
Online Combinatorial Allocations and Auctions with Few Samples
Paul Dütting, Thomas Kesselheim, ... (+3 more)
|
👻
Ghosted
|
cs.GT
|
6 |
1 year ago |
| 454 |
Stochastic Online Correlated Selection
Ziyun Chen, Zhiyi Huang, Enze Sun
|
👻
Ghosted
|
cs.DS
|
6 |
1 year ago |
| 455 |
Replicability in High Dimensional Statistics
Max Hopkins, Russell Impagliazzo, ... (+3 more)
|
👻
Ghosted
|
stat.ML
|
6 |
2 years ago |
| 456 |
Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
Nikhil Bansal, Vincent Cohen-Addad, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
6 |
2 years ago |
| 457 |
Tight Bounds for Sorting Under Partial Information
Ivor van der Hoog, Daniel Rutschmann
|
👻
Ghosted
|
cs.DS
|
6 |
2 years ago |
| 458 |
Constant Approximation for Private Interdependent Valuations
Alon Eden, Michal Feldman, ... (+3 more)
|
👻
Ghosted
|
cs.GT
|
6 |
2 years ago |
| 459 |
Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold
Venkatesan Guruswami, Jun-Ting Hsieh, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
6 |
2 years ago |
| 460 |
Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form
Adam Karczmarz, Piotr Sankowski
|
👻
Ghosted
|
cs.DS
|
6 |
2 years ago |
| 461 |
Matrix Completion in Almost-Verification Time
Jonathan A. Kelner, Jerry Li, ... (+3 more)
|
👻
Ghosted
|
cs.LG
|
6 |
2 years ago |
| 462 |
A Sampling Lovász Local Lemma for Large Domain Sizes
Chunyang Wang, Yitong Yin
|
👻
Ghosted
|
cs.DS
|
6 |
2 years ago |
| 463 |
Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the $Ω(\log n)$ Lightness Barrier
Hung Le, Shay Solomon, Cuong Than
|
👻
Ghosted
|
cs.CG
|
6 |
3 years ago |
| 464 |
Agnostic proper learning of monotone functions: beyond the black-box correction barrier
Jane Lange, Arsen Vasilyan
|
👻
Ghosted
|
cs.DS
|
6 |
3 years ago |
| 465 |
Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
Ofer Grossman, Meghal Gupta, Mark Sellke
|
👻
Ghosted
|
cs.DS
|
6 |
3 years ago |
| 466 |
Metric Sublinear Algorithms via Linear Sampling
Hossein Esfandiari, Michael Mitzenmacher
|
👻
Ghosted
|
cs.DS
|
6 |
8 years ago |
| 467 |
Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise
Noah Shutty, Mary Wootters, Patrick Hayden
|
👻
Ghosted
|
cs.IT
|
6 |
7 years ago |
| 468 |
The complexity of general-valued CSPs seen from the other side
Clement Carbonnel, Miguel Romero, Stanislav Zivny
|
🔮
The Ethereal
|
cs.CC
|
6 |
8 years ago |
| 469 |
The Salesman's Improved Paths: 3/2+1/34 Integrality Gap and Approximation Ratio
András Sebő, Anke van Zuylen
|
🔮
The Ethereal
|
cs.DM
|
6 |
10 years ago |
| 470 |
Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant
Vaggos Chatziafratis, Konstantin Makarychev
|
👻
Ghosted
|
cs.DS
|
6 |
3 years ago |
| 471 |
$\tilde{O}(n+\mathrm{poly}(k))$-time Algorithm for Bounded Tree Edit Distance
Debarati Das, Jacob Gilbert, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
6 |
3 years ago |
| 472 |
A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits
William Kuszmaul
|
👻
Ghosted
|
cs.DS
|
6 |
3 years ago |
| 473 |
The Complexity of Dynamic Least-Squares Regression
Shunhua Jiang, Binghui Peng, Omri Weinstein
|
👻
Ghosted
|
cs.DS
|
6 |
4 years ago |
| 474 |
Deterministic Almost-Linear-Time Gomory-Hu Trees
Amir Abboud, Rasmus Kyng, ... (+6 more)
|
👻
Ghosted
|
cs.DS
|
5 |
12 months ago |
| 475 |
The Quasi-Polynomial Low-Degree Conjecture is False
Rares-Darius Buhai, Jun-Ting Hsieh, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
5 |
1 year ago |
| 476 |
Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
Yumou Fei, Dor Minzer, Shuo Wang
|
👻
Ghosted
|
cs.DS
|
5 |
1 year ago |
| 477 |
Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models
Ilias Diakonikolas, Daniel M. Kane
|
👻
Ghosted
|
cs.DS
|
5 |
1 year ago |
| 478 |
Spectral Guarantees for Adversarial Streaming PCA
Eric Price, Zhiyang Xun
|
👻
Ghosted
|
cs.DS
|
5 |
1 year ago |
| 479 |
Revisiting Agnostic PAC Learning
Steve Hanneke, Kasper Green Larsen, Nikita Zhivotovskiy
|
👻
Ghosted
|
cs.LG
|
5 |
1 year ago |
| 480 |
Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem
Simone Fioravanti, Steve Hanneke, ... (+3 more)
|
👻
Ghosted
|
cs.LG
|
5 |
2 years ago |
| 481 |
Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
Sayan Bhattacharya, Din Carmon, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
5 |
2 years ago |
| 482 |
Semirandom Planted Clique and the Restricted Isometry Property
Jarosław Błasiok, Rares-Darius Buhai, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
5 |
2 years ago |
| 483 |
Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
Friedrich Eisenbrand, Lars Rohwedder, Karol Węgrzycki
|
👻
Ghosted
|
cs.DS
|
5 |
2 years ago |
| 484 |
Testing Graph Properties with the Container Method
Eric Blais, Cameron Seth
|
👻
Ghosted
|
cs.DS
|
5 |
2 years ago |
| 485 |
Chasing Positive Bodies
Sayan Bhattacharya, Niv Buchbinder, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
5 |
3 years ago |
| 486 |
Singular Value Approximation and Sparsifying Random Walks on Directed Graphs
AmirMahdi Ahmadinejad, John Peebles, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
5 |
3 years ago |
| 487 |
Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries
Dor Minzer, Kai Zheng
|
🔮
The Ethereal
|
cs.CC
|
5 |
3 years ago |
| 488 |
Lazy Search Trees
Bryce Sandlund, Sebastian Wild
|
👻
Ghosted
|
cs.DS
|
5 |
5 years ago |
| 489 |
Fast generalized DFTs for all finite groups
Chris Umans
|
👻
Ghosted
|
cs.DS
|
5 |
7 years ago |
| 490 |
Heavy-tailed Independent Component Analysis
Joseph Anderson, Navin Goyal, ... (+2 more)
|
👻
Ghosted
|
cs.LG
|
5 |
10 years ago |
| 491 |
Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
Vijay Bhattiprolu, Venkatesan Guruswami, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
5 |
1 year ago |
| 492 |
Commitments are equivalent to statistically-verifiable one-way state generators
Rishabh Batra, Rahul Jain
|
👻
Ghosted
|
quant-ph
|
5 |
2 years ago |
| 493 |
Towards Separating Computational and Statistical Differential Privacy
Badih Ghazi, Rahul Ilango, ... (+3 more)
|
👻
Ghosted
|
cs.CR
|
5 |
3 years ago |
| 494 |
An Improved Bound for the Beck-Fiala Conjecture
Nikhil Bansal, Haotian Jiang
|
🔮
The Ethereal
|
math.CO
|
4 |
11 months ago |
| 495 |
Faster logconcave sampling from a cold start in high dimension
Yunbum Kook, Santosh S. Vempala
|
👻
Ghosted
|
cs.DS
|
4 |
1 year ago |
| 496 |
Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest
Ali Ahmadi, Iman Gholami, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
4 |
1 year ago |
| 497 |
Optimal Smoothed Analysis of the Simplex Method
Eleon Bach, Sophie Huiberts
|
👻
Ghosted
|
cs.DS
|
4 |
1 year ago |
| 498 |
Robust Learning of Multi-index Models via Iterative Subspace Approximation
Ilias Diakonikolas, Giannis Iakovidis, ... (+2 more)
|
👻
Ghosted
|
cs.LG
|
4 |
1 year ago |
| 499 |
Overcomplete Tensor Decomposition via Koszul-Young Flattenings
Pravesh K. Kothari, Ankur Moitra, Alexander S. Wein
|
👻
Ghosted
|
cs.DS
|
4 |
1 year ago |
| 500 |
An Optimal Algorithm for Sorting Pattern-Avoiding Sequences
Michal Opler
|
👻
Ghosted
|
cs.DS
|
4 |
1 year ago |