Category:Locally stable function

Definition

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

[math]\dfrac{\#\{y \sim x \mid f(x) = f(y)\}}{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] keeps the value [math]f(x)[/math] on exactly a p-fraction of the neighbors of [math]x[/math].

Properties

• If [math]p = 1/n[/math] or [math]p = (n-1)/n[/math], then the parity function is the only locally p-stable function up to isomorphism. There is a superpolynomial number of locally [math](n/2)/(n+1)[/math]-stable functions on [math]\{-1,1\}^{n+1}[/math]. ^[1]

References