Category:Locally biased function

From Boolean Zoo
Jump to: navigation, search


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


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


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


  1. Renan Gross and Uri Grupel, Indistinguishable Sceneries on the Boolean Hypercube, CPC 2018

This category currently contains no pages or media.