# Category:Locally stable function

## Definition

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

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

## Properties

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

## References

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

This category currently contains no pages or media.