"The Degree-d Chow Parameters Problem"
Ilias Diakonikolas (USC)
Monday, February 4, 2019, 2:00 pm
EBU3B, Room 4258
Abstract: The Degree-d Chow Parameters of a Boolean function are its degree at most d Fourier coefficients. A degree-d Polynomial Threshold Function (PTF) is a Boolean function of the form f(x) = sgn(p(x)), where p is a degree at most d real polynomial. A classical result, dating back to the 1960s, shows that degree-d PTFs are uniquely specified by their degree-d Chow parameters. The algorithmic problem of reconstructing degree-d PTFs from their degree-d Chow parameters is of fundamental interest in several scientific disciplines, including learning theory, computational complexity, and game theory. In this talk, we will provide an overview of the recent progress on this problem.
Based on joint works with Daniel Kane (UCSD) and Chrystalla Pavlou (Edinburgh).