Peter Manohar

activity

20242026

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2026

Certifiable Near-Optimality: A Simple Framework for Unifying Search and Refutation for (Semi)random CSPs

Prashanti Anderson, Peter Manohar, Jeff Xu

A classical problem in average-case complexity is the study of random constraint satisfaction problems (CSPs). Random CSPs are traditionally studied in two different settings: refu…

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…

Certifiable Near-Optimality: A Simple Framework for Unifying Search and Refutation for (Semi)random CSPs

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