[Colloquium] [Staff] Theory Seminars at Computer Science

[Donna Brooms]

Date:         Wednesday,May 16,  2012
Time:        11:30 a.m..
Place:        Ryerson 277, 1100 E. 58th Street
_________________________ 

Speaker:    Ilias Diakonikolas
From:        UC Berkeley
Title:       Reconstructing Boolean Threshold Functions from their Average Satisfying Assignment.
Abstract:  In the 2nd FOCS conference (1961) C.-K. Chow gave a surprising characterization of Boolean threshold functions (halfspaces). Among all Boolean functions, each threshold function f is uniquely determined by the "center of mass'' of its positive inputs, and the number of positive inputs. These n+1 parameters of f (known since as "Chow parameters'') are equivalent to its degree-0 and degree-1 Fourier coefficients.
The proof of Chow's theorem is highly non-constructive. In this work, we address the algorithmic problem of efficiently reconstructing a threshold function from its Chow parameters. This problem arises in various contexts and has been considered by researchers in electrical engineering, game theory, social choice and learning.
I will describe a nearly-optimal algorithm to approximately reconstruct a threshold function from its Chow parameters. The algorithm and its analysis use tools from Fourier analysis, linear algebra, probability and learning.
(Based on joint work with Anindya De, Vitaly Feldman and Rocco Servedio.)
 Host: Anastasios Sidiropoulos
 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20120515/1a0ac2ec/attachment.htm