Andrew D. Lin

activity

20242026

collaborators

Showing cs.CCShow all

2 papers · 1 filter

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