Andrew D. Lin

activity

20242026

collaborators

Showing cs.DSShow all

2 papers · 1 filter

cs.DS2026

Strongly Refuting Semirandom Linear Systems in Subexponential Time

Pravesh K. Kothari, Andrew D. Lin, Peter Manohar

In this paper, we consider the problem of refuting $F_{2}$ -linear equations with random right-hand sides. Formally, we give a sub-exponential $2^{O (n / l o g n)}$ -time randomiz…

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…

Strongly Refuting Semirandom Linear Systems in Subexponential Time

Solving Random Planted CSPs below the nk/2 Threshold

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