דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Testing of Polynomials and related questions
event speaker icon
אלעד הרמתי, הרצאה סמינריונית לדוקטורט
event date icon
יום רביעי, 18.6.2014, 14:00
event location icon
טאוב 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.
[בחזרה לאינדקס האירועים]