Buchumschlag

Beyond Worst-Case Dimensionality Reduction for Sparse Vectors

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Silwal, Sandeep, Woodruff, David P., Zhang, Qiuyi
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms Machine Learning
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
von: Gao, Jie, et al.
Veröffentlicht: (2025)

Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms
von: Li, Yi, et al.
Veröffentlicht: (2024)

Optimal Algorithms for Augmented Testing of Discrete Distributions
von: Aliakbarpour, Maryam, et al.
Veröffentlicht: (2024)

How fast can you find a good hypothesis?
von: Aamand, Anders, et al.
Veröffentlicht: (2025)

A Bi-metric Framework for Fast Similarity Search
von: Xu, Haike, et al.
Veröffentlicht: (2024)

John Ellipsoids via Lazy Updates
von: Woodruff, David P., et al.
Veröffentlicht: (2025)

Better Bounds for the Distributed Experts Problem
von: Woodruff, David P., et al.
Veröffentlicht: (2026)

Sharper Bounds for $\ell_p$ Sensitivity Sampling
von: Woodruff, David P., et al.
Veröffentlicht: (2023)

Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation
von: Woodruff, David P., et al.
Veröffentlicht: (2024)

Reweighted Solutions for Weighted Low Rank Approximation
von: Woodruff, David P., et al.
Veröffentlicht: (2024)

Coresets for Multiple $\ell_p$ Regression
von: Woodruff, David P., et al.
Veröffentlicht: (2024)

On the Structure of Replicable Hypothesis Testers
von: Aamand, Anders, et al.
Veröffentlicht: (2025)

Improved Approximations for Hard Graph Problems using Predictions
von: Aamand, Anders, et al.
Veröffentlicht: (2025)

Learning-Augmented Frequent Directions
von: Aamand, Anders, et al.
Veröffentlicht: (2025)

Fast White-Box Adversarial Streaming Without a Random Oracle
von: Feng, Ying, et al.
Veröffentlicht: (2024)

Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysis
von: Jiang, Minhui, et al.
Veröffentlicht: (2024)

Optimal Scalarizations for Sublinear Hypervolume Regret
von: Zhang, Qiuyi
Veröffentlicht: (2023)

Dimension Reduction for Clustering: The Curious Case of Discrete Centers
von: Jiang, Shaofeng H. -C., et al.
Veröffentlicht: (2025)

Statistical-Computational Trade-offs for Density Estimation
von: Aamand, Anders, et al.
Veröffentlicht: (2024)

Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond
von: Axiotis, Kyriakos, et al.
Veröffentlicht: (2024)

On Socially Fair Low-Rank Approximation and Column Subset Selection
von: Song, Zhao, et al.
Veröffentlicht: (2024)

LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions
von: Kannan, Ravindran, et al.
Veröffentlicht: (2024)

Efficiently Computing Similarities to Private Datasets
von: Backurs, Arturs, et al.
Veröffentlicht: (2024)

Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph
von: Kamath, Gautam, et al.
Veröffentlicht: (2025)

Online Learning with Limited Information in the Sliding Window Model
von: Braverman, Vladimir, et al.
Veröffentlicht: (2026)

Learning the Positions in CountSketch
von: Li, Yi, et al.
Veröffentlicht: (2023)

Learning-Augmented Moment Estimation on Time-Decay Models
von: Nagawanshi, Soham, et al.
Veröffentlicht: (2026)

Sublinear Time Quantum Sensitivity Sampling
von: Song, Zhao, et al.
Veröffentlicht: (2025)

A Simple Sparse Matrix Vector Multiplication Approach to Padded Convolution
von: Chaudhry, Zan
Veröffentlicht: (2024)

Guessing Efficiently for Constrained Subspace Approximation
von: Bhaskara, Aditya, et al.
Veröffentlicht: (2025)

Worst-Case to Expander-Case Reductions: Derandomized and Generalized
von: Abboud, Amir, et al.
Veröffentlicht: (2024)

Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters
von: Woodruff, David P., et al.
Veröffentlicht: (2024)

Online Metric Matching: Beyond the Worst Case
von: Yang, Mingwei, et al.
Veröffentlicht: (2024)

Beyond Worst Case Local Computation Algorithms
von: Biswas, Amartya Shankha, et al.
Veröffentlicht: (2024)

A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2024)

Dynamic Data Layout Optimization with Worst-case Guarantees
von: Rong, Kexin, et al.
Veröffentlicht: (2024)

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

Robust Streaming Against Low-Memory Adversaries
von: Ben-Eliezer, Omri, et al.
Veröffentlicht: (2025)

Quantum Worst-Case to Average-Case Reduction for Matrix-Vector Multiplication
von: Aggarwal, Divesh, et al.
Veröffentlicht: (2025)

Perfect Sampling in Turnstile Streams Beyond Small Moments
von: Woodruff, David P., et al.
Veröffentlicht: (2025)