R. O'Donnell and R. Servedio.

Preliminary version in

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 \emph{Chow Parameters}. Providing an algorithmic version of Chow's theorem --- i.e., efficiently constructing 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~\cite{Elgot:60,Chow:61,Dertouzos:65,Winder:71}, game theory and the design of voting systems~\cite{DubeyShapley:79,Leech:03,TT:06,APL:07}, and learning theory~\cite{BDJ+:98,Goldberg:06b}.

In this paper we effectively solve the problem, giving a randomized PTAS with the following behavior:

**Theorem:** Given the Chow Parameters of a Boolean threshold
function $f$ over $n$ bits and any constant $\eps > 0$, the
algorithm runs in time $O(n^2 \log^2 n)$ and with high probability
outputs a representation of a threshold function $f'$ which is
$\eps$-close to $f$.

Along the way we prove several new results of independent interest about Boolean threshold functions. In addition to various structural results, these include the following new algorithmic results in learning theory (where threshold functions are usually called ``halfspaces''):

As a special case of the latter result we obtain the fastest known algorithm for learning halfspaces to constant accuracy in the uniform distribution PAC learning model. For constant $\eps$ our algorithm runs in time $\tilde{O}(n^2)$, which substantially improves on previous bounds and nearly matches the $\Omega(n^2)$ bits of training data that any successful learning algorithm must use.

Postscript or pdf of journal version