Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Testing of Polynomials and related questions
event speaker icon
Elad Haramaty (Ph.D. Thesis Seminar)
event date icon
Wednesday, 18.06.2014, 14:00
event location icon
Taub 601
event speaker icon
Advisor: 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.