The Taub Faculty of Computer Science Events and Talks

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.