5 papers
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…
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) is an error-correcting code that allows one to recover any bit of the original message with good probability while…
Spectral Refutations of Semirandom -LIN over Larger Fields
Nicholas Kocurek, Peter Manohar
We study the problem of strongly refuting semirandom -LIN instances: systems of -sparse inhomogeneous linear equations over a finite field . For the…
Solving Random Planted CSPs below the Threshold
Arpon Basu, Jun-Ting Hsieh, Andrew D. Lin +1
We present a family of algorithms to solve random planted instances of any -ary Boolean constraint satisfaction problem (CSP). A randomly planted instance of a Boolean CSP is ge…
A Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs
Oliver Janzer, Peter Manohar
A code is a -query locally decodable code (-LDC) if one can recover any chosen bit of the message with good confide…