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".
|