On the Approximate Non-Deterministic Degree of Total Boolean Functions

Samruddhi Pednekar, Supartha Podder

The approximate non-deterministic degree of a Boolean function $f$, denoted ${\mathsf{ndeg}}_{\hat{I}}\mu (f)$ (written ${\mathsf{N}}_{\hat{I}}\mu (f)$ for brevity), is the minimum degree of a real polynomi…