Cover Image

Provable Quantization with Randomized Hadamard Transform

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Feng, Ying, Indyk, Piotr, Kapralov, Michael, Krachun, Dmitry, Prokhorov, Boris
Format:	Preprint
Published:	2026
Subjects:	Machine Learning Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions
by: Indyk, Piotr, et al.
Published: (2025)

Optimal Algorithms for Augmented Testing of Discrete Distributions
by: Aliakbarpour, Maryam, et al.
Published: (2024)

Even Faster Algorithm for the Chamfer Distance
by: Feng, Ying, et al.
Published: (2025)

A Bi-metric Framework for Fast Similarity Search
by: Xu, Haike, et al.
Published: (2024)

Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven
by: Ben-Basat, Ran, et al.
Published: (2026)

Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors
by: Chatziafratis, Vaggos, et al.
Published: (2023)

Statistical-Computational Trade-offs for Density Estimation
by: Aamand, Anders, et al.
Published: (2024)

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

A Provably Accurate Randomized Sampling Algorithm for Logistic Regression
by: Chowdhury, Agniva, et al.
Published: (2024)

Fast White-Box Adversarial Streaming Without a Random Oracle
by: Feng, Ying, et al.
Published: (2024)

Recovering Communities in Structured Random Graphs
by: Kapralov, Michael, et al.
Published: (2026)

Efficient and Provable Algorithms for Covariate Shift
by: Adil, Deeksha, et al.
Published: (2025)

Streaming Attention Approximation via Discrepancy Theory
by: Kochetkova, Ekaterina, et al.
Published: (2025)

Dynamic Spectral Clustering with Provable Approximation Guarantee
by: Laenen, Steinar, et al.
Published: (2024)

Provably learning a multi-head attention layer
by: Chen, Sitan, et al.
Published: (2024)

Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch
by: Arvanitakis, Dionysis, et al.
Published: (2026)

Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds
by: Kapralov, Michael, et al.
Published: (2022)

On the adversarial robustness of Locality-Sensitive Hashing in Hamming space
by: Kapralov, Michael, et al.
Published: (2024)

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

Spectral Clustering in Birthday Paradox Time
by: Kapralov, Michael, et al.
Published: (2026)

Online Learning in the Random Order Model
by: Bernasconi, Martino, et al.
Published: (2025)

Active Learning for Decision Trees with Provable Guarantees
by: Moakhar, Arshia Soltani, et al.
Published: (2026)

On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models
by: Bhaskara, Aditya, et al.
Published: (2024)

Improving LSH via Tensorized Random Projection
by: Verma, Bhisham Dev, et al.
Published: (2024)

Learning Juntas under Markov Random Fields
by: Chandrasekaran, Gautam, et al.
Published: (2025)

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

Provably Extracting the Features from a General Superposition
by: Liu, Allen
Published: (2025)

Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random
by: Chandrasekaran, Gautam, et al.
Published: (2025)

Graph-based Nearest Neighbors with Dynamic Updates via Random Walks
by: Mishra, Nina, et al.
Published: (2025)

Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model
by: Burathep, Kunanon, et al.
Published: (2025)

Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
by: Chen, Hongjie, et al.
Published: (2024)

On the Streaming Complexity of Expander Decomposition
by: Chen, Yu, et al.
Published: (2024)

Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
by: Jiang, Shunhua, et al.
Published: (2025)

Streaming Algorithms for Connectivity Augmentation
by: Jin, Ce, et al.
Published: (2024)

Graph-Based Algorithms for Diverse Similarity Search
by: Anand, Piyush, et al.
Published: (2025)

Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees
by: Lebeda, Christian Janos, et al.
Published: (2026)

From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model
by: Sakaue, Shinsaku, et al.
Published: (2026)

A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values
by: Chen, Tyler, et al.
Published: (2025)

Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics
by: Gaitonde, Jason, et al.
Published: (2024)

Provably Learning from Modern Language Models via Low Logit Rank
by: Golowich, Noah, et al.
Published: (2025)