דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: Combinatorial Construction of Locally Testable Codes
event speaker icon
אור מאיר (מכון ויצמן למדע)
event date icon
יום ראשון, 6.7.2008, 11:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
An error correcting code is said to be locally testable if there is a test that can check whether a given string is a codeword of the code, or rather far from the code, by reading only a constant number of symbols of the string. Locally Testable Codes (LTCs) were first explicitly studied by Goldreich and Sudan (J. ACM 53(4)) and since then several constructions of LTCs were suggested.

While the best known construction of LTCs achieves very efficient parameters, it relies heavily on algebraic tools and on PCP machinery. We present a new and arguably simpler construction of LTCs that is purely combinatorial and does not rely on PCP machinery. Finally, our construction matches the parameters of the best known construction.
[בחזרה לאינדקס האירועים]