Preliminaries {#sec:preliminaries}
=============

We use bold font letters such as $\bT$ and $\bx$ for random variables.  Given $n\ge 1$, we write $[n]$ to denote $\{1, \dots, n\}$. Given a point $x$ in the Boolean hypercube $\{0, 1\}^n$ and $S \subset [n]$, we use $x^{(S)}$ to denote the string obtained from $x$ by flipping each entry $x_i$ with $i \in S$. When $S = \{i \}$ is a singleton, we write $x^{(i)}$ instead of $x^{(\{i\})}$ for convenience.  Given $x, y \in \{0, 1\}^n$, $x \oplus y \in \{0, 1\}^n$ is their bit-wise XOR. 

We define the *distance* between two Boolean functions $f,g\colon\{0,1\}^n\rightarrow\{0,1\}$ using the uniform distribution: $\dist(f,g):=\Pr_{\bx \sim\{0,1\}^n} [f(\bx)\ne g(\bx)]$. The distance of $f$ to unateness is defined as the minimum value of $\dist(f,g)$ over all unate functions $g$; we say $f$ is *$\eps$-far from unate* if its distance to unateness is at least $\eps$, or equivalently, $\dist(f,g)\ge \eps$ for all unate functions $g$.

We say an algorithm tests the unateness of Boolean functions if, given $\eps$ and query access to a Boolean function $f$, (1) it ouputs “unate” with probability at least $2/3$ when $f$ is unate; and (2) it outputs “non-unate” with probability at least $2/3$ when $f$ is $\eps$-far from unate.  We say the algorithm is one-sided if it always outputs “unate” when $f$ is unate. 

Recall that an *edge violation* of unateness for $f$ consists of a pair of bi-chromatic edges along the same direction, one being monotone and one being anti-monotone.  We remark that all algorithms discussed in this paper output “non-unate” only when an edge violation is found among the queries they made.  We commonly refer to edge violations simply as violations. 

The *total influence* $I_f$ of a Boolean function $f\colon\{0,1\}^n\rightarrow \{0,1\}$ is the number of bi-chromatic edges of $f$ divided by $2^n$. We combine a lemma from [@KMS15] and a unateness testing algorithm of [@BCPRS17] to find an edge violation in a function of *high* total influence using $\widetilde{O}(\sqrt{n})$ queries only.[^1] The proof can be found in Appendix \[sec:high-inf\]. 

\[hehelem\] There is an $\widetilde{O}(\sqrt{n})$-query, non-adaptive algorithm that, given any $f \colon \{0, 1\}^n \to \{0, 1\}$ with $I_f > 6\sqrt{n}$, finds an edge violation of $f$ to unateness with probability at least $2/3$.

Given Lemma \[hehelem\], it suffices for us to give an $\widetilde{O}(n^{3/4}/\eps^2)$-query algorithm that can find an edge violation of any function that is $\eps$-far from unate and satisfies $I_f\le 6\sqrt{n}$.

Adaptive edge search {#sec:aes}
====================

In this section, we introduce a new subroutine called *adaptive edge search* ($\ESearch$) which will be heavily used in our main algorithm for testing unateness.  We present the subroutine in Figure \[fig:edge-search\].  It has query access to a Boolean function $f\colon \{0, 1\}^n \to \{0, 1\}$ and takes two inputs: $x \in \{0, 1\}^n$ is a point in the hypercube and $S \subseteq [n]$ is a nonempty set of even size.  The goal of $\ESearch(x,S)$ is to find an index $i \in S$ such that $(x, x^{(i)})$ is a bi-chromatic edge in $f$. It returns an index $i\in S$ if it finds one (note that $\ESearch$ always checks and makes sure that $(x,x^{(i)})$ is bi-chromatic before it outputs $i$), or returns “fail” if it fails to find one (which does not necessarily mean that none of the edges $(x,x^{(i)})$, $i\in S$, are bi-chromatic).  While a naive search would consider each $i \in S$ and query each $f(x^{(i)})$, as well as $f(x)$, incurring a cost of $|S|+1$ queries that can be expensive when $S$ is large, $\ESearch(x,S)$ only uses $L+2=O(\log n)$ queries, where we set the parameter $L=\lceil 4\log n\rceil$ in Figure \[fig:edge-search\]. 

We will analyze the performance of $\ESearch$ in Section \[sec:main2\], where we show that, informally, under the assumption that $f$ is far from unate, $\ESearch$ succeeds in finding a bi-chromatic edge $(x,x^{(i)})$ for some $i\in S$ for “many” input pairs $(x,S)$ with high probability.  For now, we just record the following simple observation that follows from the description of $\ESearch$ in Figure \[fig:edge-search\]. 

Subroutine $(x, S)$

[**Input:**]{} Query access to $f \colon \{0, 1\}^n \to \{0, 1\}$, $x \in \{0, 1\}^n$, a nonempty set $S \subseteq [n]$ of even size. 

[**Output:**]{} Either an index $i \in S$ with $f(x^{(i)}) \neq f(x)$, or “fail.” 

1.   -.02in Query $f(x)$ and set $b\leftarrow f(x)$.

2.   -0.02in If $|S| = 2$, pick one coordinate $\bi \in S$ uniformly at random.  Query $f(x^{(\bi)})$ and\
    return $\bi$ if $f(x^{(\bi)}) \neq b$; otherwise return “fail.” 

3.   -0.02in Sample $L=\lceil 4\log n\rceil$ subsets $\bT_1, \dots, \bT_L \subset S$ of size ${|S|}/{2}$ uniformly at random.\
    Query $f(x^{(\bT_\ell)})$ and set the output to be $\bb_\ell$ for each $\ell\in [L]$. Let $\bC \subset S$ where $$\bC = \bigcap_{\ell \in [L] \colon\hspace{-0.02cm}\bb_\ell \neq b} \bT_\ell\ \ \ \ \ \ \text{($\bC=\emptyset$ by default if $\bb_\ell=b$ for all $\ell$)}.  \vspace{-0.06cm}$$

4.   -0.06in If $\bC = \{ \bi \}$ for some $\bi$, query $f(x^{(\bi)})$ and return $\bi$ if $f(x^{(\bi)}) \neq b$; otherwise return “fail.” 

-0.14in

$\ESearch(x,S)$ makes $O(\log n)$ queries and returns either an index $i$ or “fail.”  Whenever it returns an index $i$, we have $i\in S$ and $(x,x^{(i)})$ is a bi-chromatic edge in $f$.

Scores {#sec:scores}
======

In this section, we use the $\ESearch$ subroutine to introduce the notion of *scores* for monotone and anti-monotone edges.  We start with some notation. 

We consider some fixed function $f \colon \{0, 1\}^n \to \{0, 1\}$. For each $i \in [n]$, we let $E_i^+$ denote the set of monotone edges in direction $i$ and $E_i^-$ denote the set of anti-monotone edges in direction $i$. Let $$\Lambda = \left\lfloor \log_{2} \left(\frac{\sqrt{n}}{\log n} \right) \right\rfloor=\Theta(\log n)$$ be a parameter which will be used in the rest of the paper.  Given $i\in [n]$ and $j\in [ \Lambda]$, we let $$\calP_{i, j} = \left\{ S \subset [n] \setminus \{i\} : |S| = 2^{j} - 1 \right\}.$$ We need the following definitions:

\[def:goodpairs\] Let $(x,x^{(i)})$ be a monotone edge in $E_i^+$ for some $i\in [n]$ and let $S$ be a set in $\calP_{i,j}$ for some $j\in [\Lambda]$. We say $(x,S)$ is a *good pair for* $E_i^+$ if $\ESearch(x,S\cup \{i\})$ returns $i$ with probability at least $1/2$ (i.e., running the adaptive edge search subroutine over $x$ and $S\cup \{i\}$ would help us discover the monotone edge $(x,x^{(i)})$ in $E_i^+$ with probability at least $1/2$). 

By definition, $(x,S)$ can be a good pair for $E_i^+$ only if $(x,x^{(i)})$ is a monotone edge.  Additionally, if $(x, x^{(i)})$ is a monotone edge, then $(x, S)$ is always a good pair for all $S\in \calP_{i,1}$. This simply follows from the fact that, as $|S\cup\{i\}|=2$, $\ESearch(x,S\cup\{i\})$ will pick $i$ with probability $ {1}/{2}$ on line 2 and find the monotone edge $(x, x^{(i)})$. Next we use good pairs to define *strong* points. 

A point $x \in \{0, 1\}^n$ with $(x,x^{(i)})\in E_i^+$ is said to be $j$-*strong* *(*or a $j$-*strong point)* for $E_i^+$, for some $j\in [\Lambda]$, if $(x,S)$ is a good pair for $E_i^+$ for at least $3/4$ of $S\in \calP_{i,j}$.

Consider an $x \in \{0, 1\}^n$ that is a $j$-strong for $E_i^+$. Then, if we sample an $\bS$ from $\calP_{i,j}$ uniformly and run $\ESearch (x,\bS\cup \{i\})$, we will discover $(x,x^{(i)})\in E_i^+$ with probability $(3/4)\cdot (1/2)=3/8$. Note that if $(x, x^{(i)})$ is a monotone edge, then $x$ is always $1$-strong.  We also extend both definitions of *good pairs* and $j$-*strong* points to $\smash{E_i^-}$, so we may consider a good pair $(x, S)$ for $\smash{E_i^-}$, as well as, a point $x\in \{0,1\}^n$ which is $j$-strong for $\smash{E_i^-}$, when $(x,x^{(i)})\in E_i^-$ is an anti-monotone edge. 

For each $i\in [n]$ and $j\in [\Lambda]$, let $\score_{i,j}^+$ be the fraction of points that are $j$-strong for $E_i^+$: $$\score_{i,j}^+=\frac{ \text{the number of $j$-strong points for $E_i^+$}}{2^n}\in [0,1].$$ Intuitively, when $\smash{\score_{i,j}^+}$ is high, it becomes easy to discover a monotone edge in direction $i$ using $\ESearch$ with $2^j$-sized sets (as $|S\cup \{i\}|=2^j$ in Definition \[def:goodpairs\]) without using too many queries.  This intuition will be made formal in the analysis of our main algorithm later in Section \[sec:main2\]. 

Finally we define $\score_i^+$ for each $i\in [n]$ as (recall that $2^j\le \sqrt{n}/\log n$ by the choice of $\Lambda$) $$\label{eheh}
\score_i^+=\max_{j\in [\Lambda]} \left\{\score_{i,j}^+\cdot  \frac{2^j}{\sqrt{n}}\right\}\in [0,1].$$ Note that $\smash{\score_{i,j}^+}$’s are adjusted in (\[eheh\]) with weights $2^j/\sqrt{n}$ before taking the maximum.  Roughly speaking, this is done here to reflect the fact that with the same $\smash{\score_{i,j}^+}$, the larger $j$ is, the easier it becomes to discover an edge in $E_i^+$ using sets of size $2^j$ in $\ESearch$. Consider some point $x \in \{0, 1\}^n$ which is $j$-strong for $E_i^+$. Then as noted above, if the algorithm samples a set $\bS \sim \calP_{i, j}$ uniformly at random and runs $\ESearch(x, \bS \cup \{i \})$, the algorithm will observe $(x, x^{(i)})$ with probability $\frac{3}{8}$; however, the algorithm does not know $\calP_{i,j}$ or $i$. From the algorithm’s perspective, there is a point $x \in \{0, 1\}^n$ with some bi-chromatic edge $(x, x^{(i)})$. The algorithm runs $\ESearch(x, \bS')$ for some set $\bS'$, and must hope that the set $\bS'$ of size $2^j$ contains $i$ and $\bS' \setminus \{ i \} \in \calP_{i,j}$ is a good pair.  As $j$ increases, it becomes easier for $\bS'$ to include $i$. (Again this will be made more formal in Section \[sec:main2\]).  We also extend $\smash{\score_{i,j}^+}$, $\smash{\score_i^+}$ to $\smash{\score_{i,j}^-}$, $\smash{\score_i^-}$ for $E_i^-$.

Plan for the proof of Theorem \[thm:main\]
------------------------------------------

The plan is the following.  Let $f\colon\{0,1\}^n\rightarrow \{0,1\}$ be a function that is $\eps$-far from unate.  Our goal is to give an $\widetilde{O}(n^{3/4}/\eps^2)$-query algorithm which finds an edge violation of $f$ with probability at least $2/3$. By Lemma \[hehelem\], we may assume without loss of generality that $f$ also satisfies $I_f \leq 6 \sqrt{n}$. We rely on the following technical lemma for the scores of $f$ but delay its proof to Section \[sec:main2\]. 

\[main2\] If $f\colon\{0,1\}^n\rightarrow \{0,1\}$ is $\eps$-far from unate and satisfies $I_f \leq 6\sqrt{n}$, then we have $$\label{maineq}
\sum_{i=1}^n \min\Big\{ \score_i^+,\score_i^-\Big\} \geq \Omega\left(\dfrac{\eps^2}{\log^8 n}\right).$$

We present our main $\widetilde{O}(n^{3/4}/\eps^2)$-query (adaptive) algorithm in the next section and show that, given any function $f$ that satisfies (\[maineq\]), it finds an edge violation of $f$ with probability at least $2/3$.

[^1]: Here we do not need to assume that $f$ is far from unate.  Actually Lemma \[blabla1\] implies that any $f$ with $I_f\ge 6\sqrt{n}$ cannot be unate, and the algorithm stated in Lemma \[hehelem\] finds an edge violation with high probability.