Treffer: The Chow Parameters Problem

In the 2nd Annual FOCS (1961), C. K. Chow proved that every Boolean threshold function is uniquely determined by its degree-0 and degree-1 Fourier coefficients. These numbers became known as the Chow Parameters. Providing an algorithmic version of Chow’s theorem — i.e., efficiently construct-ing a representation of a threshold function given its Chow Parameters — has remained open ever since. This problem has received significant study in the fields of circuit complexity [Elg60, Cho61, Der65, Win71], game theory and the design of voting systems [DS79, Lee03, TT06, APL07], and learning theory [BDJ+98, Gol06]. In this paper we effectively solve the problem, giving a randomized PTAS with the following behav-ior: Theorem: Given the Chow Parameters of a Boolean threshold function f over n bits and any con-stant > 0, the algorithm runs in time O(n2 log2 n) and with high probability outputs a representation of a threshold function f ′ which is -close to f. Along the way we prove several new results of independent interest about Boolean threshold func-tions. In addition to various structural results, these include the following new algorithmic results in