| 501 |
Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
Moise Blanchard
|
👻
Ghosted
|
math.OC
|
1 |
2 years ago |
| 502 |
Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
Venkatesan Guruswami, Jun-Ting Hsieh, Prasad Raghavendra
|
👻
Ghosted
|
cs.DS
|
1 |
2 years ago |
| 503 |
Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation
David P. Woodruff, Taisuke Yasuda
|
👻
Ghosted
|
cs.DS
|
1 |
2 years ago |
| 504 |
Tight Bounds for Classical Open Addressing
Michael A. Bender, William Kuszmaul, Renfei Zhou
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 505 |
Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
Shyam Narayanan, Václav Rozhoň, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 506 |
Faster Mixing of the Jerrum-Sinclair Chain
Xiaoyu Chen, Weiming Feng, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 507 |
Lower Bounds for Non-adaptive Local Computation Algorithms
Amir Azarmehr, Soheil Behnezhad, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 508 |
Shuffling Cards When You Are of Very Little Brain: Low Memory Generation of Permutations
Boaz Menuhin, Moni Naor
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 509 |
Stochastic scheduling with Bernoulli-type jobs through policy stratification
Antonios Antoniadis, Ruben Hoeksma, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 510 |
Polynomial-Time Approximation Schemes via Utility Alignment: Unit-Demand Pricing and More
Robin Bowers, Marius Garbea, ... (+2 more)
|
👻
Ghosted
|
cs.GT
|
1 |
1 year ago |
| 511 |
Almost Tight Additive Guarantees for $k$-Edge-Connectivity
Nikhil Kumar, Chaitanya Swamy
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 512 |
On the Parallel Complexity of Finding a Matroid Basis
Sanjeev Khanna, Aaron Putterman, Junkai Song
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 513 |
Obfuscation of Unitary Quantum Programs
Mi-Ying Huang, Er-Cheng Tang
|
👻
Ghosted
|
quant-ph
|
1 |
1 year ago |
| 514 |
Edge-weighted Matching in the Dark
Zhiyi Huang, Enze Sun, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 515 |
Improved 2-Approximate Shortest Paths for close vertex pairs
Manoj Gupta
|
👻
Ghosted
|
cs.DS
|
1 |
12 months ago |
| 516 |
Finding Colorings in One-Sided Expanders
Rares-Darius Buhai, Yiding Hua, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
1 |
11 months ago |
| 517 |
Solving Zero-Sum Games with Fewer Matrix-Vector Products
Ishani Karmarkar, Liam O'Carroll, Aaron Sidford
|
👻
Ghosted
|
math.OC
|
1 |
10 months ago |
| 518 |
A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
Sanjeev Khanna, Ashwin Padaki, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
1 |
9 months ago |
| 519 |
Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks
Louis Golowich, Venkatesan Guruswami
|
👻
Ghosted
|
quant-ph
|
1 |
9 months ago |
| 520 |
Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
Aaron Bernstein, Joakim Blikstad, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
1 |
9 months ago |
| 521 |
Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
Shunhua Jiang, Michael Kapralov, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
1 |
9 months ago |
| 522 |
Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
Debarati Das, Jacob Gilbert, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
1 |
9 months ago |
| 523 |
Fingerprint Filters Are Optimal
William Kuszmaul, Jingxun Liang, Renfei Zhou
|
👻
Ghosted
|
cs.DS
|
1 |
9 months ago |
| 524 |
Coordinate Methods for Accelerating $\ell_\infty$ Regression and Faster Approximate Maximum Flow
Aaron Sidford, Kevin Tian
|
👻
Ghosted
|
cs.DS
|
0 |
7 years ago |
| 525 |
Subsets and Supermajorities: Optimal Hashing-based Set Similarity Search
Thomas Dybdahl Ahle, Jakob Bæk Tejs Knudsen
|
👻
Ghosted
|
cs.DS
|
0 |
7 years ago |
| 526 |
Resolution of the Burrows-Wheeler Transform Conjecture
Dominik Kempa, Tomasz Kociumaka
|
👻
Ghosted
|
cs.DS
|
0 |
6 years ago |
| 527 |
Naively Sorting Evolving Data is Optimal and Robust
George Giakkoupis, Marcos Kiwi, Dimitrios Los
|
👻
Ghosted
|
cs.DS
|
0 |
2 years ago |
| 528 |
Distributed Triangle Detection is Hard in Few Rounds
Sepehr Assadi, Janani Sundaresan
|
👻
Ghosted
|
cs.DS
|
0 |
1 year ago |
| 529 |
Dynamic Treewidth in Logarithmic Time
Tuukka Korhonen
|
👻
Ghosted
|
cs.DS
|
0 |
1 year ago |
| 530 |
Radial Isotropic Position via an Implicit Newton's Method
Arun Jambulapati, Jonathan Li, Kevin Tian
|
👻
Ghosted
|
cs.DS
|
0 |
1 year ago |
| 531 |
Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics
Hyung-Chan An, Mong-Jen Kao, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
0 |
1 year ago |
| 532 |
Adaptivity Gaps for Stochastic Probing with Subadditive Functions
Jian Li, Yinchen Liu, Yiran Zhang
|
👻
Ghosted
|
cs.DS
|
0 |
1 year ago |
| 533 |
Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set
Mohsen Ghaffari, Christoph Grunau
|
👻
Ghosted
|
cs.DS
|
0 |
1 year ago |
| 534 |
Parallel Repetition for Post-Quantum Arguments
Andrew Huang, Yael Tauman Kalai
|
👻
Ghosted
|
quant-ph
|
0 |
1 year ago |
| 535 |
Paths and Intersections: Exact Emulators for Planar Graphs
George Z. Li, Zihan Tan, Tianyi Zhang
|
👻
Ghosted
|
cs.DS
|
0 |
1 year ago |
| 536 |
Faster exact learning of k-term DNFs with membership and equivalence queries
Josh Alman, Shivam Nadimpalli, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
0 |
12 months ago |
| 537 |
Instance-Optimal Uniformity Testing and Tracking
Guy Blanc, Clément L. Canonne, Erik Waingarten
|
👻
Ghosted
|
cs.DS
|
0 |
11 months ago |
| 538 |
Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
Lorenzo Beretta, Vincent Cohen-Addad, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
0 |
11 months ago |
| 539 |
Integral Online Algorithms for Set Cover and Load Balancing with Convex Objectives
Thomas Kesselheim, Marco Molinaro, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
0 |
11 months ago |
| 540 |
Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum
Josh Alman, Baitian Li
|
👻
Ghosted
|
cs.DS
|
0 |
10 months ago |
| 541 |
Optimal 4-Approximation for the Correlated Pandora's Problem
Nikhil Bansal, Zhiyi Huang, Zixuan Zhu
|
👻
Ghosted
|
cs.DS
|
0 |
10 months ago |
| 542 |
Distance Approximating Minors for Planar and Minor-Free Graphs
Hsien-Chih Chang, Jonathan Conroy
|
👻
Ghosted
|
cs.DS
|
0 |
10 months ago |
| 543 |
Near-Optimal Fault-Tolerant Strong Connectivity Preservers
Gary Hoppenworth, Thatchaphol Saranurak, Benyu Wang
|
👻
Ghosted
|
cs.DS
|
0 |
9 months ago |
| 544 |
Random-Shift Revisited: Tight Approximations for Tree Embeddings and L1-Oblivious Routings
Rasmus Kyng, Maximilian Probst Gutenberg, Tim Rieder
|
👻
Ghosted
|
cs.DS
|
0 |
9 months ago |
| 545 |
Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
Amir Azarmehr, Soheil Behnezhad, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
0 |
9 months ago |
| 546 |
Near-Optimal Property Testers for Pattern Matching
Ce Jin, Tomasz Kociumaka
|
👻
Ghosted
|
cs.DS
|
0 |
9 months ago |
| 547 |
Pattern Matching under Weighted Edit Distance
Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz
|
👻
Ghosted
|
cs.DS
|
0 |
9 months ago |
| 548 |
Static Retrieval Revisited: To Optimality and Beyond
Yang Hu, William Kuszmaul, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
0 |
9 months ago |
| 549 |
$\ell_2/\ell_2$ Sparse Recovery via Weighted Hypergraph Peeling
Nick Fischer, Vasileios Nakos
|
👻
Ghosted
|
cs.DS
|
0 |
9 months ago |
| 550 |
Parallel $(1+ε)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
Bernhard Haeupler, Yonggang Jiang, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
0 |
9 months ago |