Cover Image

Average-Distortion Sketching

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bao, Yiqiao, Baweja, Anubhav, Menand, Nicolas, Waingarten, Erik, White, Nathan, Zhang, Tian
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Streaming and Massively Parallel Algorithms for Euclidean Max-Cut
by: Menand, Nicolas, et al.
Published: (2025)

Nearly Tight Bounds on Testing of Metric Properties
by: Bao, Yiqiao, et al.
Published: (2024)

Data-Dependent LSH for the Earth Mover's Distance
by: Jayaram, Rajesh, et al.
Published: (2024)

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
by: Charikar, Moses, et al.
Published: (2024)

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
by: Khanna, Sanjeev, et al.
Published: (2025)

Prune, Don't Rebuild: Efficiently Tuning $α$-Reachable Graphs for Nearest Neighbor Search
by: Zhang, Tian, et al.
Published: (2026)

Instance-Optimal Uniformity Testing and Tracking
by: Blanc, Guy, et al.
Published: (2025)

Testing noisy low-degree polynomials for sparsity
by: Bao, Yiqiao, et al.
Published: (2025)

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
by: Beretta, Lorenzo, et al.
Published: (2025)

Lower Bounds for Convexity Testing
by: Chen, Xi, et al.
Published: (2024)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

On Sketching Quadratic Forms
by: Andoni, Alexandr, et al.
Published: (2015)

On Sketching Trimmed Statistics
by: Lin, Honghao, et al.
Published: (2025)

Fast Similarity Sketching
by: Dahlgaard, Søren, et al.
Published: (2017)

LMQ-Sketch: Lagom Multi-Query Sketch for High-Rate Online Analytics
by: Hilgendorf, Martin, et al.
Published: (2025)

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
by: Gao, Jie, et al.
Published: (2025)

The Case for External Graph Sketching
by: Bender, Michael A., et al.
Published: (2025)

Sketching and Streaming for Dictionary Compression
by: Becker, Ruben, et al.
Published: (2023)

Sketching Cuts in Graphs and Hypergraphs
by: Kogan, Dmitry, et al.
Published: (2014)

Fast Sampling Based Sketches for Tensors
by: Swartworth, William, et al.
Published: (2024)

Approximating Tensor Network Contraction with Sketches
by: Heddes, Mike, et al.
Published: (2026)

On Differential Privacy for Adaptively Solving Search Problems via Sketching
by: Feng, Shiyuan, et al.
Published: (2025)

Almost Linear Size Edit Distance Sketch
by: Koucký, Michal, et al.
Published: (2024)

Fast and Compact Sketch-Based Dynamic Connectivity
by: De Man, Quinten, et al.
Published: (2025)

ResidualSketch: Enhancing Layer Efficiency and Error Reduction in Hierarchical Heavy Hitter Detection with ResNet Innovations
by: Liu, Xilai, et al.
Published: (2025)

Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance
by: Song, Zhao, et al.
Published: (2022)

Sampling Methods for Inner Product Sketching
by: Daliri, Majid, et al.
Published: (2023)

SimiSketch: Efficiently Estimating Similarity of streaming Multisets
by: Dong, Fenghao, et al.
Published: (2024)

Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs
by: Ahmadian, Sara, et al.
Published: (2024)

Multipass Linear Sketches for Geometric LP-Type Problems
by: Çekirge, N. Efe, et al.
Published: (2025)

Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
by: Gribelyuk, Elena, et al.
Published: (2025)

MagnifierSketch: Quantile Estimation Centered at One Point
by: Guo, Jiarui, et al.
Published: (2025)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
by: Khanna, Sanjeev, et al.
Published: (2024)

Carbonyl4: A Sketch for Set-Increment Mixed Updates
by: Zhao, Yikai, et al.
Published: (2024)

Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
by: Cohen, Edith, et al.
Published: (2025)

Average sensitivity of the Knapsack Problem
by: Kumabe, Soh, et al.
Published: (2024)

Inner Product Aware Quantization: Provably Fast, Accurate, and Adaptive Algorithms
by: White, Nathan, et al.
Published: (2026)

A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates
by: Sawettamalya, Pachara, et al.
Published: (2025)

Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems
by: Alman, Josh, et al.
Published: (2024)

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