Self-Predicting Boolean Functions

Abstract

A Boolean function $g$ is said to be an optimal predictor for another Boolean function $f$, if it minimizes the probability that $f(X^n)\ne g(Y^n)$ among all functions, where $X^n$ is uniform over the Hamming cube and $Y^n$ is obtained from $X^n$ by independently flipping each coordinate with probability $\delta$. This paper is about self-predicting functions, which are those that coincide with their optimal predictor.