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

We give improved lower bounds for binary 3-query locally correctable codes (3-LCCs)<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$C: \{\ 0,1 \}^k \rightarrow \{\ 0,1 \}^n$</tex>. Specifically, we prove: 1) If C is a linear design 3-LCC, then <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n \geq 2^{(1 - o(1))\sqrt{k} }$</tex>. A design 3-LCC has the additional property that the correcting sets for every codeword bit form a perfect matching, and every pair of codeword bits is queried an equal number of times across all matchings. Our bound is tight up to a factor <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\sqrt{8}$</tex> in the exponent of 2, as the best construction of binary 3-LCCs (obtained by taking Reed--Muller codes on F_4 and applying a natural projection map) is a design 3-LCC with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n \leq 2^{\sqrt{8 k}}$</tex>. Up to a factor of 8, this resolves the Hamada conjecture on the maximum F_2-codimension of a 4-design. 2) If C is a smooth, non-linear, adaptive 3-LCC with perfect completeness, then, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n \geq 2^{\Omega(k^{1/5})}$</tex>. 3) If C is a smooth, non-linear, adaptive 3-LCC with completeness 1 - \eps, then n \geq \Omega(k^{\frac<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">${1}{2\eps}})</tex>. In particular, when <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\eps$</tex> is a small constant, this implies a lower bound for general non-linear LCCs that beats the prior best <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n \geq \Omega(k^3)$</tex> lower bound of Alrabiah-Guruswami-Kothari-Manohar by a polynomial factor. Our design LCC lower bound is obtained via a fine-grained analysis of the Kikuchi matrix method applied to a variant of the matrix used in the work of Kothari and Manohar (2023). Our lower bounds for non-linear codes are obtained by designing a from-scratch reduction from nonlinear 3-LCCs to a system of “chain XOR equations” — polynomial equations with a similar structure to the long chain derivations that arise in the lower bounds for linear 3-LCCs of Kothari and Manohar.