| 551 |
On Approximating Cutwidth and Pathwidth
Nikhil Bansal, Dor Katzelnick, Roy Schwartz
|
👻
Ghosted
|
cs.DS
|
2 |
2 years ago |
| 552 |
Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence
Mohsen Ghaffari, Christoph Grunau, Václav Rozhoň
|
👻
Ghosted
|
cs.DS
|
2 |
2 years ago |
| 553 |
On Symmetric Factorizations of Hankel Matrices
Mehrdad Ghadiri
|
👻
Ghosted
|
math.NA
|
2 |
3 years ago |
| 554 |
On Pseudolinear Codes for Correcting Adversarial Errors
Eric Ruzomberka, Homa Nikbakht, ... (+2 more)
|
👻
Ghosted
|
cs.IT
|
2 |
3 years ago |
| 555 |
Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles
Guy Bresler, Chenghao Guo, Yury Polyanskiy
|
👻
Ghosted
|
math.PR
|
2 |
3 years ago |
| 556 |
Testability of relations between permutations
Oren Becker, Alexander Lubotzky, Jonathan Mosheiff
|
👻
Ghosted
|
cs.DS
|
2 |
5 years ago |
| 557 |
A computational test of quantum contextuality, and even simpler proofs of quantumness
Atul Singh Arora, Kishor Bharti, ... (+2 more)
|
👻
Ghosted
|
quant-ph
|
2 |
2 years ago |
| 558 |
Obfuscation of Unitary Quantum Programs
Mi-Ying Huang, Er-Cheng Tang
|
👻
Ghosted
|
quant-ph
|
1 |
1 year ago |
| 559 |
Fingerprint Filters Are Optimal
William Kuszmaul, Jingxun Liang, Renfei Zhou
|
👻
Ghosted
|
cs.DS
|
1 |
9 months ago |
| 560 |
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 |
| 561 |
Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
Shunhua Jiang, Michael Kapralov, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
1 |
9 months ago |
| 562 |
Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
Aaron Bernstein, Joakim Blikstad, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
1 |
9 months ago |
| 563 |
A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
Sanjeev Khanna, Ashwin Padaki, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
1 |
9 months ago |
| 564 |
Solving Zero-Sum Games with Fewer Matrix-Vector Products
Ishani Karmarkar, Liam O'Carroll, Aaron Sidford
|
👻
Ghosted
|
math.OC
|
1 |
10 months ago |
| 565 |
Finding Colorings in One-Sided Expanders
Rares-Darius Buhai, Yiding Hua, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
1 |
11 months ago |
| 566 |
Improved 2-Approximate Shortest Paths for close vertex pairs
Manoj Gupta
|
👻
Ghosted
|
cs.DS
|
1 |
12 months ago |
| 567 |
Edge-weighted Matching in the Dark
Zhiyi Huang, Enze Sun, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
1 |
12 months ago |
| 568 |
On the Parallel Complexity of Finding a Matroid Basis
Sanjeev Khanna, Aaron Putterman, Junkai Song
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 569 |
Almost Tight Additive Guarantees for $k$-Edge-Connectivity
Nikhil Kumar, Chaitanya Swamy
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 570 |
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 |
| 571 |
Stochastic scheduling with Bernoulli-type jobs through policy stratification
Antonios Antoniadis, Ruben Hoeksma, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 572 |
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 |
| 573 |
Lower Bounds for Non-adaptive Local Computation Algorithms
Amir Azarmehr, Soheil Behnezhad, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 574 |
Deterministic factorization of constant-depth algebraic circuits in subexponential time
Somnath Bhattacharjee, Mrinal Kumar, ... (+3 more)
|
🔮
The Ethereal
|
cs.CC
|
1 |
1 year ago |
| 575 |
Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
Alberto Larrauri
|
🔮
The Ethereal
|
cs.CC
|
1 |
1 year ago |
| 576 |
Faster Mixing of the Jerrum-Sinclair Chain
Xiaoyu Chen, Weiming Feng, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 577 |
Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
Jonathan Leake, Kasper Lindberg, Shayan Oveis Gharan
|
🔮
The Ethereal
|
math.CO
|
1 |
1 year ago |
| 578 |
Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
Shyam Narayanan, Václav Rozhoň, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 579 |
Fast decision tree learning solves hard coding-theoretic problems
Caleb Koch, Carmen Strassle, Li-Yang Tan
|
🔮
The Ethereal
|
cs.CC
|
1 |
1 year ago |
| 580 |
Tight Bounds for Classical Open Addressing
Michael A. Bender, William Kuszmaul, Renfei Zhou
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 581 |
Obstructions to Erdős-Pósa Dualities for Minors
Christophe Paul, Evangelos Protopapas, ... (+2 more)
|
🔮
The Ethereal
|
math.CO
|
1 |
2 years ago |
| 582 |
Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation
David P. Woodruff, Taisuke Yasuda
|
👻
Ghosted
|
cs.DS
|
1 |
2 years ago |
| 583 |
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 |
| 584 |
Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
Moise Blanchard
|
👻
Ghosted
|
math.OC
|
1 |
2 years ago |
| 585 |
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 |
| 586 |
Sparse Submodular Function Minimization
Andrei Graur, Haotian Jiang, Aaron Sidford
|
👻
Ghosted
|
cs.DS
|
1 |
2 years ago |
| 587 |
On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs
Suprovat Ghoshal, Euiwoong Lee
|
👻
Ghosted
|
cs.DS
|
1 |
2 years ago |
| 588 |
Motif Cut Sparsifiers
Michael Kapralov, Mikhail Makarov, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
1 |
4 years ago |
| 589 |
Efficiently Batching Unambiguous Interactive Proofs
Bonnie Berger, Rohan Goyal, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
0 |
9 months ago |
| 590 |
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 |
| 591 |
$\ell_2/\ell_2$ Sparse Recovery via Weighted Hypergraph Peeling
Nick Fischer, Vasileios Nakos
|
👻
Ghosted
|
cs.DS
|
0 |
9 months ago |
| 592 |
Undirected Multicast Network Coding Gaps via Locally Decodable Codes
Mark Braverman, Zhongtian He
|
🔮
The Ethereal
|
cs.CC
|
0 |
9 months ago |
| 593 |
Static Retrieval Revisited: To Optimality and Beyond
Yang Hu, William Kuszmaul, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
0 |
9 months ago |
| 594 |
Pattern Matching under Weighted Edit Distance
Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz
|
👻
Ghosted
|
cs.DS
|
0 |
9 months ago |
| 595 |
Near-Optimal Property Testers for Pattern Matching
Ce Jin, Tomasz Kociumaka
|
👻
Ghosted
|
cs.DS
|
0 |
9 months ago |
| 596 |
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 |
| 597 |
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 |
| 598 |
Near-Optimal Fault-Tolerant Strong Connectivity Preservers
Gary Hoppenworth, Thatchaphol Saranurak, Benyu Wang
|
👻
Ghosted
|
cs.DS
|
0 |
9 months ago |
| 599 |
Distance Approximating Minors for Planar and Minor-Free Graphs
Hsien-Chih Chang, Jonathan Conroy
|
👻
Ghosted
|
cs.DS
|
0 |
10 months ago |
| 600 |
Optimal 4-Approximation for the Correlated Pandora's Problem
Nikhil Bansal, Zhiyi Huang, Zixuan Zhu
|
👻
Ghosted
|
cs.DS
|
0 |
10 months ago |