|Ph.D Student||Kaplan Yohay|
|Subject||Multi-Variate Abstractions of Algebraic Geometry Codes,|
|Department||Department of Computer Science||Supervisor||Professor Eliyahu Ben Sasson|
|Full Thesis text|
Polynomials over finite fields, and specifically the error correcting codes they induce,
have been used extensively in all areas of theoretical computer science. These consist
of the evaluation of univariate or multivariate (known as Reed-Solomon(RS) or Reed-
Muller(RM) codes, respectively) polynomials on the points of some finite field. One of the limits of using such codes has been that the size of the field limits the degree of
polynomials that we can use, and therefore the rate of the codes we achieve.
A well-known generalization of RS can be found in Algebraic Geometry(AG) codes.
In these, we evaluate a well-chosen space of functions on a well-chosen set of points to get behavior that is strikingly similar to RS codes, both in parameters achieved and in the various algebraic properties polynomials have, but without the field size limiting the code size, though with an added cost in the complexity of description and operations.
This has allowed for advances in many areas of theory (ǫ-biased sets, list decoding,
secret sharing etc.).
In this work we show how Algebraic Geometric codes can generalize RM codes by
showing multi-variate versions of them. These include:
1. We construct locally correctable codes of previously unknown parameters by
considering the ”Degree lifting” of AG codes. This is a generalization of total
degree RM (where only the total degree of a monomial is relevant). We define
and prove the needed Schwartz-Zippel type lemma to make these codes useful and
show how to generalize the standard RM correction methods.
2. We construct probabilistically checkable proofs(PCPs) of linear lengths and polynomial query length for circuit-SAT using tensored AG codes, which are a generalization of individual degree RM (where only the degree of each variable matters). No non-trivial linear PCPs were previously known. As a part of this construction, an appropriate generalization of Alon’s combinatorial nullstellensatz is given.