| 301 |
Provably learning a multi-head attention layer
Sitan Chen, Yuanzhi Li
|
👻
Ghosted
|
cs.LG
|
21 |
2 years ago |
| 302 |
Optimal Bounds for Noisy Sorting
Yuzhou Gu, Yinzhan Xu
|
👻
Ghosted
|
cs.DS
|
21 |
3 years ago |
| 303 |
No distributed quantum advantage for approximate graph coloring
Xavier Coiteux-Roy, Francesco d'Amore, ... (+8 more)
|
👻
Ghosted
|
cs.DC
|
21 |
3 years ago |
| 304 |
On codes decoding a constant fraction of errors on the BSC
Alex Samorodnitsky, Ori Sberlo
|
👻
Ghosted
|
cs.IT
|
21 |
5 years ago |
| 305 |
Data Structures Meet Cryptography: 3SUM with Preprocessing
Alexander Golovnev, Siyao Guo, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
21 |
7 years ago |
| 306 |
An improved approximation algorithm for ATSP
Vera Traub, Jens Vygen
|
🔮
The Ethereal
|
cs.DM
|
21 |
6 years ago |
| 307 |
Smoothed complexity of local Max-Cut and binary Max-CSP
Xi Chen, Chenghao Guo, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
21 |
6 years ago |
| 308 |
Stronger L2/L2 Compressed Sensing; Without Iterating
Vasileios Nakos, Zhao Song
|
👻
Ghosted
|
cs.DS
|
21 |
7 years ago |
| 309 |
Metric Embedding via Shortest Path Decompositions
Ittai Abraham, Arnold Filtser, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
21 |
8 years ago |
| 310 |
Learning Arbitrary Statistical Mixtures of Discrete Distributions
Jian Li, Yuval Rabani, ... (+2 more)
|
👻
Ghosted
|
cs.LG
|
21 |
11 years ago |
| 311 |
Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme
Hu Fu, Jiawei Li, Daogao Liu
|
👻
Ghosted
|
cs.DS
|
21 |
4 years ago |
| 312 |
(Fractional) Online Stochastic Matching via Fine-Grained Offline Statistics
Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu
|
👻
Ghosted
|
cs.DS
|
21 |
4 years ago |
| 313 |
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 |
| 314 |
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 |
| 315 |
Tree Embeddings for Hop-Constrained Network Design
Bernhard Haeupler, D Ellis Hershkowitz, Goran Zuzic
|
👻
Ghosted
|
cs.DS
|
20 |
5 years ago |
| 316 |
Achieving Optimal Backlog in Multi-Processor Cup Games
Michael A. Bender, Martin Farach-Colton, William Kuszmaul
|
👻
Ghosted
|
cs.DS
|
20 |
7 years ago |
| 317 |
Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards
Alessandro Arlotto, Xinchang Xie
|
👻
Ghosted
|
math.PR
|
20 |
7 years ago |
| 318 |
Why Extension-Based Proofs Fail
Dan Alistarh, James Aspnes, ... (+3 more)
|
👻
Ghosted
|
cs.DC
|
20 |
7 years ago |
| 319 |
A Characterization of List Learnability
Moses Charikar, Chirag Pabbaraju
|
👻
Ghosted
|
stat.ML
|
20 |
3 years ago |
| 320 |
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 |
| 321 |
Spectral hypergraph sparsification via chaining
James R. Lee
|
👻
Ghosted
|
math.PR
|
20 |
3 years ago |
| 322 |
0-1 Knapsack in Nearly Quadratic Time
Ce Jin
|
👻
Ghosted
|
cs.DS
|
19 |
2 years ago |
| 323 |
The Number of Minimum $k$-Cuts: Improving the Karger-Stein Bound
Anupam Gupta, Euiwoong Lee, Jason Li
|
👻
Ghosted
|
cs.DS
|
19 |
7 years ago |
| 324 |
Fast hashing with Strong Concentration Bounds
Anders Aamand, Jakob B. T. Knudsen, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
19 |
7 years ago |
| 325 |
An Adaptive Sublinear-Time Block Sparse Fourier Transform
Volkan Cevher, Michael Kapralov, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
19 |
9 years ago |
| 326 |
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 |
| 327 |
Memory Bounds for the Experts Problem
Vaidehi Srinivas, David P. Woodruff, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
19 |
4 years ago |
| 328 |
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 |
| 329 |
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Ran Duan, Jiayi Mao, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
18 |
1 year ago |
| 330 |
Online Edge Coloring is (Nearly) as Easy as Offline
Joakim Blikstad, Ola Svensson, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
18 |
2 years ago |
| 331 |
An optimal tradeoff between entanglement and copy complexity for state tomography
Sitan Chen, Jerry Li, Allen Liu
|
👻
Ghosted
|
quant-ph
|
18 |
2 years ago |
| 332 |
Solving Dense Linear Systems Faster Than via Preconditioning
Michał Dereziński, Jiaming Yang
|
👻
Ghosted
|
cs.DS
|
18 |
2 years ago |
| 333 |
Knapsack with Small Items in Near-Quadratic Time
Karl Bringmann
|
👻
Ghosted
|
cs.DS
|
18 |
2 years ago |
| 334 |
Optimal Eigenvalue Approximation via Sketching
William Swartworth, David P. Woodruff
|
👻
Ghosted
|
cs.DS
|
18 |
3 years ago |
| 335 |
New Subset Selection Algorithms for Low Rank Approximation: Offline and Online
David P. Woodruff, Taisuke Yasuda
|
👻
Ghosted
|
cs.DS
|
18 |
3 years ago |
| 336 |
Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs
Mina Dalirrooyfard, Nicole Wein
|
👻
Ghosted
|
cs.DS
|
18 |
5 years ago |
| 337 |
A Unified Framework for Light Spanners
Hung Le, Shay Solomon
|
👻
Ghosted
|
cs.DS
|
18 |
5 years ago |
| 338 |
On the computability of continuous maximum entropy distributions with applications
Jonathan Leake, Nisheeth K. Vishnoi
|
👻
Ghosted
|
cs.DS
|
18 |
6 years ago |
| 339 |
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 |
| 340 |
Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
Arun Jambulapati, Yin Tat Lee, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
18 |
6 years ago |
| 341 |
Dynamic Sampling from Graphical Models
Weiming Feng, Nisheeth K. Vishnoi, Yitong Yin
|
👻
Ghosted
|
cs.DS
|
18 |
8 years ago |
| 342 |
From Independence to Expansion and Back Again
Tobias Christiani, Rasmus Pagh, Mikkel Thorup
|
👻
Ghosted
|
cs.DS
|
18 |
11 years ago |
| 343 |
On Optimal Coreset Construction for Euclidean $(k,z)$-Clustering
Lingxiao Huang, Jian Li, Xuan Wu
|
👻
Ghosted
|
cs.DS
|
18 |
3 years ago |
| 344 |
Six Candidates Suffice to Win a Voter Majority
Moses Charikar, Alexandra Lassota, ... (+3 more)
|
👻
Ghosted
|
cs.GT
|
17 |
1 year ago |
| 345 |
Trickle-Down in Localization Schemes and Applications
Nima Anari, Frederic Koehler, Thuy-Duong Vuong
|
👻
Ghosted
|
math.PR
|
17 |
1 year ago |
| 346 |
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 |
| 347 |
Fully Dynamic Approximation of LIS in Polylogarithmic Time
Paweł Gawrychowski, Wojciech Janczewski
|
👻
Ghosted
|
cs.DS
|
17 |
5 years ago |
| 348 |
Fully-dynamic Planarity Testing in Polylogarithmic Time
Jacob Holm, Eva Rotenberg
|
👻
Ghosted
|
cs.DS
|
17 |
6 years ago |
| 349 |
Routing under Balance
Alina Ene, Gary Miller, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
17 |
10 years ago |
| 350 |
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 |