Open Collections will undergo maintenance on Thursday, July 24th, 2025. The site will not be available from 8:00 AM - 9:00 AM PST and performance may be impacted from 9:00 AM - 12:00 PM PST.

BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

High rate locally-correctable and locally-testable codes with sub-polynomial query complexity Saraf, Shubhangi

Description

We study locally correctable and locally testable codes in the high rate regime. The tradeoff between the rate of a code and the locality/efficiency of its decoding and testing algorithms has been studied extensively in the past decade, with numerous applications to complexity theory and pseudorandomness. In this talk I will discuss some recent results giving efficient sub-polynomial query decoding and testing algorithms for high rate error correcting codes. I will also highlight some of the most interesting challenges that remain. Based on joint work with Swastik Kopparty, Or Meir and Noga Ron-Zewi

Item Media

Item Citations and Data

Rights

Attribution-NonCommercial-NoDerivatives 4.0 International