An Optimal Algorithm for Certifying Monotone Functions

Christian Engels May 03, 2022 [TCS, Boolean Circuit Complexity]

2022-04-04 Gupta, Manoj - An Optimal Algorithm for Certifying Monotone Functions

Query Access to Monotone function of some certifying complexity ($C(f)$)and input $x^*$
Output a $C(f)$ sized subset of $x^* $ certifying the value of $f(x^*)$.
- Makes $O(C(f)\log n)$ queries which matches the information theoretic lower bound.
Extended to real valued function.
Show lower bound of $\Omega(\binom{n}{C(f)})$ queries in the worst case for finding the shortest certificate.

A certificate is the value of bits that "fix" $f(x)$.
Let $x$ (otherwise denoted by $x^* $) be an input $S\subseteq [n]$ is a certificate if for all $y$ such that $x|_S=y|_S$ implies $f(x)=f(y)$.
The certificate size is the $\max_{x\in {0,1}^n} \min_j$ exists a certificate for $f$ of size $j$.
There exists a randomized algorithm that for monotone boolean functions, with at most $O(C(f)^8 \log n)$ queries that outputs at such a certificate for a given input.
$O(C(f)\log n)$ queries are necessary.
For non-monotone functions $\Omega(2^{C(f)} + C(f)\log n)$ queries are necessary.
And $O(2^{C(f)} \cdot C(f)\log n)$ queries are sufficient for a randomized algorithm.
Definition:
- $x_S$ is the indicator vector and $x|_S$ the coordinates.
- $S_x$ is the set coming from the vector $x\in {0,1}$.
- Minimal Certificate:
  - A certificate is minimal if for all $S\setminus a$ is not a certificate for $a\in S$.
  - For monotone this is equivalent to: for all $A\subset S$ $f(x|_A)\neq f(x|_S)$.

Algorith:
- Input: Query Access to $f$, $x$ with $f(x)=1$.
- Set $A=\emptyset$, $S=S_x$, i.e., all indices where $x_i=1$.
- Run until $f(x_A)=1$
  - Set $s\leftarrow \text{search}(f,A,S)$.
  - Add $s$ to $A$.
  - Set $S = S\cap [s-1]$.
- Output $A$.
Search:
- On Input $f,A,S$ output the smallest $s\in S$ such that $f(x_{A\cup ([s]\cap S)})=1$ with binary search.
Proof of Correctness:
- $f(A)=1$ by the loop condition.
- Assume any $A\setminus s$ with $s\in A$.
  - Then $f(A\setminus s)=0$.
  - It must be the case that $f(x_{S\cap [s-1]\cup A})=0$ but $f(x_{S\cap [s]\cup A})=1$. Otherwise $s$ would not have been picked by the binary search algorithm
  - All future elements that are added to the certificate must be in $S\cap [s-1]$ if $A$ is not allready minimal.
  - But $f(x_{S\cap [s-1]\cup A})=0$, a contradiction.
Proof of Runtime:
- $A$ has at most $C(f)$ coordinates.
- Every step we add another element to $A$.
- The binary search uses $\log n$ steps.
- Checking if $f(x_A)=1$ uses one query.
- Hence, $C(f)(\log n +1)$.

Claim 1.1: Any query algorithm that starts with $x$ and goes through hamming neighbours iteratively needs $\Omega(\epsilon n)$ time.
- Notice that the above algorithm is not doing this.
Claim 1.2: Lower bound of $\Omega(k\log n)$ where $k$ is the certificate size for monotone functions.
Claim 8.3: $\Omega(2^k + k\log n)$ for arbitrary functions.

Yao's Lemma:
- Let $R_q$, $D_q$ be the set of all $q$-query randomized and deterministic algorithms respectively.
- Let $I$ be the set of all possible pairs $f:{0,1}^n \rightarrow {0,1}$ and $x$ an instance.
- For any distribution $\mu$ on $I$ $\min_{R\in R_q} \max_{(f,x)\in I} [\text{error}R(f,x)] \geq \min{D\in D_q} E_{f,x\sim \mu}[\text{error}_D(f,x)]$.
Claim 7.6:
- There is some monotone function with $C(f)\leq k$ and input $x$ on which a $q$-query algorithm $A$ successfully returns and a size $l$ certificate for $x$ with probability $2^q \binom{l}{k}/\binom{n}{k} \leq 2^q (ne/n)^k$.

Notice that communication complexity is difficult to apply as our outut is a set of numbers.