Category:Locally biased function

Definition

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

[math]\dfrac{\#\{y \sim x \mid f(x) = 1\}}{n} = p,[/math]

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

Properties

• There exist locally p-biased functions if and only if [math]p = b/2^k[/math] where [math]b,k[/math] are some integers and [math]2^k[/math] 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