Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs

Pravesh K. Kothari, Peter Manohar

We give improved lower bounds for binary $3$-query locally correctable codes (3-LCCs) $C:\{0,1{\}}^k\to \{0,1{\}}^n$. Specifically, we prove: (1) If $C$ is a linear des…