Title	High rate locally-correctable and locally-testable codes with sub-polynomial query complexity
Creator	Saraf, Shubhangi
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2016-09-09T08:38
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
Extent	28 minutes
Subject	Mathematics; Computer science; Theoretical computer science
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: Rutgers
Series	BIRS Workshop Lecture Videos (Banff, Alta)
Date Available	2017-03-11
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0343138
URI	http://hdl.handle.net/2429/60862
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Faculty
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos