All reports by Author Meghal Gupta:

__
TR22-044
| 4th April 2022
__

Meghal Gupta, Naren Manoj#### An Optimal Algorithm for Certifying Monotone Functions

Meghal Gupta, Naren Manoj

Given query access to a monotone function $f\colon\{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)$ subset of $x^{\star}$ certifying the value of $f(x^{\star})$. Our algorithm makes $O(C(f) \cdot \log n)$ queries to $f$, which matches the information-theoretic lower bound for this ... more >>>