Cover Image

Entrywise Low-Rank Approximation and Matrix $p \rightarrow q$ Norms via Global Correlation Rounding

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Anderson, Prashanti, Bakshi, Ainesh, Hopkins, Samuel B.
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Additive Approximation Schemes for Low-Dimensional Embeddings
by: Anderson, Prashanti, et al.
Published: (2025)

Faster MAX-CUT on Bounded Threshold Rank Graphs
by: Anderson, Prashanti, et al.
Published: (2025)

Sample-Optimal Private Regression in Polynomial Time
by: Anderson, Prashanti, et al.
Published: (2025)

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
by: Bakshi, Ainesh, et al.
Published: (2023)

An Improved Classical Singular Value Transformation for Quantum Machine Learning
by: Bakshi, Ainesh, et al.
Published: (2023)

Entrywise Approximate Laplacian Solving
by: Chen, Jingbang, et al.
Published: (2024)

Approximating $q \rightarrow p$ Norms of Non-Negative Matrices in Nearly-Linear Time
by: Objois, Étienne, et al.
Published: (2025)

Rapid mixing for high-temperature Gibbs states with arbitrary external fields
by: Bakshi, Ainesh, et al.
Published: (2026)

A Dobrushin condition for quantum Markov chains: Rapid mixing and conditional mutual information at high temperature
by: Bakshi, Ainesh, et al.
Published: (2025)

Faster Algorithms for Schatten-p Low Rank Approximation
by: Kacham, Praneeth, et al.
Published: (2024)

Simultaneously Approximating All Norms for Massively Parallel Correlation Clustering
by: Cao, Nairen, et al.
Published: (2024)

Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
by: Bakshi, Ainesh, et al.
Published: (2026)

Consistent Low-Rank Approximation
by: Woodruff, David P., et al.
Published: (2026)

Efficient Certificates of Anti-Concentration Beyond Gaussians
by: Bakshi, Ainesh, et al.
Published: (2024)

Structure learning of Hamiltonians from real-time evolution
by: Bakshi, Ainesh, et al.
Published: (2024)

Learning quantum Hamiltonians at any temperature in polynomial time
by: Bakshi, Ainesh, et al.
Published: (2023)

High-Temperature Gibbs States are Unentangled and Efficiently Preparable
by: Bakshi, Ainesh, et al.
Published: (2024)

Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding
by: Friggstad, Zachary, et al.
Published: (2025)

Supermodular Approximation of Norms and Applications
by: Kesselheim, Thomas, et al.
Published: (2024)

3.415-Approximation for Coflow Scheduling via Iterated Rounding
by: Rohwedder, Lars, et al.
Published: (2025)

FPT Approximations for Fair Sum of Radii with Outliers and General Norm Objectives
by: Gadekar, Ameet
Published: (2026)

Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously
by: Kaul, Matthias, et al.
Published: (2025)

Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
by: Brakensiek, Joshua, et al.
Published: (2026)

Improved Approximation for Ranking on General Graphs
by: Derakhshan, Mahsa, et al.
Published: (2025)

Reweighted Solutions for Weighted Low Rank Approximation
by: Woodruff, David P., et al.
Published: (2024)

$k$-Clustering via Iterative Randomized Rounding
by: Byrka, Jarosław, et al.
Published: (2026)

Proportionally Fair Matching via Randomized Rounding
by: Duppala, Sharmila, et al.
Published: (2024)

Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs
by: Li, Shi
Published: (2024)

The Change-of-Measure Method, Block Lewis Weights, and Approximating Matrix Block Norms
by: Manoj, Naren Sarayu, et al.
Published: (2023)

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

Sublinear Time Low-Rank Approximation of Hankel Matrices
by: Kapralov, Michael, et al.
Published: (2025)

Sublinear Time Low-Rank Approximation of Toeplitz Matrices
by: Musco, Cameron, et al.
Published: (2024)

1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP
by: Lee, Dahoon, et al.
Published: (2025)

Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method
by: Garg, Sachin, et al.
Published: (2025)

(Approximate) Matrix Multiplication via Convolutions
by: Uffenheimer, Yahel, et al.
Published: (2025)

Optimal Approximate Matrix Multiplication over Sliding Window
by: Xian, Haoming, et al.
Published: (2025)

Optimal 4-Approximation for the Correlated Pandora's Problem
by: Bansal, Nikhil, et al.
Published: (2025)

Improved Combinatorial Approximations for Weighted Correlation Clustering
by: Ostovari, Mojtaba, et al.
Published: (2023)

On Socially Fair Low-Rank Approximation and Column Subset Selection
by: Song, Zhao, et al.
Published: (2024)

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
by: Chalermsook, Parinya, et al.
Published: (2021)