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