School of Technology and Computer Science Seminars

The Approximate Degree of Surjectivity

by Suhail Sherif (School of Technology and Computer Science, TIFR)

Friday, March 23, 2018 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
The surjectivity function (SURJ) takes as input the truth table of a function f: [n] -> [r] and outputs 1 iff all elements of [r] are mapped to.

In recent months, there has been some activity regarding the degree of a real polynomial pointwise approximating SURJ with error <= 1/3. It was conjectured that with r set to n/2, the degree needed would be Omega(n). Sherstov showed that degree around O(n^.75) would suffice.

He proved this by constructing such a polynomial from scratch. The construction is surprisingly simple and I will be presenting this construction.

This result is from Sherstov's 2018 paper "Algorithmic Polynomials".