Category:Locally biased function

Definition

A Boolean function $f:\{-1,1\}^n \to \{-1,1\}$ is called locally p-biased if for every input $x$, we have that

$\dfrac{\#\{y \sim x \mid f(x) = 1\}}{n} = p,$

where $y\sim x$ denotes vertices $y$ of the cube which differ from $x$ in just a single coordinate. In other words, for every input $x$, the function $f$ attains the value 1 on exactly a p-fraction of the neighbors of $x$.

Properties

• There exist locally p-biased functions if and only if $p = b/2^k$ where $b,k$ are some integers and $2^k$ divides n. The number of nonisomorphic 1/n-biased functions and the number of nonisomorphic 1/2-biased functions is superpolynomial. ^[1]

Examples

• The function which calculates the parity on only half its bits is locally 1/2-biased.

References