Andrew D. Lin

activity

20242026

collaborators

5 papers

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

Lower Bounds for all List-Decodable Deletion Codes

Andrew D. Lin

A length- $n$ binary $k$ -deletion code is a set of binary strings such that if we delete any $k$ bits of a string, leaving a length- $(n - k)$ binary string, we can uniquely recover th…

cs.CC2026

An Approximate Cauchy-Schwarz Inequality and Improved Bounds for Sherali-Adams Refutation of Semirandom CSPs

Pravesh K. Kothari, Andrew D. Lin

We formulate an approximate Cauchy-Schwarz inequality and show that it is satisfied by solutions to the Sherali-Adams linear programming hierarchy (interpreted as ``pseudo-distribu…

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…

cs.CC2024

Improved Lower Bounds for all Odd-Query Locally Decodable Codes

Arpon Basu, Jun-Ting Hsieh, Pravesh K. Kothari +1

We prove that for every odd $q \geq 3$ , any $q$ -query binary, possibly non-linear locally decodable code ( $q$ -LDC) $E : {\pm 1}^{k} \to {\pm 1}^{n}$ must satisfy $k \leq \tilde{…