| 201 |
Near-linear Size Hypergraph Cut Sparsifiers
Yu Chen, Sanjeev Khanna, Ansh Nagda
|
👻
Ghosted
|
cs.DS
|
36 |
5 years ago |
| 202 |
On Approximating Maximum Independent Set of Rectangles
Julia Chuzhoy, Alina Ene
|
👻
Ghosted
|
cs.DS
|
36 |
9 years ago |
| 203 |
Fully Online Matching II: Beating Ranking and Water-filling
Zhiyi Huang, Zhihao Gavin Tang, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
35 |
6 years ago |
| 204 |
General Framework for Metric Optimization Problems with Delay or with Deadlines
Yossi Azar, Noam Touitou
|
👻
Ghosted
|
cs.DS
|
35 |
7 years ago |
| 205 |
PPP-Completeness with Connections to Cryptography
Katerina Sotiraki, Manolis Zampetakis, Giorgos Zirdelis
|
🔮
The Ethereal
|
cs.CC
|
35 |
7 years ago |
| 206 |
Non-Malleable Codes for Small-Depth Circuits
Marshall Ball, Dana Dachman-Soled, ... (+3 more)
|
🔮
The Ethereal
|
cs.CC
|
35 |
8 years ago |
| 207 |
Sample Efficient Estimation and Recovery in Sparse FFT via Isolation on Average
Michael Kapralov
|
👻
Ghosted
|
cs.DS
|
35 |
8 years ago |
| 208 |
Near-optimal bounds on bounded-round quantum communication complexity of disjointness
Mark Braverman, Ankit Garg, ... (+3 more)
|
🔮
The Ethereal
|
cs.CC
|
35 |
11 years ago |
| 209 |
Almost 3-Approximate Correlation Clustering in Constant Rounds
Soheil Behnezhad, Moses Charikar, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
35 |
4 years ago |
| 210 |
Quantum eigenvalue processing
Guang Hao Low, Yuan Su
|
👻
Ghosted
|
quant-ph
|
34 |
2 years ago |
| 211 |
A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels
Emmanuel Abbe, Colin Sandon
|
👻
Ghosted
|
cs.IT
|
34 |
3 years ago |
| 212 |
Faster Matroid Intersection
Deeparnab Chakrabarty, Yin Tat Lee, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
34 |
6 years ago |
| 213 |
Efficiently Learning Mixtures of Mallows Models
Allen Liu, Ankur Moitra
|
👻
Ghosted
|
cs.DS
|
34 |
7 years ago |
| 214 |
Minor-free graphs have light spanners
Glencora Borradaile, Hung Le, Christian Wulff-Nilsen
|
👻
Ghosted
|
cs.DS
|
34 |
8 years ago |
| 215 |
Planar Graph Perfect Matching is in NC
Nima Anari, Vijay V. Vazirani
|
👻
Ghosted
|
cs.DS
|
34 |
8 years ago |
| 216 |
Linear algebraic analogues of the graph isomorphism problem and the Erdős-Rényi model
Yinan Li, Youming Qiao
|
👻
Ghosted
|
cs.DS
|
34 |
8 years ago |
| 217 |
Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering
Fedor V. Fomin, Daniel Lokshtanov, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
34 |
10 years ago |
| 218 |
Decidability of Non-Interactive Simulation of Joint Distributions
Badih Ghazi, Pritish Kamath, Madhu Sudan
|
👻
Ghosted
|
cs.IT
|
34 |
9 years ago |
| 219 |
Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models
Ilias Diakonikolas, Daniel M. Kane
|
👻
Ghosted
|
cs.LG
|
33 |
5 years ago |
| 220 |
Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms
Sepehr Assadi, Ran Raz
|
👻
Ghosted
|
cs.DS
|
33 |
5 years ago |
| 221 |
A Faster Isomorphism Test for Graphs of Small Degree
Martin Grohe, Daniel Neuen, Pascal Schweitzer
|
👻
Ghosted
|
cs.DS
|
33 |
8 years ago |
| 222 |
Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees
David Durfee, John Peebles, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
33 |
9 years ago |
| 223 |
Fast Similarity Sketching
Søren Dahlgaard, Mathias Bæk Tejs Langhede, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
33 |
9 years ago |
| 224 |
Optimizing Star-Convex Functions
Jasper C. H. Lee, Paul Valiant
|
👻
Ghosted
|
cs.DS
|
33 |
10 years ago |
| 225 |
Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
Dominik Kempa, Tomasz Kociumaka
|
👻
Ghosted
|
cs.DS
|
32 |
2 years ago |
| 226 |
Algorithms and Hardness for Linear Algebra on Geometric Graphs
Josh Alman, Timothy Chu, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
32 |
5 years ago |
| 227 |
Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time
Mahdi Cheraghchi, Vasileios Nakos
|
👻
Ghosted
|
cs.IT
|
32 |
5 years ago |
| 228 |
Reed-Muller codes polarize
Emmanuel Abbe, Min Ye
|
👻
Ghosted
|
cs.IT
|
32 |
7 years ago |
| 229 |
A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees
Rasmus Kyng, Zhao Song
|
👻
Ghosted
|
math.PR
|
32 |
7 years ago |
| 230 |
A Holant Dichotomy: Is the FKT Algorithm Universal?
Jin-Yi Cai, Zhiguo Fu, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
32 |
11 years ago |
| 231 |
New Unconditional Hardness Results for Dynamic and Online Problems
Raphael Clifford, Allan Grønlund, Kasper Green Larsen
|
👻
Ghosted
|
cs.DS
|
32 |
11 years ago |
| 232 |
Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More
Xin Li
|
🔮
The Ethereal
|
cs.CC
|
32 |
3 years ago |
| 233 |
Flip-width: Cops and Robber on dense graphs
Szymon Toruńczyk
|
🔮
The Ethereal
|
math.CO
|
31 |
3 years ago |
| 234 |
List Decodable Mean Estimation in Nearly Linear Time
Yeshwanth Cherapanamjeri, Sidhanth Mohanty, Morris Yau
|
👻
Ghosted
|
cs.DS
|
31 |
6 years ago |
| 235 |
Sublinear Algorithms for Gap Edit Distance
Elazar Goldenberg, Robert Krauthgamer, Barna Saha
|
🔮
The Ethereal
|
cs.CC
|
31 |
6 years ago |
| 236 |
Efficient Truncated Statistics with Unknown Truncation
Vasilis Kontonis, Christos Tzamos, Manolis Zampetakis
|
👻
Ghosted
|
math.ST
|
31 |
6 years ago |
| 237 |
Commutativity in the Algorithmic Lovasz Local Lemma
Vladimir Kolmogorov
|
👻
Ghosted
|
cs.DS
|
31 |
10 years ago |
| 238 |
Optimal mixing for two-state anti-ferromagnetic spin systems
Xiaoyu Chen, Weiming Feng, ... (+2 more)
|
👻
Ghosted
|
math-ph
|
31 |
4 years ago |
| 239 |
Optimal tradeoffs for estimating Pauli observables
Sitan Chen, Weiyuan Gong, Qi Ye
|
👻
Ghosted
|
quant-ph
|
30 |
2 years ago |
| 240 |
A Parameterized Approximation Scheme for Min $k$-Cut
Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan
|
👻
Ghosted
|
cs.DS
|
30 |
6 years ago |
| 241 |
Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design
Bo Peng, Zhihao Gavin Tang
|
👻
Ghosted
|
cs.DS
|
30 |
4 years ago |
| 242 |
Covering Planar Metrics (and Beyond): O(1) Trees Suffice
Hsien-Chih Chang, Jonathan Conroy, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
29 |
3 years ago |
| 243 |
Fast uniform generation of random graphs with given degree sequences
Andrii Arman, Pu Gao, Nicholas Wormald
|
🔮
The Ethereal
|
math.CO
|
29 |
7 years ago |
| 244 |
Theoretical limitations of multi-layer Transformer
Lijie Chen, Binghui Peng, Hongxun Wu
|
👻
Ghosted
|
cs.LG
|
28 |
1 year ago |
| 245 |
Structure learning of Hamiltonians from real-time evolution
Ainesh Bakshi, Allen Liu, ... (+2 more)
|
👻
Ghosted
|
quant-ph
|
28 |
2 years ago |
| 246 |
New Techniques for Proving Fine-Grained Average-Case Hardness
Mina Dalirrooyfard, Andrea Lincoln, Virginia Vassilevska Williams
|
🔮
The Ethereal
|
cs.CC
|
28 |
5 years ago |
| 247 |
Collaborative Top Distribution Identifications with Limited Interaction
Nikolai Karpov, Qin Zhang, Yuan Zhou
|
👻
Ghosted
|
cs.DS
|
28 |
6 years ago |
| 248 |
Near-Optimal Decremental SSSP in Dense Weighted Digraphs
Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
|
👻
Ghosted
|
cs.DS
|
28 |
6 years ago |
| 249 |
The Sketching Complexity of Graph and Hypergraph Counting
John Kallaugher, Michael Kapralov, Eric Price
|
👻
Ghosted
|
cs.DS
|
28 |
7 years ago |
| 250 |
Robust polynomial regression up to the information theoretic limit
Daniel Kane, Sushrut Karmalkar, Eric Price
|
👻
Ghosted
|
cs.DS
|
28 |
8 years ago |