An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes

Explore an in-depth lecture on the exponential lower bound for linear 3-query locally correctable codes. Delve into the proof that the blocklength n of a linear 3-query LCC C: {0,1}^k -＞ {0,1}^n must be at least exp(k^{1/8}), demonstrating exponential growth with k. Examine how this improves upon previous lower bounds and approaches the best-known construction based on Reed-Muller codes. Discover the first separation between q-query LCCs and LDCs for constant q. Investigate "design 3-LCCs" and their blocklength requirements, connecting to the Hamada conjecture for 4-designs. Learn about the extension to nonlinear LCCs, proving a superpolynomial lower bound of k^{log k}. Gain insights into advanced error-correcting code theory and its implications for computer science and information theory.

An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes