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

Events

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