Cover Image

Sparsifying Sums of Positive Semidefinite Matrices

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Basu, Arpon, Kothari, Pravesh K., Liu, Yang P., Meka, Raghu
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Many Hamiltonians Are Sparsifiable
by: Basu, Arpon, et al.
Published: (2026)

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

Sum-Of-Squares To Approximate Knapsack
by: Kothari, Pravesh K., et al.
Published: (2025)

Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
by: Kothari, Pravesh K., et al.
Published: (2025)

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
by: Kothari, Pravesh, et al.
Published: (2024)

Optimal $e^{(γ+o(1))n}$-Approximation of the Permanent of Positive Semidefinite Matrices
by: Anari, Nima, et al.
Published: (2026)

Improved Certificates for Independence Number in Semirandom Hypergraphs
by: Kothari, Pravesh, et al.
Published: (2026)

Semirandom Planted Clique and the Restricted Isometry Property
by: Błasiok, Jarosław, et al.
Published: (2024)

Overcomplete Tensor Decomposition via Koszul-Young Flattenings
by: Kothari, Pravesh K., et al.
Published: (2024)

Rounding Large Independent Sets on Expanders
by: Bafna, Mitali, et al.
Published: (2024)

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
by: Abboud, Amir, et al.
Published: (2023)

Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms
by: Kalavasis, Alkis, et al.
Published: (2026)

Solving Random Planted CSPs below the $n^{k/2}$ Threshold
by: Basu, Arpon, et al.
Published: (2025)

Dynamic Kernel Graph Sparsifiers
by: Cao, Yang, et al.
Published: (2022)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
by: Chen, Yu, et al.
Published: (2026)

Sparse Linear Regression is Easy on Random Supports
by: Chandrasekaran, Gautam, et al.
Published: (2025)

The Quasi-Polynomial Low-Degree Conjecture is False
by: Buhai, Rares-Darius, et al.
Published: (2025)

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
by: Dughmi, Shaddin, et al.
Published: (2025)

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

The communication complexity of distributed estimation
by: Gopalan, Parikshit, et al.
Published: (2025)

Improved Tree Sparsifiers in Near-Linear Time
by: Agassy, Daniel, et al.
Published: (2025)

Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs
by: Zhao, Yibin
Published: (2025)

Sparsifying Cayley Graphs on Every Group
by: Hsieh, Jun-Ting, et al.
Published: (2025)

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

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
by: Das, Syamantak, et al.
Published: (2024)

Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs
by: Chen, Yu, et al.
Published: (2024)

Twice-Ramanujan Sparsifiers
by: Batson, Joshua, et al.
Published: (2008)

Unweighted One-Sided Code Sparsifiers and Thin Subgraphs
by: Gharan, Shayan Oveis, et al.
Published: (2025)

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
by: Kelner, Jonathan, et al.
Published: (2024)

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
by: Anand, Aditya, et al.
Published: (2025)

Approximation Algorithms for Digraph Width Parameters
by: Kintali, Shiva, et al.
Published: (2011)

On Convex Optimization with Semi-Sensitive Features
by: Ghazi, Badih, et al.
Published: (2024)

Tight Bounds for Sparsifying Random CSPs
by: Brakensiek, Joshua, et al.
Published: (2025)

Variational Quantum Algorithms for Semidefinite Programming
by: Patel, Dhrumil, et al.
Published: (2021)

Semidefinite Programming for the Asymmetric Stochastic Block Model
by: Gaudio, Julia, et al.
Published: (2025)

Linear-Sized Spectral Sparsifiers and the Kadison-Singer Problem
by: Paschalidis, Phevos, et al.
Published: (2023)

Sparse Random Matrices for Dimensionality Reduction
by: Mackenzie, Pierre
Published: (2025)

Distribution Testing Meets Sum Estimation
by: Pradhan, Pinki, et al.
Published: (2025)

Approximate Min-Sum Subset Convolution
by: Stoian, Mihail
Published: (2024)

FPT Approximation for Capacitated Sum of Radii
by: Jaiswal, Ragesh, et al.
Published: (2024)