Self-Predicting Boolean Functions

Nir Weinberger, Ofer Shayevitz

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…