An Optimal Algorithm for Certifying Monotone Functions

Meghal Gupta, Naren Sarayu Manoj

Given query access to a monotone function $f:\{0,1{\}}^n\to \{0,1\}$ with certificate complexity $C(f)$ and an input $x^{\star }$, we design an algorithm that outputs a size-$C(f)…