Peter Manohar

collaborators

Showing cs.DSShow all

2 papers · 1 filter

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…

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