Andrew D. Lin

activity

20242026

collaborators

Showing 2026Show all

3 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.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…