Testing of Polynomials and related questions

Elad Haramaty, Ph.D. Thesis Seminar
Wednesday, 18.6.2014, 14:00
Taub 601
Prof. A. Shpilka

Degree d Testing is a probabilistic algorithm that given a function f answer whether f is a degree d polynomial or far from such polynomial using "few" queries to f. One natural such tester is the low dimensional tester. This test checks if the degree of f is d on a low dimensional subspace. Another test is the Gowers norm test. This test checks that the a random d+1 derivative is zero. In this talk, we will study the structure of functions that pass those tests with non-negligible probability, generalize those results to Lifted Codes and present an application for those types of results.

Back to the index of events