Peter Manohar

activity

20242026

collaborators

Showing 2025Show all

3 papers · 1 filter

cs.CC2025

Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes

Elena Grigorescu, Vinayak M. Kumar, Peter Manohar +1

A locally decodable code (LDC) $C : {0, 1}^{k} \to {0, 1}^{n}$ is an error-correcting code that allows one to recover any bit of the original message with good probability while…

cs.DS2025

Spectral Refutations of Semirandom $k$ -LIN over Larger Fields

Nicholas Kocurek, Peter Manohar

We study the problem of strongly refuting semirandom $k$ -LIN $(F)$ instances: systems of $k$ -sparse inhomogeneous linear equations over a finite field $F$ . For the…

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…

Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes

Spectral Refutations of Semirandom k-LIN over Larger Fields

Solving Random Planted CSPs below the nk/2 Threshold

Spectral Refutations of Semirandom $k$ -LIN over Larger Fields

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