Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LINEAR THRESHOLD FUNCTIONS:
Reports tagged with Linear Threshold Functions:
TR01-098 | 19th November 2001
Ke Yang

#### On Learning Correlated Boolean Functions Using Statistical Query

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

TR07-128 | 10th November 2007
Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco Servedio

#### Testing Halfspaces

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 &#8901; x - &#952;). 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 >>>

TR13-096 | 25th June 2013
Dana Ron, Rocco Servedio

#### Exponentially improved algorithms and lower bounds for testing signed majorities

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

TR22-068 | 5th May 2022