Ke Yang

In this paper, we study the problem of using statistical

query (SQ) to learn highly correlated boolean functions, namely, a

class of functions where any

pair agree on significantly more than a fraction 1/2 of the inputs.

We give a limit on how well ...
more >>>

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco Servedio

This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e. a function of the form f(x)=sgn(w ⋅ x - θ). We consider halfspaces over the continuous domain R^n (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube {-1,1}^n ... more >>>

Dana Ron, Rocco Servedio

A signed majority function is a linear threshold function $f : \{+1,1\}^n \to \{+1,1\}$ of the form

$f(x)={\rm sign}(\sum_{i=1}^n \sigma_i x_i)$ where each $\sigma_i \in \{+1,-1\}.$ Signed majority functions are a highly symmetrical subclass of the class of all linear threshold functions, which are functions of the form ${\rm ...
more >>>