CSAIL Event Calendar: Previous Series

A nearly optimal solution for the Chow Parameters Problem and applications

Speaker: Ilias Diakonikolas , UC Berkeley
Date: February 28 2012
Time: 5:15PM to 6:15PM
Location: 32-155
Host: Costis Daskalakis, CSAIL, MIT

The Chow parameters of an n-variable Boolean function are its (n + 1) degree-0 and degree-1 Fourier coefficients. It has been known since 1961 that the (exact values of the) Chow parameters of any Linear Threshold Function (LTF) f uniquely specify f within the space of all Boolean functions, but until recently nothing was known about efficient algorithms for reconstructing f (exactly or approximately) from exact or approximate values of its Chow parameters. We refer to this reconstruction problem as the Chow Parameters Problem.

In this talk I will describe a new algorithm for the Chow Parameters Problem which, given the Chow parameters of any LTF f, runs in time O(n^2)* (1/eps)^O(log^2 (1/eps)) and outputs a representation of an LTF g that is eps-close to f . The best previous algorithm [O'Donnell - Servedio, STOC'08/SICOMP'11] has running time poly(n)*2^{2^{Omega(1/eps^2)}}.

As a byproduct of our approach, we obtain nearly optimal low-weight approximations for LTFs and improved algorithms for related problems in learning theory.

The two main ingredients underlying our results are:

(1) a new structural result showing that for f any LTF and g any bounded function, if the Chow parameters of f are close to the Chow parameters of g, then f is close to g (in L_1 distance);

(2) a new boosting-like algorithm that given approximations to the Chow parameters of an LTF outputs a bounded function whose Chow parameters are close to those of f.

Based on joint work with Anindya De (Berkeley), Vitaly Feldman (IBM Almaden), and Rocco Servedio (Columbia).

See other events that are part of Theory Colloquium 2011/2012

See other events happening in February 2012