# Category:Locally biased function

## Contents

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

- ↑ Renan Gross and Uri Grupel, Indistinguishable Sceneries on the Boolean Hypercube, CPC 2018

*This category currently contains no pages or media.*