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

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.

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