Showing 2025 · cs.DSShow all
2 papers · 2 filters
cs.DS2025
Sparsifying Sums of Positive Semidefinite Matrices
Arpon Basu, Pravesh K. Kothari, Yang P. Liu +1
In this paper, we revisit spectral sparsification for sums of arbitrary positive semidefinite (PSD) matrices. Concretely, for any collection of PSD matrices $\mathcal{A} = \{A_1, A…
cs.DS2025
Solving Random Planted CSPs below the Threshold
Arpon Basu, Jun-Ting Hsieh, Andrew D. Lin +1
We present a family of algorithms to solve random planted instances of any -ary Boolean constraint satisfaction problem (CSP). A randomly planted instance of a Boolean CSP is ge…