Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

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

Simons Institute via YouTube

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
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.

Syllabus

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

Taught by

Simons Institute

Reviews

Start your review of An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.