Title	Locally testable and locally correctable codes approaching the Gilbert-Varshamov bound
Creator	Kopparty, Swastik
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2016-09-09T09:07
Description	We show that there exist binary locally testable codes (for all rates) and locally correctable codes (for low rates) with rate and distance approaching the Gilbert-Varshamov bound (which is the best rate-distance tradeoff known for general binary error-correcting codes). Our constructions use a number of ingredients: Thommesen's random concatenation technique, the Guruswami-Sudan-Indyk strategy for list-decoding concatenated codes, the Alon-Edmonds-Luby distance amplification method, and the local list-decodability and local testability of Reed-Muller codes. Interestingly, this seems to be the first time that local testability is used in the construction of locally correctable codes. Joint work with Sivakanth Gopi, Rafael Oliveira, Noga Ron-Zewi and Shubhangi Saraf
Extent	27 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.0343139
URI	http://hdl.handle.net/2429/60863
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

Locally testable and locally correctable codes approaching the Gilbert-Varshamov bound Kopparty, Swastik

Description

Item Metadata

Item Media

Item Citations and Data

Rights