Image de couverture de livre

Fast White-Box Adversarial Streaming Without a Random Oracle

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Feng, Ying, Jain, Aayush, Woodruff, David P.
Format:	Preprint
Publié:	2024
Sujets:	Data Structures and Algorithms Machine Learning
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions
par: Kannan, Ravindran, et autres
Publié: (2024)

Approximating the Top Eigenvector in Random Order Streams
par: Kacham, Praneeth, et autres
Publié: (2024)

Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation
par: Woodruff, David P., et autres
Publié: (2024)

Reweighted Solutions for Weighted Low Rank Approximation
par: Woodruff, David P., et autres
Publié: (2024)

Coresets for Multiple $\ell_p$ Regression
par: Woodruff, David P., et autres
Publié: (2024)

Better Bounds for the Distributed Experts Problem
par: Woodruff, David P., et autres
Publié: (2026)

Sharper Bounds for $\ell_p$ Sensitivity Sampling
par: Woodruff, David P., et autres
Publié: (2023)

John Ellipsoids via Lazy Updates
par: Woodruff, David P., et autres
Publié: (2025)

Accelerating Matroid Optimization through Fast Imprecise Oracles
par: Eberle, Franziska, et autres
Publié: (2024)

Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms
par: Li, Yi, et autres
Publié: (2024)

Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
par: Silwal, Sandeep, et autres
Publié: (2025)

Adversarial Robustness on Insertion-Deletion Streams
par: Gribelyuk, Elena, et autres
Publié: (2026)

Spectral Guarantees for Adversarial Streaming PCA
par: Price, Eric, et autres
Publié: (2024)

On Socially Fair Low-Rank Approximation and Column Subset Selection
par: Song, Zhao, et autres
Publié: (2024)

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
par: Cohen-Addad, Vincent, et autres
Publié: (2025)

Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph
par: Kamath, Gautam, et autres
Publié: (2025)

$L_p$ Sampling in Distributed Data Streams with Applications to Adversarial Robustness
par: Lin, Honghao, et autres
Publié: (2025)

Online Learning with Limited Information in the Sliding Window Model
par: Braverman, Vladimir, et autres
Publié: (2026)

Learning the Positions in CountSketch
par: Li, Yi, et autres
Publié: (2023)

Learning-Augmented Moment Estimation on Time-Decay Models
par: Nagawanshi, Soham, et autres
Publié: (2026)

Fast and Accurate Triangle Counting in Graph Streams Using Predictions
par: Boldrin, Cristian, et autres
Publié: (2024)

Guessing Efficiently for Constrained Subspace Approximation
par: Bhaskara, Aditya, et autres
Publié: (2025)

Connectivity Oracles for Predictable Vertex Failures
par: Hu, Bingbing, et autres
Publié: (2023)

Provable Quantization with Randomized Hadamard Transform
par: Feng, Ying, et autres
Publié: (2026)

Fast Sampling Based Sketches for Tensors
par: Swartworth, William, et autres
Publié: (2024)

Query-Efficient Correlation Clustering with Noisy Oracle
par: Kuroki, Yuko, et autres
Publié: (2024)

Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters
par: Woodruff, David P., et autres
Publié: (2024)

Streaming Algorithms with Few State Changes
par: Jayaram, Rajesh, et autres
Publié: (2024)

Top-k on a Budget: Adaptive Ranking with Weak and Strong Oracles
par: Oettershagen, Lutz
Publié: (2026)

Improved and Oracle-Efficient Online $\ell_1$-Multicalibration
par: Ghuge, Rohan, et autres
Publié: (2025)

Matroid Algorithms Under Size-Sensitive Independence Oracles
par: Banihashem, Kiarash, et autres
Publié: (2026)

Sublinear Time Quantum Sensitivity Sampling
par: Song, Zhao, et autres
Publié: (2025)

Metric $k$-clustering using only Weak Comparison Oracles
par: Raychaudhury, Rahul, et autres
Publié: (2026)

Perfect Sampling in Turnstile Streams Beyond Small Moments
par: Woodruff, David P., et autres
Publié: (2025)

Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning
par: Attias, Idan, et autres
Publié: (2025)

Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond
par: Axiotis, Kyriakos, et autres
Publié: (2024)

Unrolled denoising networks provably learn optimal Bayesian inference
par: Karan, Aayush, et autres
Publié: (2024)

Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
par: Kacham, Praneeth, et autres
Publié: (2023)

Range Counting Oracles for Geometric Problems
par: Driemel, Anne, et autres
Publié: (2025)

Unbiased Insights: Optimal Streaming Algorithms for $\ell_p$ Sampling, the Forget Model, and Beyond
par: Lin, Honghao, et autres
Publié: (2025)