Peter Manohar

collaborators

4 papers

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.CC2025

A $k^{\frac{q}{q - 2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs

Oliver Janzer, Peter Manohar

A code $C : {0, 1}^{k} \to {0, 1}^{n}$ is a $q$ -query locally decodable code ( $q$ -LDC) if one can recover any chosen bit $b_{i}$ of the message $b \in {0, 1}^{k}$ with good confide…

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

A kq−2q​ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs

Solving Random Planted CSPs below the nk/2 Threshold

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

A $k^{\frac{q}{q - 2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs

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