Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
Why Study CS at U of T
Career Options
History of DCS
Giving to DCS
Computer Science at UofT Mississauga
Computer Science at UofT Scarborough
Contact
Employment Opportunities for Faculty/Lecturers
How to Find Us
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate students
Current Graduate students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
Newsletter: @DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> APRIL 30: Theory CS Seminar
About
Undergraduate
Graduate
Research
People
News & Events
APRIL 30: Theory CS Seminar
Event date: Friday, April 30, 2010, at 11:10 AM
Location: Galbraith Bldg, Rm. 244
Speaker: Sergey Yekhanin
Microsoft Research
Title: Matching Vector Codes
Abstract: An (r,delta,epsilon)-locally decodable code encodes a k-bit message to an N-bit codeword, such that for every i in [k], the i-th message bit can be recovered with probability 1-epsilon, by a randomized decoding procedure that reads only r bits, even if the codeword is corrupted in up to delta*N locations.
Recently a new class of locally decodable codes, based on families of vectors with restricted dot products has been discovered. We refer to those codes as Matching Vector (MV) codes. Several families of MV codes have been obtained. While codes in those families were shorter than codes of earlier generations, they suffered from having large values of epsilon. Codes with constant query complexity could only tolerate tiny amounts of error, and no MV codes of super-constant number of queries capable of tolerating a constant fraction of errors were known to exist.
In this paper we develop a new view of matching vector codes and uncover certain similarities between MV codes and classical Reed Muller codes. Our view allows us to obtain a deeper insight into power and limitations of MV codes. Specifically,
1. We show that existing families of MV codes can be enhanced to tolerate a nearly 1/8 fraction of errors, independent of the value of r. Such enhancement comes at a price of a moderate increase in the number of queries;
2. Our construction yields the first families of matching vector codes of super-constant query complexity that can tolerate a constant fraction of errors. Our codes are shorter than Reed Muller LDCs for all values of r < log k / (log log k)^c;
3. We show that any MV code encodes messages of length k to codewords of length at least k*exp(sqrt(log k)). Therefore MV codes do not improve upon Reed Muller locally decodable codes for r > exp(sqrt(log k)).
Joint work with Zeev Dvir and Parikshit Gopalan.