The Chow Parameters Problem.
R. O'Donnell and R. Servedio.
SIAM Journal on Computing, 40(1), 2011, pp. 165-199.
Preliminary version in 40th Annual Symposium on Theory of Computing (STOC), 2008, pp. 517--526.

Abstract:

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''):

  • An $\tO(n^2)$-time uniform distribution algorithm for learning halfspaces to constant accuracy in the ``Restricted Focus of Attention'' (RFA) model of Ben-David et al.~\cite{BenDavidDichterman:98}. This answers the main open question of \cite{BDJ+:98}.

  • An $\tO(n^2)$-time agnostic-type learning algorithm for halfspaces under the uniform distribution. This is in contrast with recent results of Guruswami and Raghavendra~\cite{GR:06} who show that the learning problem we solve is NP-hard under general distributions.

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

    pdf of conference version

    Postscript or pdf of journal version

    Back to main papers page