Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SIGNED MAJORITY FUNCTIONS:
Reports tagged with Signed Majority Functions:
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 >>>

ISSN 1433-8092 | Imprint