Cover Image

$\ell_2/\ell_2$ Sparse Recovery via Weighted Hypergraph Peeling

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Fischer, Nick, Nakos, Vasileios
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Beating Bellman's Algorithm for Subset Sum
by: Bringmann, Karl, et al.
Published: (2024)

A $2\ell k$ Kernel for $\ell$-Component Order Connectivity
by: Kumar, Mithilesh, et al.
Published: (2016)

Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation
by: Munteanu, Alexander, et al.
Published: (2024)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
by: Makarychev, Yury, et al.
Published: (2024)

Minimizing $\ell_2$ Norm of Flow Time by Starvation Mitigation
by: Kuo, Tung-Wei
Published: (2021)

Optimally detecting uniformly-distributed $\ell_2$ heavy hitters in data streams
by: Velusamy, Santhoshini, et al.
Published: (2025)

Listing Even Cycles Faster than the Submodular-Width Barrier
by: Nakos, Vasileios, et al.
Published: (2026)

Fast Dimensionality Reduction from $\ell_2$ to $\ell_p$
by: Chiclana, Rafael, et al.
Published: (2025)

On Finding $\ell$-th Smallest Perfect Matchings
by: Maalouly, Nicolas El, et al.
Published: (2025)

Dynamic Metric Embedding into $\ell_p$ Space
by: Banihashem, Kiarash, et al.
Published: (2024)

Algorithms and Hardness Results for the $(k,\ell)$-Cover Problem
by: Madani, Amirali, et al.
Published: (2025)

Faster Approximate Fixed Points of $\ell_\infty$-Contractions
by: Feodorov, Andrei, et al.
Published: (2026)

Quadratic-Time Algorithm for the Maximum-Weight $(k, \ell)$-Sparse Subgraph Problem
by: Deák, Bence, et al.
Published: (2025)

Targeted Least Cardinality Candidate Key for Relational Databases
by: Nakos, Vasileios, et al.
Published: (2024)

Embedding Probability Distributions into Low Dimensional $\ell_1$: Tree Ising Models via Truncated Metrics
by: Charikar, Moses, et al.
Published: (2023)

A Strong Separation for Adversarially Robust $\ell_0$ Estimation for Linear Sketches
by: Gribelyuk, Elena, et al.
Published: (2024)

Coresets for Multiple $\ell_p$ Regression
by: Woodruff, David P., et al.
Published: (2024)

Node-Weighted Triangles: Faster and Simpler
by: Akmal, Shyan, et al.
Published: (2026)

Unbiased Insights: Optimal Streaming Algorithms for $\ell_p$ Sampling, the Forget Model, and Beyond
by: Lin, Honghao, et al.
Published: (2025)

The $\ell_p$-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines
by: Li, Yi, et al.
Published: (2022)

Improved $\ell_{p}$ Regression via Iteratively Reweighted Least Squares
by: Ene, Alina, et al.
Published: (2025)

Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses
by: Fischer, Nick
Published: (2026)

Sumsets, 3SUM, Subset Sum: Now for Real!
by: Fischer, Nick
Published: (2024)

Sharper Bounds for $\ell_p$ Sensitivity Sampling
by: Woodruff, David P., et al.
Published: (2023)

Near-Optimal Constructive Bounds for $\ell_2$ Prefix Discrepancy and Steinitz Problems via Affine Spectral Independence
by: Dutta, Kunal, et al.
Published: (2026)

All-Pairs Shortest Paths with Few Weights per Node
by: Abboud, Amir, et al.
Published: (2025)

Improved and Oracle-Efficient Online $\ell_1$-Multicalibration
by: Ghuge, Rohan, et al.
Published: (2025)

Turnstile $\ell_p$ leverage score sampling with applications
by: Munteanu, Alexander, et al.
Published: (2024)

A near-linear time approximation scheme for $(k,\ell)$-median clustering under discrete Fréchet distance
by: Driemel, Anne, et al.
Published: (2025)

The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation
by: Ahmadian, Sara, et al.
Published: (2025)

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
by: Fischer, Nick, et al.
Published: (2024)

Improved Sparse Recovery for Approximate Matrix Multiplication
by: Uffenheimer, Yahel, et al.
Published: (2026)

Sample-efficient Multiclass Calibration under $\ell_{p}$ Error
by: Bairaktari, Konstantina, et al.
Published: (2025)

Acceleration Meets Inverse Maintenance: Faster $\ell_{\infty}$-Regression
by: Adil, Deeksha, et al.
Published: (2024)

Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation
by: Woodruff, David P., et al.
Published: (2024)

Simultaneously Approximating All $\ell_p$-norms in Correlation Clustering
by: Davies, Sami, et al.
Published: (2023)

Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts
by: Fischer, Nick, et al.
Published: (2026)

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
by: Fischer, Nick, et al.
Published: (2024)

A face cover perspective to $\ell_1$ embeddings of planar graphs
by: Filtser, Arnold
Published: (2019)

Efficient Algorithms and Implementations for Extracting Maximum-Size $(k,\ell)$-Sparse Subgraphs
by: Madarasi, Péter
Published: (2025)