Preprint
Sep 2026
Certification complexity of Boolean functions
Certificate complexity $(C(f ))$ is a fundamental measure of complexity of Boolean functions f which counts the number of bits of an input that need to be known in order for the value of the function to be determined. A certificate can be viewed as a partial assignment, or a boolean subcube where the function is consta...
Chandrima Kayal, Sophie Laplante, É. Larroque et al.
· 0 citations