אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

Locally decodable codes are codes that allow decoding of single message bits by reading a sublinear amount of the codeword. These codes have been the object of intense study, of particular interest is the trade-off between the rate of these codes and the query complexity of their local decoding algorithms. When limiting our attention to codes of constant rate, we know of only two such families of codes: Reed-Muller codes and multiplicity codes. While multiplicity codes achieve a higher rate (RM codes have rate at most 1/2), RM codes achieve better rates when we consider long codes (codes that have a block length greater then the field size).

In this work we introduce a new family of codes, tensored AG codes, and prove a Schwartz-Zippel type lemma to establish their parameters. In addition, we prove that tensored hermitian codes, a particular type of tensored AG codes, are locally correctable (and thus, decodable) with parameters comparable to RM codes, but over smaller fields. Our decoding algorithm introduces a novel way to use the automorphisms of the hermitian function field.