Ph.D Student | Kaplan Yohay |
---|---|

Subject | Multi-Variate Abstractions of Algebraic Geometry Codes, with Applications |

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.