Ph.D Thesis | |

Ph.D Student | Haramaty Elad |
---|---|

Subject | Polynomial Testing and Related Questions |

Department | Department of Computer Science |

Supervisor | ASSOCIATE PROF. Amir Shpilka |

Full Thesis text |

We consider the problem of testing if
a given an *n* variate function *f* over the finite field *F _{q}*
of

Previous works showed that this
natural test rejected functions that were constant far from degree *d* polynomials
with probability at least order of *q ^{-t}*. Thus to get a
constant probability of detecting functions that are at constant distance from
the space of degree

In this work we show that the natural
test, in fact, rejects functions that are constant far from degree *d*
polynomials with constant probability, where the constants depend only on *q*
the field size. Thus our analysis thus shows that this test is optimal when *q*
is prime.

Moreover, we extend this result to a
more general notion called lifted codes. Given a base code over a *t*-dimensional
space, its *n*-dimensional lift consists of all words whose restriction to
every *t*-dimensional affine subspace is a codeword of the base code.
Lifting not only captures the most familiar codes, which can be expressed as
lifts of low-degree polynomials, it also yields new codes when lifting
“medium-degree” polynomials whose rate is better than that of corresponding
polynomial codes, and all other combinatorial qualities are no worse. We shows
that the natural test for those codes also has constant rejection probability
for functions that are constant far from the code.

We also study functions that pass a similar test, called Gowers Norm, with non-negligible probability. We present structural results for such polynomials with noticeable Gower norm, showing that they can be represented as "nice" function of lower degree polynomials.

We conclude this thesis with an application, showing that by using our low degree tester one can detect efficiently simple paths in graphs.