Arpon Basu

collaborators

3 papers

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 $n^{k /2}$ Threshold

Arpon Basu, Jun-Ting Hsieh, Andrew D. Lin +1

We present a family of algorithms to solve random planted instances of any $k$ -ary Boolean constraint satisfaction problem (CSP). A randomly planted instance of a Boolean CSP is ge…

cs.CC2024

Improved Lower Bounds for all Odd-Query Locally Decodable Codes

Arpon Basu, Jun-Ting Hsieh, Pravesh K. Kothari +1

We prove that for every odd $q \geq 3$ , any $q$ -query binary, possibly non-linear locally decodable code ( $q$ -LDC) $E : {\pm 1}^{k} \to {\pm 1}^{n}$ must satisfy $k \leq \tilde{…

Sparsifying Sums of Positive Semidefinite Matrices

Solving Random Planted CSPs below the nk/2 Threshold

Improved Lower Bounds for all Odd-Query Locally Decodable Codes

Solving Random Planted CSPs below the $n^{k /2}$ Threshold