Anindya De (UC Berkeley)

 

We initiate the study of inverse problems in approximate uniform generation, focusing on uniform generation of satisfying assignments of various types of Boolean functions.  In such an inverse problem, the algorithm is given uniform random satisfying assignments of an unknown function $f$ belonging to a class $C$ of Boolean functions (such as linear threshold functions or polynomial-size DNF formulas), and the goal is to output a probability distribution $D$ which is $\epsilon$-close, in total variation distance, to the uniform distribution over $f^{-1}(1)$.  Problems of this sort comprise a natural type of unsupervised learning problem in which the unknown distribution to be learned is the uniform distribution over satisfying assignments of an unknown function $f \in C.$

 

In this talk, we will consider various possibilities for the class C (like halfspaces, CNFs, DNFs ...) and show both positive and negative results. In particular, we will show that while halfspaces and DNFs are efficiently learnable in this setting, CNFs and higher degree PTFs are hard to learn under plausible cryptographic assumptions. Almost all of the talk will be spent discussing the algorithmic results.

 

Joint work with Ilias Diakonikolas and Rocco Servedio.

 

 

Ilias Diakonikolas (University of Edinburgh)

 

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