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

YouTube

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles

Simons Institute via YouTube

Overview

Explore the latest advancements in error-correcting codes through this 43-minute lecture from the Simons Institute. Delve into Omar Alrabiah's research on near-tight bounds for 3-query locally correctable binary linear codes. Learn about the improved dimension bound of O_{delta}(log^2 n * loglog n) for binary linear codes with 3-query local correctability against adversarial errors. Understand how this result compares to previous bounds and its significance in relation to quadratic Reed-Muller codes. Examine the novel approach that directly bounds the covering radius of the dual code, inspired by Iceland and Samorodnitsky's work. Discover how the proof utilizes recent breakthroughs in rainbow cycles in properly edge-colored graphs to iteratively reduce linear combinations. Gain insights into the implications of this research for the theory of error-correcting codes and its potential applications in computer science and information theory.

Syllabus

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles

Taught by

Simons Institute

Reviews

Start your review of Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles

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.