The Taub Faculty of Computer Science Events and Talks

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 complexity of description and operations. This has allowed for advances in many areas of theory (epsilon-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. This 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.