# A tight bound for the clique query problem in two rounds

Uriel Feige Weizmann Institute<EMAIL_ADDRESS>Tom Ferster This
work was done while the author was a student at the Weizmann Institute,
<EMAIL_ADDRESS>
###### Abstract

We consider a problem introduced by Feige, Gamarnik, Neeman, Rácz and Tetali
[2020], that of finding a large clique in a random graph $G\sim
G(n,\frac{1}{2})$, where the graph $G$ is accessible by queries to entries of
its adjacency matrix. The query model allows some limited adaptivity, with a
constant number of rounds of queries, and $n^{\delta}$ queries in each round.
With high probability, the maximum clique in $G$ is of size roughly $2\log n$,
and the goal is to find cliques of size $\alpha\log n$, for $\alpha$ as large
as possible. We prove that no two-rounds algorithm is likely to find a clique
larger than $\frac{4}{3}\delta\log n$, which is a tight upper bound when
$1\leq\delta\leq\frac{6}{5}$. For other ranges of parameters, namely, two-
rounds with $\frac{6}{5}<\delta<2$, and three-rounds with $1\leq\delta<2$, we
improve over the previously known upper bounds on $\alpha$, but our upper
bounds are not tight. If early rounds are restricted to have fewer queries
than the last round, then for some such restrictions we do prove tight upper
bounds.

##  1 Introduction

We consider a problem introduced by Feige, Gamarnik, Neeman, Rácz and Tetali
[5], that of finding a large clique in a random graph $G\sim
G(n,\frac{1}{2})$, where the graph $G$ is accessible by queries to entries of
its adjacency matrix. The input to the problem is a random graph $G(V,E)$ on
$n$ vertices, where for every pair $\\{u,v\\}$ of distinct vertices, $(u,v)\in
E$ independently with probability $\frac{1}{2}$. To simplify some of the
terminology, we sometimes refer to a pair $\\{u,v\\}$ of distinct vertices as
an edge, regardless of whether $(u,v)\in E$, but if $(u,v)\in E$ we refer to
it as a positive edge, and if $(u,v)\not\in E$ we refer to it as a negative
edge. The goal of the algorithm is to find in $G$ a clique (a complete
subgraph) that is as large as possible. The algorithm can access $G$ via
queries to the adjacency matrix of $G$, querying an edge $\\{u,v\\}$ and
getting in reply its status, whether it is positive or negative. We may think
of these queries as queries to a random oracle, where for each new query (not
previously asked), the oracle answers positively with probability
$\frac{1}{2}$ and negatively with probability $\frac{1}{2}$, independently of
all previous answers. The limiting resource for the algorithm is the total
number of queries $q$, whereas the running time of the algorithm may be
unbounded (e.g., exponential in $n$). The sequence of queries asked by the
algorithm may be adapative, in the sense that the choice of the next query
depends on answers to previous queries.

The results of the $q$ queries induce a graph $G^{\prime}(V,E^{\prime})$,
where the edges of $G^{\prime}$ are those edges that were queried and received
a positive answer. As the algorithm is not bounded in its computation time, it
can find the maximum clique in $G^{\prime}$. Hence the goal of the querying
process is to produce a graph $G^{\prime}$ in which the maximum clique is as
large as possible. We denote this maximum clique by $K$ and its size by $k$.
Note that for any nontrivial algorithm (for which $k>1$), $K$ (and likewise
$k$) is a random variable that will depend on the input graph $G$. Hence for a
given algorithm, we shall think of $k$ as the median value of the size of the
clique that the algorithm finds. For reasons that will become clear later, if
$k$ is even our results are somewhat simpler to express. Hence, we shall
assume that $k$ is even (this has negligible effect on the results, a
difference of at most 1 in the size of the clique found).

We shall use $\delta$ as a parameter indicating the allowed number of queries,
where $q=n^{\delta}$. (Sometimes the interpretation of $\delta$ will be
relaxed to requiring $q=O(n^{\delta})$. This has negligible effect on the
results.) Hence our goal is to maximize $k$ (as a function of $n$ and
$\delta$), such that there is an algorithm making at most $n^{\delta}$
queries, for which with probability at least $\frac{1}{2}$ over the choice of
$G\sim G(n,\frac{1}{2})$, the graph $G^{\prime}$ contains a clique $K$ of size
$k$.

We consider only $\delta\geq 1$, as for smaller $\delta$ the number of non-
isolated vertices in $G^{\prime}$ will be $n^{\prime}<n$, and we may solve a
similar problem with $n^{\prime}$ instead of $n$. For $\delta=2$, the whole
graph may be queried. The clique of maximum size in a graph $G\sim
G(n,\frac{1}{2})$ is with high probability (w.h.p.) of size roughly
(neglecting low order terms) $2\log n$ (see [13]). Therefore, the size of the
maximum clique in $G^{\prime}$ satisfies w.h.p. $k\leq 2\log n+\Theta(1)$ for
every $1\leq\delta<2$. On the other hand, a clique of (expected) size $\log n$
may be found using roughly $2n$ queries in the following way. Initialize the
sets $K=\emptyset$, $T=V(G)$. While $T$ is not empty repeat the following:

  1. 1.

Choose arbitrarily $t\in T$, and update $K\leftarrow K\cup\\{t\\}$.

  2. 2.

Query all pairs $\\{\\{t,t^{\prime}\\}\mid t^{\prime}\in
T\setminus\\{t\\}\\}$.

  3. 3.

Remove $t$ and all its non-neighbors from $T$.

The size of $T$ decreases by a factor of $2$ in each iteration (in
expectation), hence there are roughly $\log n$ iterations, and the total
expected number of queries is $2n$. After the last iteration, the set $K$ is a
clique of expected size $\log n$. Therefore, the values of $k$ of interest are
between $\log n$ and $2\log n$. In all computations we will neglect terms of
order $o(\log n)$ in the size of $k$. Hence, we can state the problem we wish
to solve in the following way: Maximize $\alpha$ for which a clique of size
$k\geq\alpha\log n-o(\log n)$ may be found using a sequence of at most
$n^{\delta}$ queries. Note that $\alpha$ is a function of $\delta$ which
satisfies $1\leq\alpha\leq 2$. We give a more formal definition of the value
$\alpha$ we wish to find.

######  Definition 1.1.

Let $1\leq\delta<2$, $\alpha\leq 2$. A deterministic algorithm $\mathcal{A}$,
which makes a sequence of at most $n^{\delta}$ adaptive queries (based on
oracle answers), will be called a $(\delta,\alpha)$-algorithm if for every
sufficiently large $n$, with probability at least $\frac{1}{2}$, the graph
$G^{\prime}$ (induced on edges discovered by the algorithm) contains a clique
of size $k\geq\alpha\log n-o(\log n)$.

######  Definition 1.2.

Let $1\leq\delta<2$. $\alpha_{*}(\delta)$ is defined as the supremum over
$\alpha$ such that there exists a $(\delta,\alpha)$-algorithm. Note that
$1\leq\alpha_{*}(\delta)\leq 2$.

######  Remark 1.3.

Since we do not limit the time complexity of algorithms, if $G^{\prime}$
contains at least one clique of size $k$, $\mathcal{A}$ can be assumed to find
such a clique $K$ (e.g., by using exhaustive search), and to return it.

A full solution to the stated problem is to find the exact value of
$\alpha_{*}(\delta)$ for every $1\leq\delta<2$. Lower bounds on
$\alpha_{*}(\delta)$ are proved by algorithms which find cliques of size
$\alpha\log n$ (for $\alpha>1$). Such algorithms were presented in [5], and
can be found in Section 4.1. The presented algorithms are suitable also for a
slightly different problem setting, in which the adaptiveness of the algorithm
is restricted to a constant number of rounds. The upper bounds we will present
in this paper will be for this restricted setting. In this setting, the
algorithm may use a constant number $l$ of rounds, where in each round it may
query at most $n^{\delta}$ edge queries simultaneously, and the oracle answers
all of them. This means that the algorithm may choose queries on round $i$
based on answers given in previous rounds, but not on those given for queries
in round $i$. Denote by $q_{i}$ the number of queries in round $i$. The
pattern of queries in the first round gives us the queries graph $Q_{1}$ with
$n$ vertices and $q_{1}$ edges. Likewise, the pattern of queries in any other
round $i$ (that may depend on the answers to queries of previous rounds) gives
us the queries graph $Q_{i}$ with $n$ vertices and $q_{i}$ edges. Note that
the edges of $Q_{i}$ consist of all pairs queried in round $i$, and not only
positive ones. We denote by $Q_{\leq i}$ the queries graph which includes all
queries up to round $i$, i.e., $E(Q_{\leq i})=\bigcup_{j\leq i}E(Q_{j})$.
(Note that we use the term ’up to’ in the meaning of ’up to and including’).
We modify definitions 1.1 and 1.2 to comply with the restricted setting.

######  Definition 1.4.

Let $l\in\mathbb{N}$, $1\leq\delta<2$, $\alpha\leq 2$. A deterministic
algorithm $\mathcal{A}$, which makes $l$ rounds of queries with at most
$n^{\delta}$ queries in each round, will be called a
$(\delta,l,\alpha)$-algorithm if for every sufficiently large $n$, with
probability at least $\frac{1}{2}$, $G^{\prime}$ contains a clique of size
$k\geq\alpha\log n-o(\log n)$.

######  Definition 1.5.

Let $l\in\mathbb{N}$, $1\leq\delta<2$. $\alpha_{*}(\delta,l)$ is defined as
the supremum over $\alpha$ such that there exists a
$(\delta,l,\alpha)$-algorithm.

These definitions can be generalized to the case where the number of queries
may not be the same in all rounds. In general, we may assume that in round $i$
the algorithm is restricted to $q_{i}=n^{\delta_{i}}$ queries for some
$0<\delta_{i}<2$. This leads to similar definitions of a
$((\delta_{1},\dots,\delta_{l}),l,\alpha)$-algorithm and
$\alpha_{*}((\delta_{1},\dots,\delta_{l}),l)$ (see definitions in Section
5.1.2). Note that for every $l\in\mathbb{N}$, denoting
$\delta\coloneqq\max_{i}\delta_{i}$ we have:

$\alpha_{*}((\delta_{1},\dots,\delta_{l}),l)\leq\alpha_{*}(\delta,l)\leq\alpha_{*}(\delta)$

###  1.1 Previous results

The problem of bounding $\alpha_{*}(\delta)$ and $\alpha_{*}(\delta,l)$ was
studied by Feige, Gamarnik, Neeman, Rácz and Tetali [5]. They proved the
following results regarding $\alpha_{*}(\delta,l)$:

  1. 1.

For every $1\leq\delta<2$, $\alpha_{*}(\delta,1)=\delta$.

  2. 2.

For every $1\leq\delta\leq\frac{6}{5}$,
$\alpha_{*}(\delta,2)\geq\frac{4\delta}{3}$, and for every
$\frac{6}{5}\leq\delta<2$, $\alpha_{*}(\delta,2)\geq 1+\frac{\delta}{2}$.

  3. 3.

For every $1\leq\delta<2$, $\alpha_{*}(\delta,3)\geq 1+\frac{\delta}{2}$.

  4. 4.

For $\delta=1$ and every $l\in\mathbb{N}$, $\alpha_{*}(1,l)\leq
2^{1-\frac{1}{2^{l}-1}}$. This gives: $\alpha_{*}(1,2)\leq 1.588$,
$\alpha_{*}(1,3)\leq 1.812$ and so on.

  5. 5.

For every $1\leq\delta<2$ and $l\in\mathbb{N}$, $\alpha_{*}(\delta,l)\leq
2-\delta\left(\frac{2-\delta}{2}\right)^{l}$.

An upper bound on $\alpha_{*}(\delta)$ was proved by Alweiss, Ben Hamida, He,
and Moreira [1]. They showed that for every $1\leq\delta<2$:

$\alpha_{*}(\delta)\leq 1+\sqrt{1-\frac{(2-\delta)^{2}}{2}}$

For example, for $\delta=1$ this gives $\alpha_{*}(1)\leq
1+\sqrt{\frac{1}{2}}\sim 1.707$. Since
$\alpha_{*}(\delta,l)\leq\alpha_{*}(\delta)$, this result also improves the
upper bound on $\alpha_{*}(\delta,l)$ for every $l\geq 3$.

##  2 Our Results

We prove upper bounds on $\alpha_{*}(\delta,l)$ and
$\alpha_{*}((\delta_{1},\dots,\delta_{l}),l)$ for $l\in\\{2,3\\}$ (see Figure
1). Namely, we upper bound the size of clique that is likely to be found using
two or three rounds algorithms. First, we prove the following upper bound for
two-rounds algorithms:

######  Theorem 2.1.

For every $1\leq\delta<2$:

$\alpha_{*}(\delta,2)\leq\frac{4}{3}\delta$

The upper bound in Theorem 2.1 is tight when $1\leq\delta\leq\frac{6}{5}$.
When $\frac{6}{5}<\delta<2$ we have the lower bound $\alpha_{*}(\delta,2)\geq
1+\frac{\delta}{2}$ (see [5] or Section 4.1), so there is a gap between the
bounds. We improve the upper bound for this case by proving the following
theorem:

######  Theorem 2.2.

For every $\frac{6}{5}<\delta<2$:

$\alpha_{*}(\delta,2)\leq 1+\sqrt{(\delta-1)(3-\delta)}$

The lower bound $\alpha_{*}(\delta,2)\geq 1+\frac{\delta}{2}$, when
$\frac{6}{5}<\delta<2$, is achieved by an algorithm which queries less than
$n^{\delta}$ queries in round 1. Therefore, we consider algorithms in which
round 1 is restricted to query at most $n^{\delta_{1}}$ pairs for some
$\delta_{1}<\delta$. We prove the following theorem:

######  Theorem 2.3.

For every $\frac{6}{5}<\delta<2$:

$\alpha_{*}\Big{(}\Big{(}\frac{3}{2}-\frac{\delta}{4},\delta\Big{)},2\Big{)}\leq
1+\frac{\delta}{2}$

The upper bound in Theorem 2.3 is tight for every $\frac{6}{5}<\delta<2$.

For three-rounds algorithms, we have the the lower bound
$\alpha_{*}(\delta,3)\geq 1+\frac{\delta}{2}$ (see [5] or Section 4.1). This
lower bound is achieved by an algorithm which queries less than $n^{\delta}$
queries in rounds 1 and 2. We consider algorithms in which the first two
rounds are restricted, and prove the following theorem:

######  Theorem 2.4.

For every $1\leq\delta<2$:

$\alpha_{*}\Big{(}\Big{(}1-\frac{\delta}{2},1,\delta\Big{)},3\Big{)}\leq
1+\frac{\delta}{2}$

The upper bound in Theorem 2.3 is tight for every $1\leq\delta<2$. We also
prove upper bounds on $\alpha_{*}(\delta,3)$ (i.e., when no round is
restricted), for several values of $\delta$. The bounds we prove are
summarized in the following table:

$\delta$ | 1 | 1.1 | 1.2 | 1.3 | 1.4 | 1.5 | 1.6 | 1.7 | 1.8 | 1.9
---|---|---|---|---|---|---|---|---|---|---
$\alpha_{*}(\delta,3)\leq$ | 1.62 | 1.69 | 1.77 | 1.83 | 1.88 | 1.92 | 1.95 | 1.97 | 1.99 | 1.997
Table 1: Upper bounds on $\alpha_{*}(\delta,3)$ Figure 1: An illustration of
upper and lower bounds on $\alpha_{*}(\delta,l)$ and
$\alpha_{*}((\delta_{1},\dots,\delta_{l}),l)$ for $l\in\\{1,2,3\\}$

For every $1\leq\delta<2$, the upper bounds we prove on $\alpha_{*}(\delta,2)$
and $\alpha_{*}(\delta,3)$ are stronger than the upper bounds on
$\alpha_{*}(\delta,l)$ proved in [5], and than the upper bound
$\alpha_{*}(\delta)\leq 1+\sqrt{1-\frac{(2-\delta)^{2}}{2}}$ proved in [1].

##  3 Related Work

There is extensive research on the query complexity of deterministic and
randomized algorithms. For a given graph property, the query complexity is the
smallest number of edge queries needed to determine whether an input graph
satisfies the property. For some properties, such as determining whether a
graph contains an edge, or whether a graph is connected, all edges must be
queried. These are called evasive properties. The Aanderaa–Karp–Rosenberg
conjecture claims that every nontrivial monotone graph property (i.e remains
true when edges are added) for graphs on $n$ vertices is evasive. While the
AKR conjecture is still open, there are many works proving variations of it.
Rivest and Vuillemin [16] showed that at least $\frac{n^{2}}{16}$ queries are
needed to test for any nontrivial monotone graph property. The constant was
later improved by Scheidweiler and Triesch[17] to the current best result of
$\frac{n^{2}}{3}-o(n^{2})$ queries. Kahn, Saks and Sturtevant used a
topological approach to show that the AKR conjecture is true when the number
of vertices is a prime power [9], and Yao showed it in the case of bipartite
graphs [19].

There has also been research on the query complexity of randomized algorithms.
No nontrivial monotone property is known with randomized query complexity less
than $\frac{n^{2}}{4}$, and a similar conjecture by Karp says that
$\Omega(n^{2})$ queries are required in this case. The first non-linear lower
bound, of $\Omega(n\log^{1/12}n)$, was proved by Yao [18], and later improved
to the current best lower bound of $\Omega(n^{4/3}\log^{1/3}n)$ by Chakrabarti
and Khot [2]. Other lower bounds were given by Friedgut, Kahn and Wigderson
[8] and O’Donnell, Saks, Schramm and Servedio [14] where the bound depends on
a critical probability $p$ such that a graph drawn from $G(n,p)$ satisfies the
property with probability $\frac{1}{2}$. The specific property of having a
subgraph isomorphic to a given graph (which is similar to our case) was proved
by Gröger to have a lower bound of $\Omega(n^{3/2})$ [4]. A summary on
Evasiveness of Graph Properties can be found in lecture notes by Neal Young
from a course taught by László Lovász [11].

A setting more similar to ours, where the input graph is drawn randomly from
$G(n,p)$, was introduced by Ferber, Krivelevich, Sudakov and Viera. They
proved that when $p>\frac{\ln n+\ln\ln n+\omega(1)}{n}$ a Hamiltonian cycle
can be found using $(1+o(1))n$ positive edge queries (which is optimal) [6].
However, when $p=\frac{1+\epsilon}{n}$, in order to find a path of length
$l=\Omega(\frac{\log(\frac{1}{\epsilon})}{\epsilon})$ at least
$\Omega(\frac{l}{p\epsilon\log(\frac{1}{\epsilon})})$ queries are required
(and not only the trivial bound of $\Omega(\frac{l}{p})$) [7]. Colon, Fox,
Grinshpun and He [3], as part of work concerning the online Ramsey number,
studied the problem of determining the number of queries needed to find in
$G\sim G(n,p)$ a copy of a target graph, in particular, a constant size
clique.

The problem we study, of finding a large clique in $G\sim G(n,\frac{1}{2})$,
was introduced by Feige, Gamarnik, Neeman, Rácz and Tetali [5], and further
studied by Alweiss, Ben Hamida, He, and Moreira [1]. See Section 1.1 for
results from these papers. The latter paper also proves bounds on the number
of queries to a random graph $G\sim G(\infty,p)$ needed in order to find a
copy of a graph $H$ with degeneracy $d$.

A related problem, that of finding a planted clique of size
$k\geq(2+\epsilon)\log n$ in a $G(n,\frac{1}{2})$ graph by adaptive probing,
was studied by Ràcz and Schiffer [15]. They proved that
$o(\frac{n^{2}}{k^{2}}+n)$ queries do not suffice in order to find the planted
clique, and that $O(\frac{n^{2}}{k^{2}}\log^{2}n+n\log n)$ queries do suffice.
Mardia, Asi and Chandrasekher [12] designed sub-linear time algorithms
($o(n^{2})$ time complexity, and consequently also $o(n^{2})$ queries) that
find planted cliques of size $k=\omega(\sqrt{n\log\log n})$.

##  4 Preliminaries

###  4.1 Algorithms - lower bounds

The following algorithms, which lower bound $\alpha_{*}(\delta,l)$, were
presented in [5].

#### Algorithm 1 - One round

The following one round algorithm finds a clique of size $\delta\log n$:

Round 1: Choose arbitrarily a set $S$ of $n^{\delta/2}$ vertices, and query
all pairs within $S$ (roughly $n^{\delta}$ pairs). Find a clique $K$ of size
$\delta\log n$ in the graph induced on $S$, and return $K$. Such a clique
exists w.h.p. as this is the expected size of the maximum clique in $S$.

#### Algorithm 2 - Two rounds when $\delta\leq\frac{6}{5}$

The following two rounds algorithm finds a clique of size
$\frac{4}{3}\delta\log n$ when $1\leq\delta\leq\frac{6}{5}$:

Round 1: Choose arbitrarily a set $S$ of $n^{\delta/6}$ vertices and a set $T$
of $n^{{5\delta}/6}$ vertices not in $S$ ($|T|\leq n$ since
$\delta\leq\frac{6}{5}$). Query all pairs within $S$ and all pairs in $S\times
T$ (roughly $n^{\delta}$ pairs). Find a clique $S^{\prime}$ of size
$\frac{\delta}{3}\log n$ in the graph induced on $S$. Such a clique exists
w.h.p. as this is the expected size of the maximum clique in $S$. Let
$T^{\prime}\subset T$ be the set of mutual neighbors of $S^{\prime}$. It is of
expected size $|T|\cdot 2^{-\frac{\delta}{3}\log n}=n^{{\delta}/2}$.

Round 2: Query all pairs within $T^{\prime}$ (roughly $n^{\delta}$ pairs).
Find a clique $T^{\prime\prime}$ of size $\delta\log n$ in the graph induced
on $T^{\prime}$ (neglecting low order terms, such a clique exists w.h.p.).
Return $K\coloneqq S^{\prime}\cup T^{\prime\prime}$, which is of size
$\frac{4\delta}{3}\log n$.

We get that for every $1\leq\delta\leq\frac{6}{5}$:
$\alpha_{*}(\delta,2)\geq\frac{4}{3}\delta$.

#### Algorithm 3 - Two rounds when $\delta\geq\frac{6}{5}$

The following two rounds algorithm finds a clique of size
$(1+\frac{\delta}{2})\log n$ when $\frac{6}{5}\leq\delta<2$:

Round 1: Choose arbitrarily a set $S$ of $n^{(1-\delta/2)/2}$ vertices, and
let $T$ be the set of all vertices not in $S$. Query all pairs within $S$
(roughly $n^{1-\delta/2}<n^{\delta}$ pairs), and all pairs in $S\times T$
(roughly $n^{3/2-\delta/4}$ pairs, which is less than $n^{\delta}$ when
$\delta\geq\frac{6}{5}$). Find a clique $S^{\prime}$ of size
$(1-\frac{\delta}{2})\log n$ in the graph induced on $S$ (exists w.h.p.). Let
$T^{\prime}\subset T$ be the set of mutual neighbors of $S^{\prime}$. It is of
expected size $|T|\cdot 2^{-(1-\frac{\delta}{2})\log n}\simeq n^{{\delta}/2}$.

Round 2: Query all pairs within $T^{\prime}$ (roughly $n^{\delta}$ pairs).
Find a clique $T^{\prime\prime}$ of size $\delta\log n$ (neglecting low order
terms) in the graph induced on $T^{\prime}$ (exists w.h.p.). Return
$K\coloneqq S^{\prime}\cup T^{\prime\prime}$, which is of size
$(1+\frac{\delta}{2})\log n$.

We get that for every $\frac{6}{5}\leq\delta<2$: $\alpha_{*}(\delta,2)\geq
1+\frac{\delta}{2}$.

#### Algorithm 4 - Three rounds

The following three rounds algorithm finds a clique of size
$(1+\frac{\delta}{2})\log n$.

Round 1: Choose arbitrarily a set $S$ of $n^{(1-\delta/2)/2}$ vertices. Query
all pairs within $S$ (roughly $n^{1-\delta/2}<n^{\delta}$ pairs). Find a
clique $S^{\prime}$ of size $(1-\frac{\delta}{2})\log n$ in the graph induced
on $S$ (exists w.h.p.).

Round 2: Let $T$ be a set of $\frac{n}{|S^{\prime}|}$ vertices not in $S$.
Query all pairs in $S^{\prime}\times T$ (roughly $n$ pairs) and let
$T^{\prime}\subset T$ be the set of mutual neighbors of $S^{\prime}$. It is of
expected size $|T|\cdot 2^{-(1-\frac{\delta}{2})\log
n}\simeq\frac{n^{{\delta}/2}}{|S^{\prime}|}$.

Round 3: Query all pairs within $T^{\prime}$ (roughly $n^{\delta}$ pairs).
Find a clique $T^{\prime\prime}$ of size $\delta\log n$ (neglecting low order
terms) in the graph induced on $T^{\prime}$ (exists w.h.p.). Return
$K\coloneqq S^{\prime}\cup T^{\prime\prime}$, which is of size
$(1+\frac{\delta}{2})\log n$.

We get that for every $1\leq\delta<2$: $\alpha_{*}(\delta,3)\geq
1+\frac{\delta}{2}$.

Algorithms 2 and 3 have the same queries structure in general. Both query on
round 1 all pairs within some set $S$, and between $S$ and some set $T$, and
on round 2 query all pairs within some $T^{\prime}\subset T$. The sizes of the
sets are chosen such that the constraint on the number of queries is
satisfied, and the returned clique size is maximized (in relation to similar
algorithms). The major difference between algorithms 2 and 3 is that in
Algorithm 2 the set of vertices participating in any query is of size smaller
than $n$ (when $\delta<\frac{6}{5}$). So the effective number of vertices in
$G$ in that case is smaller than $n$ (as we may discard vertices that are
never queried). When $\delta=\frac{6}{5}$ both algorithms are identical and
this is the smallest $\delta$ for which the size of $T$ (and therefore the
effective size of the graph $G$) is of size roughly $n$. For larger $\delta$,
the size of $T$ cannot increase further, and the growth rate of $\alpha$ as a
function of $\delta$ decreases (from $\frac{4}{3}\delta$ to
$1+\frac{\delta}{2}$).

In fact, Algorithm 3 resembles Algorithm 4 more than it resembles Algorithm 2.
Both algorithms 3 and 4 find the same clique size, and the extra round in
Algorithm 4 has no benefit to the size of the clique. The only difference is
that round 1 of Algorithm 3 is split to rounds 1,2 in Algorithm 4, and this
allows to leave out some unnecessary queries. This reduction in the number of
queries allows using Algorithm 4 also when $\delta<\frac{6}{5}$, in which case
the clique returned is larger than the one returned by Algorithm 2
($\frac{4}{3}\delta<1+\frac{\delta}{2}$ for $\delta<\frac{6}{5}$).

###  4.2 Constrained algorithms

Let $\mathcal{A}$ be a $(\delta,l,\alpha)$-algorithm. Assuming the algorithm
succeeds, we denote the clique it returns by $K$, where $|V(K)|=k=\alpha\log
n$. After round $i$, each pair of vertices $u,v\in V$ is of one of three
types:

  1. 1.

The pair $u,v$ was not queried up to round $i$.

  2. 2.

The pair $u,v$ was queried up to round $i$ and answered positively.

  3. 3.

The pair $u,v$ was queried up to round $i$ and answered negatively.

The state $K_{i}$, of the returned clique after round $i$, is the state of all
pairs of vertices of $K$ after round $i$. Since we assume the algorithm
succeeds and $K$ is indeed a clique, the last state $K_{l}$ consists only of
pairs of type $2$. Therefore, there are no pairs of type $3$ in any of the
states $K_{i}$, and we can look at $K_{i}$ as a subgraph of $K_{l}$ which
contains only edges queried up to round $i$. Note that $K_{0}$ is an
independent set.

The only constraints we had on the algorithm so far were the number of query
rounds it was allowed to make and the number of edge queries in each of them.
Following the proof method introduced in [5], the algorithms we will analyze
will have some more constraints upon them. Those constraints will refer to
properties of the states $K_{i}$ during the algorithm’s runtime. Such
properties may be for example - the size of the maximum matching in $K_{i}$,
the number of edges in some subgraph, and etc. The idea behind this is that
such algorithms will be easier to analyze because we may assume the
intermediate states $K_{i}$ satisfied several properties.

Each constraint will be associated with some parameter which receives values
out of some finite domain. The (ordered) set of all parameters will be
referred to as the template, and each proper assignment of the template will
be referred to as a signature. Let $\mathcal{S}$ be the set of all possible
signatures (note that $\mathcal{S}$ may be a subset of the Cartesian product
of the parameters’ domains). We say that an algorithm $\mathcal{A}$ had a
signature $p\in\mathcal{S}$ if the values of all parameters in the template
were according to $p$ during the runtime of the algorithm. For example, we may
use two constraints - the size of the maximum matching in $K_{1}$, and the
number of edges in $K_{1}$. The template will be $(m_{1},e_{1})$, and the set
of signatures will be some subset of the following set (considering only pairs
of integers):

$\mathcal{S}\subseteq\Big{[}0,\frac{k}{2}\Big{]}\times\Big{[}0,{k\choose{2}}\Big{]}$

For a signature $p\in\mathcal{S}$, and an algorithm $\mathcal{A}$, we define
the algorithm $\mathcal{A}_{p}$ as follows. $\mathcal{A}_{p}$ succeeds, and
returns the clique $K$, if and only if $\mathcal{A}$ returned $K$ and had the
signature $p$. Otherwise, the algorithm fails. In the example with template
$(m_{1},e_{1})$, if the maximum matching of $K_{1}$ when $\mathcal{A}$ runs is
$a^{*}$ and the number of edges is $b^{*}$, then only $\mathcal{A}_{p}$ with
$p=(a^{*},b^{*})$ returns $K$ (assuming $\mathcal{A}$ succeeds). Note that if
$\mathcal{A}$ succeeds, there is exactly one $p\in\mathcal{S}$ for which the
algorithm $\mathcal{A}_{p}$ succeeds. If $\mathcal{A}$ fails, all
$\mathcal{A}_{p}$’s fail too.

Due to the extra structure, it will be simpler to analyze the algorithms
$\mathcal{A}_{p}$ instead of $\mathcal{A}$. Given some upper bound on the
probability $\mathcal{A}_{p}$ succeeds for any $p$, we will derive a bound on
the probability $\mathcal{A}$ succeeds, and then derive a bound on
$\alpha_{*}(\delta,l)$. This can be generalized to the case where we have
several upper bounds (denote their amount by $B$). We will assume that the $B$
bounds have the following form:

$\mathbb{P}(\mathcal{A}_{p}\text{ succeeds})\leq n^{f_{1}^{j}(p)k}\cdot
2^{-f_{2}^{j}(p){k\choose{2}}}$

where $f_{1}^{j},f_{2}^{j}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{S}\rightarrow\mathbb{R}$ for every $1\leq j\leq B$, and
$f_{1}^{j}(p),f_{2}^{j}(p)$ do not depend on $n$. We give a brief overview to
the reason we consider bounds of this form, which will become more clear when
we prove the actual bounds.

  * •

$n^{f_{1}^{j}(p)k}$ will be the number of candidate sets (sets of vertices of
$G$) that satisfy the signature $p$, and possibly may be returned as the
clique $K$.

  * •

$2^{-f_{2}^{j}(p){k\choose{2}}}$ will be the probability that some subset of
the edges within a candidate set will be positive. If this event occurs, we
refer to the candidate set as a feasible set. A clique $K$ returned by the
algorithm must be a feasible set.

  * •

The product $n^{f_{1}^{j}(p)k}\cdot 2^{-f_{2}^{j}(p){k\choose{2}}}$ will be an
upper bound on the expected number of feasible sets. Using this bound we will
derive a bound on $\mathbb{P}(\mathcal{A}_{p}\text{ succeeds})$ (using
Markov’s inequality).

In order to prove upper bounds on $\alpha_{*}(\delta,l)$ using upper bounds on
$\mathbb{P}(\mathcal{A}_{p}\text{ succeeds})$, we prove the following lemma.

######  Lemma 4.1.

Let $1\leq\delta<2$, $l\geq 1$, and let $\mathcal{S}$ be a set of signatures
such that $|\mathcal{S}|=n^{o(\log n)}$. Suppose we have several upper bounds
(denote their amount by $B$) on the probability algorithm $\mathcal{A}_{p}$
succeeds. Suppose the bounds are of the following form:
$\mathbb{P}(\mathcal{A}_{p}\text{ succeeds})\leq n^{f_{1}^{j}(p)k}\cdot
2^{-f_{2}^{j}(p){k\choose{2}}}$ where
$f_{1}^{j},f_{2}^{j}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{S}\rightarrow\mathbb{R}$ for every $1\leq j\leq B$, and
$f_{1}^{j}(p),f_{2}^{j}(p)$ do not depend on $n$. Then:

$\alpha_{*}(\delta,l)\leq\max_{p\in\mathcal{S}}\min_{j}\frac{2f_{1}^{j}(p)}{f_{2}^{j}(p)}$

###### Proof.

Denote $\alpha=\alpha_{*}(\delta,l)$, $k=\alpha\log n$, and let $\mathcal{A}$
be a $(\delta,l,\alpha)$-algorithm. Assume for contradiction
$\alpha>\max_{p\in\mathcal{S}}\min_{j}\frac{2f_{1}^{j}(p)}{f_{2}^{j}(p)}$.
Given the upper bounds, we have that $\mathbb{P}(\mathcal{A}_{p}\text{
succeeds})\leq\min_{j}n^{f_{1}^{j}(p)k}\cdot 2^{-f_{2}^{j}(p){k\choose{2}}}$.
If $\mathcal{A}$ succeeds, there must be some $p\in\mathcal{S}$ for which
$\mathcal{A}_{p}$ succeeds (we define $\mathcal{S}$ to include all possible
outcomes). Hence, using union bound we get:

$\displaystyle\frac{1}{2}$ $\displaystyle\leq\mathbb{P}(\mathcal{A}\text{
succeeds})$
$\displaystyle\leq\sum_{p\in\mathcal{S}}\mathbb{P}(\mathcal{A}_{p}\text{
succeeds})$
$\displaystyle\leq\Big{[}\max_{p\in\mathcal{S}}\mathbb{P}(\mathcal{A}_{p}\text{
succeeds})\Big{]}\cdot n^{o(\log n)}$
$\displaystyle\leq\Big{[}\max_{p\in\mathcal{S}}\min_{j}\Big{(}n^{f_{1}^{j}(p)k}\cdot
2^{-f_{2}^{j}(p){k\choose{2}}}\Big{)}\Big{]}\cdot n^{o(\log n)}$

Taking $\log$ of both sides we get:

$\displaystyle\log\Big{(}\Big{[}\max_{p\in\mathcal{S}}\min_{j}\Big{(}n^{f_{1}^{j}(p)k}\cdot
2^{-f_{2}^{j}(p){k\choose{2}}}\Big{)}\Big{]}\cdot n^{o(\log n)}\Big{)}\geq$
$\displaystyle-1$
$\displaystyle\max_{p\in\mathcal{S}}\min_{j}\Big{[}{f_{1}^{j}(p)k}\log
n-f_{2}^{j}(p){k\choose{2}}\Big{]}+o(\log^{2}n)\geq$ $\displaystyle-1$
$\displaystyle\max_{p\in\mathcal{S}}\min_{j}\Big{[}(2f_{1}^{j}(p)-\alpha
f_{2}^{j}(p))\Big{]}\frac{1}{2}\alpha\log^{2}n+o(\log^{2}n)\geq$
$\displaystyle-1$

For sufficiently large $n$, this expression is dominated by the term
$\log^{2}n$. Since we assumed that
$\alpha>\max_{p\in\mathcal{S}}\min_{j}\frac{2f_{1}^{j}(p)}{f_{2}^{j}(p)}$, we
have that for every $p\in\mathcal{S}$ there exists $j$ such that:

$\displaystyle\alpha>\frac{2f_{1}^{j}(p)}{f_{2}^{j}(p)}$
$\displaystyle\implies 2f_{1}^{j}(p)-\alpha f_{2}^{j}(p)<0$

Therefore, $\max_{p\in\mathcal{S}}\min_{j}\Big{[}(2f_{1}^{j}(p)-\alpha
f_{2}^{j}(p))\Big{]}<0$ and as $n\rightarrow\infty$ we have that:

$\max_{p\in\mathcal{S}}\min_{j}\Big{[}(2f_{1}^{j}(p)-\alpha
f_{2}^{j}(p))\Big{]}\frac{1}{2}\alpha\log^{2}n+o(\log^{2}n)\rightarrow-\infty$

Which is a contradiction. ∎

We show examples of the use of Lemma 4.1 in the proofs of lemmas 4.2 and 4.3.
Lemma 4.2 was proved in [5]. Here we illustrate how Lemma 4.1 can be used in
order to prove this lemma.

######  Lemma 4.2.

For every $1\leq\delta<2$:

$\alpha_{*}(\delta,1)\leq\delta$

###### Proof.

We will use Lemma 4.1 with a template which consists of a single parameter,
the size of the maximum matching in $K_{1}$. An algorithm $\mathcal{A}_{p}$
may succeed only if the maximum matching in $K_{1}$ is a perfect matching,
i.e., of size $\frac{1}{2}k$. Therefore, there is only one relevant signature
of the template to consider, which we denote $p_{0}$. In order to bound
$\mathbb{P}(\mathcal{A}_{p_{0}}\text{ succeeds})$, we first bound the number
of subgraphs that may be the returned clique $K$. A set of vertices $a$ will
be called a candidate if it satisfies the following:

  * •

$|a|=k$.

  * •

$Q_{1}$ induced on $a$ has a perfect matching of size $\frac{1}{2}k$.

Note that if the algorithm succeeds, it must return a candidate. The number of
candidates is bounded by the number of ways to choose a perfect matching. The
perfect matching is a set of $\frac{1}{2}k$ edges out of the $n^{\delta}$
edges in $Q_{1}$. Hence there are at most
${{n^{\delta}}\choose{\frac{1}{2}k}}\leq n^{\frac{1}{2}\delta k}$ candidates.
For a candidate to be a clique, all ${k\choose{2}}$ edges within it must be
positive, and this happens with probability $2^{-{k\choose{2}}}$. Therefore,
$\mathbb{P}(\mathcal{A}_{p_{0}}\text{ succeeds})\leq n^{\frac{1}{2}\delta
k}\cdot 2^{-{k\choose{2}}}$, and by Lemma 4.1:

$\alpha_{*}(\delta,1)\leq\delta$

∎

For the next lemma, we use a template which consists of the following
parameters:

  * •

$m_{i}\in[0,\frac{1}{2}]$ where $1\leq i\leq l$ and $m_{i}k$ is the size of
the maximum matching in $K_{i}$.

  * •

$w_{i}\in[0,1]$ where $0\leq i\leq l$ and $w_{i}{k\choose{2}}$ is the number
of edges of $K$ not queried up to round $i$ (i.e., the number of edges in the
complement of $K_{i}$). Note that $w_{0}=1$.

######  Lemma 4.3.

For every $l\in\mathbb{N}$, and $1\leq\delta<2$:

$\alpha_{*}(\delta,l)\leq\max_{p\in\mathcal{S}}\min_{1\leq i\leq
l}\frac{2-(4-2\delta)m_{i}}{w_{i-1}}$

###### Proof.

Let $1\leq i\leq l$, and let $p\in\mathcal{S}$ be some signature. We start
with an upper bound on the number of subgraphs of $G$ which after round $i$
may be the subgraph $K_{i}$. Such subgraphs, which will be called
$i$-candidates, must satisfy several conditions in order to comply with the
signature. A set of vertices $a$ will be called an $i$-candidate if it
satisfies the following:

  * •

$|a|=k$.

  * •

$Q_{\leq i}$ induced on $a$ has a maximum matching of size $m_{i}k$.

  * •

$Q_{\leq(i-1)}$ induced on $a$ has $(1-w_{i-1}){k\choose{2}}$ edges.

An $i$-candidate $a$ may be partitioned to $b\sqcup c$ where $b$ consists of
the $2m_{i}k$ vertices covered by a maximum matching (breaking ties
arbitrarily), and $c$ is the rest of the vertices ($\mathinner{\\!\left\lvert
c\right\rvert}=(1-2m_{i})k$). The maximum matching must be some subset of
$m_{i}k$ edges among the $in^{\delta}$ edges queried up to round $i$, so we
can upper bound the number of different matchings by the number of subsets of
$m_{i}k$ queries. Hence, there are at most ${{in^{\delta}}\choose{m_{i}k}}$
ways to choose the set $b$. The $(1-2m_{i})k$ vertices in $c$ may be any
vertices of $V$, so there are at most ${{n}\choose{k(1-2m_{i})}}$ ways to
choose $c$. Therefore, the number of $i$-candidates is at most
${{in^{\delta}}\choose{m_{i}k}}{{n}\choose{k(1-2m_{i})}}\leq n^{\delta
m_{i}k+k(1-2m_{i})}=n^{(1-(2-\delta)m_{i})k}$.

The queries up to round $i$ are determined by the answers to the queries up to
round $i-1$. The answers given on round $i$ and on later rounds, do not affect
which subgraphs belong to the family of $i$-candidates (as opposed to answers
given up to round $i-1$). Any pair of vertices not queried up to round $i-1$
has probability $\frac{1}{2}$ of being answered positively when queried, and
in any $i$-candidate there are $w_{i-1}{k\choose{2}}$ such potential edges. If
all these edges in a given $i$-candidate are answered positively, we say that
the candidate is $i$-feasible. The probability an $i$-candidate is
$i$-feasible is $2^{-w_{i-1}{k\choose{2}}}$.

The clique $K$ returned by the algorithm must be an $i$-feasible set for every
$i$. Hence, in order for $\mathcal{A}_{p}$ to succeed, there must be a set
which is $i$-feasible for every $i$. Using union bound we get that the
probability $\mathcal{A}_{p}$ will succeed is at most
$n^{(1-(2-\delta)m_{i})k}\cdot 2^{-w_{i-1}{k\choose{2}}}$ for every $i$. In
addition, we have $|\mathcal{S}|=polylog(n)$. Therefore, by Lemma 4.1:

$\alpha_{*}(\delta,l)\leq\max_{p\in\mathcal{S}}\min_{1\leq i\leq
l}\frac{2-(4-2\delta)m_{i}}{w_{i-1}}$

∎

In [5] a variation of Lemma 4.3 was used, where the constrained parameters
were $w_{i}$, and bounds on $m_{i}$ were deduced from them. We will use the
opposite direction, which is simpler, and deduce bounds on $w_{i}$ from
$m_{i}$.

####  4.2.1 Restricting the signatures set

When we use Lemma 4.1 it will sometimes be useful to restrict the signatures
set over which we maximize, when we bound $\alpha_{*}(\delta,l)$. For this
purpose, we include the size of the maximum independent set in $K_{l-1}$ as a
parameter in the template, denoted $I_{l-1}$. An independent set in $K_{l-1}$
must be a clique fully queried in round $l$, in order for $K_{l}$ to be a
clique. Finding any clique of size $I_{l-1}$ in round $l$, considering only
subgraphs completely un-queried up to round $l-1$, is at least as hard as
finding a clique of size $I_{l-1}$ using a one round algorithm (since all
queries are answered independently). Using Lemma 4.2, we cannot expect to find
a clique if $I_{l-1}>\delta\log n$. This is formulated in the following lemma,
which is proved in Appendix A.

######  Lemma 4.4.

Let $\mathcal{S}_{I_{l-1}\leq\delta\log
n}\sqcup\mathcal{S}_{I_{l-1}>\delta\log n}$ be a partition of the signatures
in $\mathcal{S}$ according to the size of $I_{l-1}$ in relation to $\delta\log
n$. Lemma 4.1 holds when $\mathcal{S}$ is restricted to
$\mathcal{S}_{I_{l-1}\leq\delta\log n}$, i.e.,

$\alpha_{*}(\delta,l)\leq\max_{p\in\mathcal{S}_{I_{l-1}\leq\delta\log
n}}\min_{j}\frac{2f_{1}^{j}(p)}{f_{2}^{j}(p)}$

###  4.3 Gallay-Edmonds decomposition (GED)

In order to prove upper bounds in the case of three rounds, we will use the
Gallay-Edmonds Decomposition (see, e.g., [10]) of the subgraphs $K_{i}$. A
graph $H$, with maximum matching of size $m$, decomposes into three sets (see
Figure 2). The set $C$ consists of all vertices such that there is a maximum
matching in which they are not covered. The set $S$ (separator) consists of
the neighbors of $C$ ($S=N(C)\setminus C$), and $R$ is the rest of the
vertices (i.e., non-neighbors of $C$). The decomposition satisfies the
following:

  * •

The set $C$ is composed of $c$ connected components of odd size (referred to
as odd components) and no components of even size. The size of $R$ is even.

  * •

Any maximum matching satisfies:

    * –

$R$ is matched to itself (perfectly).

    * –

in any odd component, all vertices but one are matched to each other
(perfectly).

    * –

All vertices of $S$ are matched to vertices of $C$ of distinct odd components
(to vertices not matched within $C$).

  * •

In any maximum matching there are $c-|S|$ unmatched vertices, so
$c-|S|=|V(H)|-2m$.

Given a specific maximum matching $M$, we will sometimes use another
definition of the decomposition, which depends on $M$. We refer to it as a
specific matching decomposition. It is composed of the sets
$C^{*+},C^{*-},S,D$ defined as follows (see Figure 2):

  * •

$S$ is the same as in Gallay-Edmonds Decomposition (GED).

  * •

$C^{*+}$ is the set of vertices matched to $S$.

  * •

$C^{*-}$ is the set of unmatched vertices. Denoting $C^{*}=C^{*+}\cup C^{*-}$
we have $|C^{*}|=c$.

  * •

$D$ is the set of the rest of the vertices(i.e., $R$ and the even matched part
of each odd component).

Note that $C^{*}$ is an independent set and that the number of edges between
$D$ and $C^{*}$ is at most linear in $|V(H)|$ (since any vertex in $D$ has at
most one neighbor in $C^{*}$).

Figure 2: Gallay-Edmonds decomposition (right) and specific matching
decomposition (left)

##  5 Upper Bounds

###  5.1 Two rounds

####  5.1.1 Tight bound for two rounds with small $\delta$

We prove an upper bound on $\alpha_{*}(\delta,2)$ for every $1\leq\delta<2$,
which is tight when $1\leq\delta\leq\frac{6}{5}$.

######  Theorem 5.1.

Let $1\leq\delta<2$. Then:

$\alpha_{*}(\delta,2)\leq\frac{4}{3}\delta$

###### Proof.

Denote by $M_{1}$ some matching of maximum size in the subgraph of $Q_{1}$
induced on $V(K)$, i.e., in $K_{1}$ (breaking ties arbitrarily). Its size is
denoted by $m_{1}k$, where $0\leq m_{1}\leq\frac{1}{2}$. The set of $2m_{1}k$
vertices covered by $M_{1}$ is denoted by $V_{M_{1}}$. The number of edges in
the subgraph of $Q_{1}$ induced on $V_{M_{1}}$ is denoted by $e_{1}{k\choose
2}$, where $0\leq e_{1}\leq 1$. Both $m_{1},e_{1}$ will be in the template we
will use.

Consider $K_{1}$ which satisfies the signature $(m_{1},e_{1})$, and the
corresponding set $V_{M_{1}}$. The set $K_{1}\setminus V_{M_{1}}$ is
independent, otherwise we could add an edge to the matching $M_{1}$,
increasing its size. Hence, for $K$ to be a clique it is necessary that there
will be a perfect matching in the subgraph of $Q_{2}$ induced on
$V(K)\setminus V_{M_{1}}$. Denote such a matching by $M_{2}$ (breaking ties
arbitrarily). Its size is denoted by $m_{2}k$, hence
$m_{1}+m_{2}=\frac{1}{2}$. Denote $V_{M_{2}}=V(K)\setminus V_{M_{1}}$, and
denote the number of edges in the subgraph of $Q_{2}$ induced on $V(K)$ by
$e_{2}{k\choose 2}$. Observe that $e_{1}+e_{2}\leq 1$, but equality need not
hold, as some pairs $u,v$ for which $v\in V_{M_{1}}$ and $u\in V_{M_{2}}$, may
have been queried in the first round. We add the parameter $e_{2}$ to the
template.

For every signature $p=(m_{1},e_{1},e_{2})$ we wish to bound the probability
that there is a clique $K$ with signature $p$. For such $K$, $V(K)$ must
decompose into $V_{M_{1}},V_{M_{2}}$, and all pairs of vertices in $K$ must be
queried and answered positively, particularly the indicated
$(e_{1}+e_{2}){k\choose{2}}$ pairs.

A set of vertices $a$ will be a $1$-candidate if it is a possible $V_{M_{1}}$
for some $K$, i.e., satisfies the following:

  * •

$|a|=2m_{1}k$.

  * •

$Q_{1}$ induced on $a$ has a perfect matching.

  * •

$Q_{1}$ induced on $a$ has $e_{1}{k\choose{2}}$ edges.

The property of a set being a $1$-candidate depends only on $Q_{1}$, and hence
determined deterministically. There are at most ${q_{1}}\choose{m_{1}k}$ ways
to choose the matching $M_{1}$ which defines $V_{M_{1}}$, hence at most
${q_{1}\choose m_{1}k}$ $1$-candidates.

$a$ will be called $1$-feasible if:

  * •

$a$ is a $1$-candidate.

  * •

All $e_{1}{k\choose{2}}$ queries of $Q_{1}$ induced on $a$ were positive.

The probability a $1$-candidate is feasible is $2^{-e_{1}{k\choose{2}}}$, so
in expectation there are at most ${q_{1}\choose m_{1}k}\cdot
2^{-e_{1}{k\choose{2}}}$ $1$-feasible sets.

Two sets $a,b$ will be a candidate pair if $(a,b)$ are a possible pair for
$V_{M_{1}},V_{M_{2}}$ of some $K$, i.e., satisfy the following:

  * •

$a$ is $1$-feasible.

  * •

$a\cap b=\emptyset$.

  * •

$|b|=2m_{2}k$.

  * •

$Q_{1}$ induced on $b$ is an independent set.

  * •

$Q_{2}$ induced on $b$ has a perfect matching.

  * •

$Q_{2}$ induced on $a\cup b$ has $e_{2}{k\choose{2}}$ edges.

A pair $(a,b)$ will be feasible if:

  * •

$(a,b)$ is a candidate pair.

  * •

All $e_{2}{k\choose{2}}$ queries of $Q_{2}$ induced on $a\cup b$ were
positive.

Given $a$, the sets $b$ which make a candidate pair with $a$ depend on
$Q_{2}$, and $Q_{2}$ depends on the answers to $Q_{1}$. For every choice of
answers to $Q_{1}$, there are at most ${q_{2}}\choose{m_{2}k}$ ways to choose
the matching $M_{2}$ which defines $V_{M_{2}}$, so this bounds the number of
possible such sets $b$. Round $2$ queries are answered positively with
probability $\frac{1}{2}$ independently of $Q_{1}$ answers. In addition, the
number of relevant pairs, $e_{2}{k\choose{2}}$, is chosen in advance. Hence,
the probability a candidate pair will be feasible is
$2^{-e_{2}{k\choose{2}}}$, and in expectation there are at most ${q_{2}\choose
m_{2}k}\cdot 2^{-e_{2}{k\choose{2}}}$ feasible pairs $(a,b)$ for any
$1$-feasible set $a$.

The probability $\mathcal{A}_{p}$ succeeds (where $p=(m_{1},e_{1},e_{2})$) is
at most the probability a feasible pair exists, which is at most the expected
number of such pairs (by Markov’s inequality). By linearity of expectation, we
can write this expectation as the sum of expectations conditioned on a
specific $1$-feasible set $a$. Hence:

$\mathbb{P}(\mathcal{A}_{p}\text{ succeeds})\leq{q_{1}\choose m_{1}k}\cdot
2^{-e_{1}{k\choose{2}}}\cdot{q_{2}\choose m_{2}k}\cdot
2^{-e_{2}{k\choose{2}}}$

Given $q_{1}=q_{2}=n^{\delta}$ we get:

$\mathbb{P}(\mathcal{A}_{p}\text{ succeeds})\leq n^{\frac{1}{2}\delta k}\cdot
2^{-(e_{1}+e_{2}){k\choose{2}}}$

The edges in $K$ may be partitioned into three types:

  1. 1.

$e_{1}{k\choose{2}}$ edges within $V_{M_{1}}$, queried in round 1.

  2. 2.

$e_{2}{k\choose{2}}$ edges within $V(K)$, queried in round 2.

  3. 3.

$(1-e_{1}-e_{2}){k\choose{2}}$ edges between $V_{M_{1}}$ and $V_{M_{2}}$,
queried in round 1. Note that there are no edges within $V_{M_{2}}$ queried in
round 1.

After receiving $Q_{1}$ answers, the algorithm might choose $Q_{2}$ such that
all candidate pairs $a,b$ have only positive $Q_{1}$ queries between them. So
the algorithm may choose to include edges in candidates for $K$, based on
previous information that they are positive. Hence we cannot consider those
edges probability of being positive when bounding the probability a candidate
for $K$ is a clique. We therefore refer to such edges (of the third type) as
”free edges” for the algorithm. This clarifies why we defined feasibility of a
candidate pair to depend only on the $(e_{1}+e_{2}){k\choose{2}}$ edges of the
first two types, which are answered after the algorithm chose to include them
in a candidate.

The following lemma bounds the number of free edges. Its proof appears after
the end of the proof of the current theorem.

######  Lemma 5.2.

Let $H$ be a graph with an even number of vertices, let $V_{M}$ be the set of
vertices matched by a maximum matching in $H$, and let $V_{M}^{-}$ be the rest
of the vertices. Denote by $E^{-}$ the set of edges of $H$ not contained in
$V_{M}$ (i.e., have at least one endpoint in $V_{M}^{-}$). Then
$E^{-}=E(V_{M},V_{M}^{-})$ and $|E^{-}|\leq\frac{1}{2}|V_{M}||V_{M}^{-}|$.

Applying Lemma 5.2 with $H=K_{1}$ we get
$(1-e_{1}-e_{2}){k\choose{2}}\leq\frac{1}{2}\cdot 2m_{1}k\cdot 2m_{2}k$ and
then (using ${k\choose{2}}\simeq\frac{k^{2}}{2}$, neglecting low order terms):

$e_{1}+e_{2}\geq 1-4m_{1}m_{2}=1-4m_{1}(\frac{1}{2}-m_{1})$

Therefore:

$\mathbb{P}(\mathcal{A}_{p}\text{ succeeds})\leq n^{\frac{1}{2}\delta k}\cdot
2^{-(1-4m_{1}(\frac{1}{2}-m_{1})){k\choose{2}}}$

We apply Lemma 4.1 with the signatures set $\mathcal{S}$ defined by
$m_{1},e_{1},e_{2}$ which satisfies $\mathcal{S}=O(\log^{5}n)$. We get:

$\alpha_{*}(\delta,2)\leq\max_{m_{1}}\frac{\delta}{1-4m_{1}(\frac{1}{2}-m_{1})}$

This expression is maximal when $m_{1}(\frac{1}{2}-m_{1})$ is maximal, i.e.,
for $m_{1}=\frac{1}{4}$, and we get the desired upper bound:

$\alpha_{*}(\delta,2)\leq\frac{4}{3}\delta$

∎

######  Corollary 5.3.

For $1\leq\delta\leq\frac{6}{5}$ the upper bound is tight and we have:

$\alpha_{*}(\delta,2)=\frac{4}{3}\delta$

The signature which maximizes the objective function has the following setting
of parameters: $m_{1}=\frac{1}{4}$ and $e_{1},e_{2}$ are such that
$\frac{1}{2}|V_{M_{1}}||V_{M_{2}}|$ edges are queried between $V_{M_{1}}$ and
$V_{M_{2}}$ on round $1$. These values are equal to those in the signature of
Algorithm 2 (see Section 4.1), as we could expect would happen in an optimal
algorithm. We finish with a proof of Lemma 5.2.

###### Proof.

The set $V_{M}^{-}$ must be independent, because if it contains some edge we
could add the edge to the matching, contradicting its maximality. Hence,
$E^{-}=E(V_{M},V_{M}^{-})$. Let $v,u\in V_{M}$ be a pair matched by the
maximum matching. Assume without loss of generality (w.l.o.g) that
$\deg^{-}(u)\leq\deg^{-}(v)$, where $\deg^{-}$ is the number of neighbors in
$V_{M}^{-}$ the vertex has. We claim that $\deg^{-}(u)\geq 1$ implies
$\deg^{-}(u)=\deg^{-}(v)=1$. Assuming $\deg^{-}(u)\geq 1$, Let $w\in
V_{M}^{-}$ be a neighbor of $u$, and assume for contradiction $\deg^{-}(v)\geq
2$. Then, there is some $w\neq z\in V_{M}^{-}$ which is a neighbor of $v$.
Replacing the edge $\\{u,v\\}$ in the matching by $\\{u,w\\}$ and $\\{v,z\\}$
we get a larger matching, which is a contradiction. Hence, either
$\deg^{-}(u)=0$ or $\deg^{-}(u)=\deg^{-}(v)=1$. In both cases, since
$|V_{M}^{-}|\neq 1$ (as $|V(H)|$ is even), this implies
$\deg^{-}(u)+\deg^{-}(v)\leq|V_{M}^{-}|$. Since $E^{-}=E(V_{M},V_{M}^{-})$ we
have:

$|E^{-}|=\sum_{u\in V_{M}}\deg^{-}(u)=\sum_{u\text{ matched to
}v}\deg^{-}(u)+\deg^{-}(v)\leq\frac{1}{2}|V_{M}||V_{M}^{-}|$

∎

####  5.1.2 Bound for two rounds with large $\delta$

The upper bound $\alpha_{*}(\delta,2)\leq\frac{4}{3}\delta$ proved in Theorem
5.1 is tight only for $1\leq\delta\leq\frac{6}{5}$. For $\frac{6}{5}<\delta<2$
we had a lower bound of $1+\frac{\delta}{2}$, which is smaller on this range
of $\delta$ (see Figure 1). Resolving the two rounds with
$\frac{6}{5}<\delta<2$ case is important before proceeding to the analysis of
more rounds with any value of $\delta$. The reason is that we may use an
algorithm for two rounds with large $\delta$, to solve the problem of $l>2$
rounds with small $\delta$. For example we prove the following lemma.

######  Lemma 5.4.

If there exists $\frac{6}{5}<\delta<2$ and $\epsilon>0$ for which
$\alpha_{*}(\delta,2)\geq 1+\frac{\delta}{2}+\epsilon$, then for some
$\epsilon^{\prime}>0$, $\alpha_{*}(1,4)\geq\frac{3}{2}+\epsilon^{\prime}$.
(Note that the current lower bound is $\alpha_{*}(1,4)\geq\frac{3}{2}$).

###### Proof.

Suppose that $\alpha_{*}(\delta,2)\geq 1+\frac{\delta}{2}+\epsilon$, and let
$\mathcal{A}^{2}$ be a $(\delta,2,1+\frac{\delta}{2}+\epsilon)$-algorithm. We
present a $(1,4,\frac{3}{2}+\epsilon^{\prime})$-algorithm $\mathcal{A}^{4}$.
In round 1, $\mathcal{A}^{4}$ queries all pairs in a subset $S$ of size
$\sqrt{n}$, and finds a clique $S^{\prime}$ of size $\beta\log n$, for
$\beta=1-\frac{1}{\delta}<1$. In round 2, $\mathcal{A}^{4}$ queries all pairs
between $S^{\prime}$ and a disjoint set $T$ of size $\frac{n}{|S^{\prime}|}$,
and finds the set of mutual neighbors $T^{\prime}$. $T^{\prime}$ is of
expected size $n^{1-\beta}$ (neglecting low order terms). Then, in rounds 3
and 4, algorithm $\mathcal{A}^{4}$ uses algorithm $\mathcal{A}^{2}$ on the
subgraph $T^{\prime}\subset G$ and finds a clique $T^{\prime\prime}\subset
T^{\prime}$. Specifically, denoting $N=|T^{\prime}|=n^{1-\beta}$ and noting
that $\delta=\frac{1}{1-\beta}$, we have that the number of queries in rounds
3 and 4 is $N^{\delta}=n$. Hence, using $\mathcal{A}^{2}$ on $T^{\prime}$ with
$N^{\delta}$ queries is feasible. By the assumption, the clique
$T^{\prime\prime}$ found this way is of size at least

$\Big{(}1+\frac{\delta}{2}+\epsilon\Big{)}\log
N=\Big{(}1+\frac{1}{2(1-\beta)}+\epsilon\Big{)}(1-\beta)\log
n=\Big{(}\frac{3}{2}-\beta+(1-\beta)\epsilon\Big{)}\log n$

Algorithm $\mathcal{A}^{4}$ outputs the clique $K\coloneqq S^{\prime}\cup
T^{\prime\prime}$, which is of size at least
$(\frac{3}{2}+\epsilon^{\prime})\log n$, where
$\epsilon^{\prime}\coloneqq(1-\beta)\epsilon$. Hence $\alpha_{*}(\delta,2)\geq
1+\frac{\delta}{2}+\epsilon$ implies
$\alpha_{*}(1,4)\geq\frac{3}{2}+\epsilon^{\prime}$. ∎

In the following theorem we improve the upper bound
$\alpha_{*}(\delta,2)\leq\frac{4}{3}\delta$ when $\frac{6}{5}<\delta<2$.

######  Theorem 5.5.

For every $\frac{6}{5}<\delta<2$:

$\alpha_{*}(\delta,2)\leq 1+\sqrt{(\delta-1)(3-\delta)}$

###### Proof.

In the proof of Theorem 5.1 we prove that for every $1\leq\delta<2$:

$\alpha_{*}(\delta,2)\leq\max_{m_{1}}\frac{\delta}{1-4m_{1}(\frac{1}{2}-m_{1})}$

Denote
$\alpha_{2}^{\delta}(m_{1})\coloneqq\frac{\delta}{1-4m_{1}(\frac{1}{2}-m_{1})}$.

We combine this upper bound with Lemma 4.3. For convenience, we replace the
notation of Lemma 4.3 with the notation defined in Theorem 5.1.

$\displaystyle\alpha_{*}(\delta,2)$
$\displaystyle\leq\max_{p\in\mathcal{S}}\min\Big{\\{}{2-(4-2\delta)m_{1}},\frac{2-(4-2\delta)(m_{1}+m_{2})}{e_{2}}\Big{\\}}=$
$\displaystyle=\max_{p\in\mathcal{S}}\min\Big{\\{}{2-(4-2\delta)m_{1}},\frac{\delta}{e_{2}}\Big{\\}}$

Denote $\alpha_{1}^{\delta}(m_{1})\coloneqq 2-(4-2\delta)m_{1}$. We combine
both upper bounds by applying Lemma 4.1 on the corresponding upper bounds on
$\mathbb{P}(\mathcal{A}_{p}\text{ succeeds})$. The expression
$\frac{\delta}{e_{2}}$ imposes a weaker bound than the one proved in Theorem
5.1, so we omit it and get the following upper bound:

$\alpha_{*}(\delta,2)\leq\max_{m_{1}}\min\\{\alpha_{1}^{\delta}(m_{1}),\alpha_{2}^{\delta}(m_{1})\\}$

The maximum over $m_{1}\in[0,\frac{1}{2}]$ may be obtained either on the
boundary ($m_{1}\in\\{0,\frac{1}{2}\\}$), on a local maximum of
$\alpha_{1}^{\delta}$ or $\alpha_{2}^{\delta}$, or when
$\alpha_{1}^{\delta}(m_{1})=\alpha_{2}^{\delta}(m_{1})$. For
$m_{1}\in\\{0,\frac{1}{2}\\}$ we have
$\min\\{\alpha_{1}^{\delta}(m_{1}),\alpha_{2}^{\delta}(m_{1})\\}=\delta$ which
is not maximal. The only local maximum is in $\alpha_{2}^{\delta}$ when
$m_{1}=\frac{1}{4}$. For this $m_{1}$ we have
$\alpha_{2}^{\delta}(\frac{1}{4})=\frac{4}{3}\delta$ and
$\alpha_{1}^{\delta}(\frac{1}{4})=1+\frac{\delta}{2}$. Therefore, for any
$\frac{6}{5}<\delta<2$ we have
$\alpha_{2}^{\delta}(\frac{1}{4})>\alpha_{1}^{\delta}(\frac{1}{4})$, so the
maximum of $\min\\{\alpha_{1}^{\delta}(m_{1}),\alpha_{2}^{\delta}(m_{1})\\}$
cannot be obtained in $m_{1}=\frac{1}{4}$. Hence, the maximum is obtained when
$\alpha_{1}^{\delta}(m_{1})=\alpha_{2}^{\delta}(m_{1})$. Solving this equation
we get:

$\displaystyle\frac{\delta}{1-4m_{1}(\frac{1}{2}-m_{1})}=2-(4-2\delta)m_{1}$
$\displaystyle\delta=2-4m_{1}+8m_{1}^{2}-(4-2\delta)m_{1}+(8-4\delta)m_{1}^{2}-(16-8\delta)m_{1}^{3}$
$\displaystyle
0=-(16-8\delta)m_{1}^{3}+(16-4\delta)m_{1}^{2}-(8-2\delta)m_{1}+2-\delta$

The only solution of the cubic equation satisfying $m_{1}\in(0,\frac{1}{2})$
is:

$m_{1}=\frac{-\sqrt{(\delta-1)(3-\delta)}+1}{4-2\delta}$

For this value of $m_{1}$ we have
$\alpha_{1}^{\delta}(m_{1})=\alpha_{2}^{\delta}(m_{1})=1+\sqrt{(\delta-1)(3-\delta)}$,
hence:

$\alpha_{*}(\delta,2)\leq 1+\sqrt{(\delta-1)(3-\delta)}$

∎

####  5.1.3 Tight bound for two rounds with large $\delta$, restricted first
round

The upper bound proved in Theorem 5.5 may not be tight, as the current best
lower bound for $\frac{6}{5}<\delta<2$ is $\alpha_{*}(\delta,2)\geq
1+\frac{\delta}{2}$. This lower bound is achieved by Algorithm 3, which finds
a clique of size $(1+\frac{\delta}{2})\log n$. The gap between the bounds
might be due to the fact that Algorithm 3 queries less than $n^{\delta}$ pairs
in round 1, while in Theorem 5.5 we prove an upper bound for algorithms that
can query $n^{\delta}$ pairs in round 1. Therefore, we raise the question
whether Algorithm 3 is optimal among all algorithms which query the same
number of queries per round as Algorithm 3 does (which means the number of
round 1 queries in those algorithms is restricted). In round $1$, Algorithm 3
queries all pairs between a set of size $n^{\frac{1}{2}-\frac{\delta}{4}}$ and
the rest of the graph. Hence, the algorithm makes roughly
$n^{\frac{3}{2}-\frac{\delta}{4}}$ queries in round $1$. In round 2, the
algorithm queries all pairs within a set of size $n^{\delta/2}$, which is
roughly $n^{\delta}$ queries. For $\frac{6}{5}<\delta<2$ Denote
$\delta_{1}=\frac{3}{2}-\frac{\delta}{4}$. We will upper bound the maximum
size of a clique that is likely to be found using an algorithm that queries
$n^{\delta_{1}}$ pairs in round 1, and $n^{\delta}$ pairs in round 2. This is
formulated in the following definitions:

######  Definition 5.6.

Let $l\in\mathbb{N}$, $0<\delta_{i}<2$ for every $1\leq i\leq l$, and let
$\alpha\leq 2$. A deterministic algorithm $\mathcal{A}$, which makes $l$
adaptive round queries with at most $n^{\delta_{i}}$ queries in each round,
will be called a $((\delta_{1},\dots,\delta_{l}),l,\alpha)$-algorithm if for
any sufficiently large $n$, with probability at least $\frac{1}{2}$,
$G^{\prime}$ contains a clique of size $k\geq\alpha\log-o(\log n)$.

######  Definition 5.7.

Let $l\in\mathbb{N}$, and let $0<\delta_{i}<2$ for every $1\leq i\leq l$.
$\alpha_{*}((\delta_{1},\dots,\delta_{l}),l)$ is defined as the supremum over
$\alpha$ such that there exists a
$((\delta_{1},\dots,\delta_{l}),l,\alpha)$-algorithm.

Due to the new definitions, some adjustments are needed in previously proved
lemmas. The proof of Lemma 4.1 depends on $\delta$ only implicitly, so the
same proof holds also using definitions 5.6 and 5.7. Lemma 4.3 requires some
adjustments.

######  Lemma 5.8.

Using the same notation of $m_{i},w_{i}$ as in Lemma 4.3, for every
$l\in\mathbb{N}$, and $0<\delta_{i}<2$:

$\alpha_{*}((\delta_{1},\dots,\delta_{l}),l)\leq\max_{p\in\mathcal{S}}\min_{1\leq
i\leq l}\frac{2-(4-2\max_{j\leq i}{\delta_{j}})m_{i}}{w_{i-1}}$

###### Proof.

The only difference between this case and the previous one is that the
matching of size $m_{i}k$ is chosen out of $\sum_{j\leq i}n^{\delta_{j}}\leq
i\cdot n^{\max_{j\leq i}\delta_{j}}$ queries, and not $in^{\delta}$. The set
of vertices not covered by the matching has the same number of candidates and
the probability analysis is the same. Hence, we get
$\mathbb{P}(\mathcal{A}_{p}\text{ succeeds})\leq n^{(1-(2-\max_{j\leq
i}{\delta_{j}})m_{i})k}\cdot 2^{-w_{i-1}{k\choose{2}}}$. We get the desired
bound by Lemma 4.1.

∎

In the following theorem we show that Algorithm 3 is optimal when the first
round is restricted.

######  Theorem 5.9.

For every $\frac{6}{5}<\delta<2$:

$\alpha_{*}\Big{(}\Big{(}\frac{3}{2}-\frac{\delta}{4},\delta\Big{)},2\Big{)}\leq
1+\frac{\delta}{2}$

###### Proof.

Denote $\delta_{1}=\frac{3}{2}-\frac{\delta}{4}$. Similarly to the proof of
Theorem 5.5, we will use two upper bounds. The first bound is by Lemma 5.8,
and it will be useful when
$m_{1}\geq\frac{1-\frac{\delta}{2}}{1+\frac{\delta}{2}}$. The second bound
will be a variation of the bound proved in Theorem 5.1 and will be useful when
$m_{1}\leq\frac{1-\frac{\delta}{2}}{1+\frac{\delta}{2}}$. Note that this
threshold is not coincidental, as it is the value of $m_{1}$ in Algorithm 3.
By Lemma 5.8 (using the notation of Theorem 5.1) we have that:

$\displaystyle\alpha_{*}((\delta_{1},\delta),2)$
$\displaystyle\leq\max_{p\in\mathcal{S}}\min\Big{\\{}2-(4-2{\delta_{1}})m_{1},\frac{2-(4-2\delta)(m_{1}+m_{2})}{e_{2}}\Big{\\}}=$
$\displaystyle=\max_{p\in\mathcal{S}}\min\Big{\\{}2-(4-2{\delta_{1}})m_{1},\frac{\delta}{e_{2}}\Big{\\}}$

Denote $\alpha_{1}^{\delta}(m_{1})\coloneqq 2-(4-2\delta_{1})m_{1}$. For the
second bound, we will use a variation of the proof of Theorem 5.1. The only
required adjustment to that proof is that the number of $1$-candidate sets for
$V_{M_{1}}$ is at most ${{n^{\delta_{1}}}\choose{m_{1}k}}\leq
n^{\delta_{1}m_{1}k}$. The rest of the proof does not depend on the number of
queries in round $1$, and we get the following bound for this case:

$\displaystyle\alpha_{*}((\delta_{1},\delta),2)$
$\displaystyle\leq\max_{m_{1}}\frac{2(\delta_{1}m_{1}+\delta
m_{2})}{1-4m_{1}m_{2}}=\max_{m_{1}}\frac{2((\frac{3}{2}-\frac{\delta}{4})m_{1}+\delta(\frac{1}{2}-m_{1}))}{1-4m_{1}(\frac{1}{2}-m_{1})}=$
$\displaystyle=\max_{m_{1}}\frac{\delta-(\frac{5}{2}\delta-3)m_{1}}{4m_{1}^{2}-2m_{1}+1}$

Denote
$\alpha_{2}^{\delta}(m_{1})=\frac{\delta-(\frac{5}{2}\delta-3)m_{1}}{4m_{1}^{2}-2m_{1}+1}$.
As we did in the proof of Theorem 5.5, we combine both upper bounds using
Lemma 4.1, while omitting the expression $\frac{\delta}{e_{2}}$. We also
partition the domain of $m_{1}$ by the threshold
$m_{1}^{*}\coloneqq\frac{1-\frac{\delta}{2}}{1+\frac{\delta}{2}}$, and use a
different bound for each case:

$\alpha_{*}((\delta_{1},\delta),2)\leq\max_{m_{1}}\min\\{\alpha_{1}^{\delta}(m_{1}),\alpha_{2}^{\delta}(m_{1})\\}\leq\max\\{\max_{m_{1}\geq
m_{1}^{*}}\alpha_{1}^{\delta}(m_{1}),\max_{m_{1}\leq
m_{1}^{*}}\alpha_{2}^{\delta}(m_{1})\\}$

We start with $\max_{m_{1}\geq m_{1}^{*}}\alpha_{1}^{\delta}(m_{1})$. The
expression $\alpha_{1}^{\delta}(m_{1})$ is maximized when $m_{1}$ is minimal,
i.e., for $m_{1}=m_{1}^{*}$. We get:

$\displaystyle\max_{m_{1}\geq m_{1}^{*}}\alpha_{1}^{\delta}(m_{1})$
$\displaystyle=2-(4-2{\delta_{1}})\frac{1-\frac{\delta}{2}}{1+\frac{\delta}{2}}=2-\Big{(}4-\Big{(}3-\frac{\delta}{2}\Big{)}\Big{)}\frac{1-\frac{\delta}{2}}{1+\frac{\delta}{2}}=$
$\displaystyle=2-\Big{(}1+\frac{\delta}{2}\Big{)}\frac{1-\frac{\delta}{2}}{1+\frac{\delta}{2}}=1+\frac{\delta}{2}$

Regarding $\max_{m_{1}\leq m_{1}^{*}}\alpha_{2}^{\delta}(m_{1})$, we prove in
Appendix B that for $\frac{6}{5}<\delta<2$ and $m_{1}\leq m_{1}^{*}$ the
maximum of $\alpha_{2}^{\delta}(m_{1})$ is obtained when $m_{1}=m_{1}^{*}$,
and in that case $\alpha_{2}^{\delta}(m_{1})=1+\frac{\delta}{2}$. Therefore
$\max_{m_{1}\leq m_{1}^{*}}\alpha_{2}^{\delta}(m_{1})=1+\frac{\delta}{2}$.

We get:

$\alpha_{*}\Big{(}\Big{(}\frac{3}{2}-\frac{\delta}{4},\delta\Big{)},2\Big{)}\leq
1+\frac{\delta}{2}$

∎

Since Algorithm 3 is a $((\delta_{1},\delta),2,1+\frac{\delta}{2})$-algorithm
for $\delta_{1}=\frac{3}{2}-\frac{\delta}{4}$, we have:

######  Corollary 5.10.

For every $\frac{6}{5}<\delta<2$:

$\alpha_{*}\Big{(}\Big{(}\frac{3}{2}-\frac{\delta}{4},\delta\Big{)},2\Big{)}=1+\frac{\delta}{2}$

###  5.2 Three rounds

####  5.2.1 Free edges and vertices

The concept of free edges, introduced in the proof of Theorem 5.1, may be
extended to any number of rounds $l$. Given a prefect matching $M$ of the
returned clique $K$, we partition its edges according to the round in which
they were queried, i.e., $M=\bigcup_{i\leq l}M_{i}$. We denote
$|M_{i}|=m_{i}k$, and include the parameters $m_{1},\dots,m_{l}$ in the
template. We denote by $V_{M_{i}}$ the set of vertices covered by $M_{i}$, and
denote $V_{M}^{i}\coloneqq\bigcup_{j\leq i}V_{M_{j}}$. Intuitively, an edge
$e$ is free for the algorithm, if the algorithm chooses queries such that many
candidates for $K$ will contain $e$, based on previous information that $e$ is
positive. Since $V(K)=\bigcup_{i\leq l}V_{M_{i}}$, and the candidates for the
set $V_{M_{i}}$ are chosen in round $i$, if $e$ has some endpoint $u\in
V_{M_{i}}$ and $e$ was answered positively prior to round $i$, then the
algorithm may choose to include $u$ in $V_{M_{i}}$ based on the information
that $e$ is positive. Therefore, the algorithm will not ’pay’ for the
probability $e$ is positive. This intuition suggests that the free edges are
exactly the edges that were queried on some round $j$, and have an endpoint
$u\in V_{M_{i}}$ where $i>j$.

In order to prove strong upper bounds on $\mathbb{P}(\mathcal{A}_{p}\text{
succeeds})$ we want the probability factor of the bound to be small (i.e.,
$2^{-f_{2}(p){k\choose{2}}}$, see Section 4.2). The free edges will not be
included in the $f_{2}(p){k\choose{2}}$ edges which account for this
probability, so we would like to reduce the number of free edges. One way of
doing this is by a careful choice of the matching $M$ (as will be done in the
proof of Theorem 5.16). Yet another way is as follows. Consider the matching
$M^{i^{*}}\subseteq M$ which contains only matching edges queried up to round
$i^{*}$ for some $1\leq i^{*}\leq l$, i.e., $M^{i^{*}}=\bigcup_{j\leq
i^{*}}M_{j}$. This defines the set $V_{M}^{i^{*}}$ of vertices covered by
$M^{i^{*}}$. In order to reduce the number of free edges, we ignore the
template parameters $m_{i^{*}+1},\dots,m_{l}$, and allow the rest of the
vertices to be any set of vertices, regardless of the rounds in which they
participate in queries (we used a similar approach in the proof of Lemma 4.3).
This means that the family of candidates for this set of vertices is chosen
deterministicly before any answers are given, thus reducing the number of free
edges. We denote this set of vertices by $V_{free}^{i^{*}}$, and refer to them
as ’free’ vertices for the algorithm, because they are not restricted to
participate in any matching. Hence, the family of their candidates will be
larger (we will choose single vertices out of $n$ vertices, and not pairs of
vertices out of $n^{\delta}$ edges). Therefore, as we decrease the value of
$i^{*}$, the number of free edges decreases and the number of free vertices
increases, which is a trade-off that we may use in order to prove different
upper bounds on $\mathbb{P}(\mathcal{A}_{p}\text{ succeeds})$.

Determine some $1\leq i^{*}\leq l$. Given the partition
$V(K)=V_{M}^{i^{*}}\cup V_{free}^{i^{*}}=\bigcup_{i\leq i^{*}}V_{M_{i}}\cup
V_{free}^{i^{*}}$, for every $1\leq i\leq i^{*}$ we denote by
$e_{i}{k\choose{2}}$ the number of edges queried on round $i$ that have both
endpoints in $V_{M}^{i}\cup V_{free}^{i^{*}}$. The parameters $e_{i}$,
together with the parameters $m_{i}$, will be a part of the template. We
denote the number of free vertices by $|V_{free}^{i^{*}}|=v_{free}^{i^{*}}k$.
We have that:

$v_{free}^{i^{*}}=2\sum_{i^{*}<i\leq l}m_{i}$

Similar to the proof of Theorem 5.1, we will define candidate and feasible
sets for each round number $i\leq i^{*}$, and prove an upper bound on the
expected number of feasible sets. The definition will be recursive since
candidate sets contain feasible sets and vice versa. We start with the
definition of $0$-candidate sets which are the candidates for the set of free
vertices. A $0$-candidate set $a$ satisfies the following:

  * •

$|a|=v_{free}^{i^{*}}k$.

Next, we define $1$-candidate sets (which is the base case of the recursive
definition). A $1$-candidate is a set $a$ which may be partitioned into
$a=b\sqcup c$ such that:

  * •

$b$ is a $0$-candidate.

  * •

$b\cap c=\emptyset$.

  * •

$|c|=2m_{1}k$.

  * •

$Q_{1}$ induced on $c$ has a perfect matching.

  * •

$Q_{1}$ induced on $a$ has $e_{1}{k\choose{2}}$ edges.

$a$ will be called $1$-feasible if:

  * •

$a$ is a $1$-candidate.

  * •

All $e_{1}{k\choose{2}}$ queries of $Q_{1}$ induced on $a$ were positive.

For $2\leq i\leq i^{*}$, a set $a$ will be an $i$-candidate if it may be
partitioned into disjoint sets $a=b\sqcup c$ which satisfy the following:

  * •

$b$ is $i-1$-feasible.

  * •

$b\cap c=\emptyset$.

  * •

$|c|=2m_{i}k$.

  * •

$Q_{i}$ induced on $c$ has a perfect matching.

  * •

$Q_{i}$ induced on $a$ has $e_{i}{k\choose{2}}$ edges.

Note that in a general matching $M$, which is not required to be a maximum
matching at any stage, we do not require $c$ to be edge-free prior to round
$i$ (as opposed to the definition of a candidate pair in the proof of Theorem
5.1). For $2\leq i\leq i^{*}$, a set $a$ will be $i$-feasible if:

  * •

$a$ is an $i$-candidate.

  * •

All $e_{i}{k\choose{2}}$ queries of $Q_{i}$ induced on $a$ were positive.

Denote by $F^{i}$ the number of $i$-feasible sets. Then we have the following
lemma:

######  Lemma 5.11.

For every $1\leq i^{*}\leq l$ and $1\leq i\leq i^{*}$, assuming
$q_{i}=n^{\delta_{i}}$, we have:

$\operatorname*{\mathbb{E}}_{1,\dots,i}[F^{i}]\leq
n^{\Big{[}v_{free}^{i^{*}}+\sum_{j\leq i}\delta_{j}m_{j}\Big{]}k}\cdot
2^{-\sum_{j\leq i}e_{j}{k\choose{2}}}$

The subscript indicates the rounds over which the expectation is taken.

###### Proof.

The proof is by induction on the round number $i$. For $i=1$, the number of
$0$-candidates is at most ${{n}\choose{v_{free}^{i^{*}}k}}\leq
n^{v_{free}^{i^{*}}k}$, and the number of $1$-candidates is at most
$n^{v_{free}^{i^{*}}k}\cdot{{n^{\delta}}\choose{m_{1}k}}\leq
n^{(v_{free}^{i^{*}}+\delta_{1}m_{1})k}$. The family of $1$-candidates is
determined deterministically by the algorithm before it receives answers.
Hence, each candidate is $1$-feasible with probability
$2^{-e_{1}{k\choose{2}}}$, so we get the desired bound:

$\operatorname*{\mathbb{E}}_{1}[F^{1}]\leq
n^{\Big{[}v_{free}^{i^{*}}+\delta_{1}m_{1}\Big{]}k}\cdot
2^{-e_{1}{k\choose{2}}}$

Assuming the claim is correct for some $i-1$, we wish to prove it for $i$. An
$i$-candidate $a$ is the union of two sets $b\cup c$ where $b$ is an
$i-1$-feasible set, and $c$ is a set with a perfect matching in $Q_{i}$. After
round $i$ there are at most $F^{i-1}\cdot n^{\delta_{i}m_{i}k}$ such pairs,
and the probability such a pair induces an $i$-feasible set is at most
$2^{-e_{i}{k\choose{2}}}$ independently of the answers up to round $i-1$
(since this probability comes from round $i$ answers). By linearity of
expectation we get:

$\displaystyle\operatorname*{\mathbb{E}}_{1,\dots,i}[F^{i}]$
$\displaystyle=\operatorname*{\mathbb{E}}_{1,\dots,i-1}[\operatorname*{\mathbb{E}}_{i}[F^{i}]]\leq\operatorname*{\mathbb{E}}_{1,\dots,i-1}[F^{i-1}\cdot
n^{\delta_{i}m_{i}k}\cdot 2^{-e_{i}{k\choose{2}}}]=$
$\displaystyle=n^{\delta_{i}m_{i}k}\cdot
2^{-e_{i}{k\choose{2}}}\cdot\operatorname*{\mathbb{E}}_{1,\dots,i-1}[F^{i-1}]\leq
n^{\Big{[}v_{free}^{i^{*}}+\sum_{j\leq i}\delta_{j}m_{j}\Big{]}k}\cdot
2^{-\sum_{j\leq i}e_{j}{k\choose{2}}}$

∎

For $i=i^{*}$ we get an upper bound on
$\operatorname*{\mathbb{E}}_{1,\dots,i^{*}}[F^{i^{*}}]$, and since the clique
$K$ returned by the algorithm must be an $i^{*}$-feasible set, we deduce a
bound on the probability such a clique exists.

As we defined in the intuitive explanation, an edge $e$ queried on round $i$
for which $i<i^{*}$, will be a free edge if it has an endpoint $u$ in
$V_{M_{j}}$ where $i<j\leq i^{*}$. This happens if and only if the edge is not
contained in $V_{M}^{i}$, i.e., it is not one of the $e_{i}{k\choose{2}}$
edges accounted for the probability factor of the bound in Lemma 5.11.
Therefore, denoting by $e_{free}^{i^{*}}{k\choose{2}}$ the number of free
edges, we have that:

$e_{free}^{i^{*}}=1-\sum_{1\leq i\leq i^{*}}e_{i}$

Using Lemma 4.1 with the template
$m_{1},\dots,m_{i^{*}},e_{1},\dots,e_{i^{*}}$, and the $l$ bounds proved in
Lemma 5.11 (i.e., for any $1\leq i^{*}\leq l$) we get the following corollary:

######  Corollary 5.12.

$\alpha_{*}((\delta_{1},\dots,\delta_{l}),l)\leq\max_{p\in\mathcal{S}}\min_{1\leq
i^{*}\leq l}\frac{2\Big{[}v_{free}^{i^{*}}+\sum_{i\leq
i^{*}}\delta_{i}m_{i}\Big{]}}{1-e_{free}^{i^{*}}}$

####  5.2.2 Three rounds analysis

In the following sections we analyze the case of three rounds algorithms for
any $1\leq\delta<2$, and prove upper bounds on $\alpha_{*}(\delta,3)$ using
Corollary 5.12. We introduce a specific perfect matching $M$ of $K$, and prove
upper bounds on the number of free edges corresponding to it. $M$ partitions
$V(K)$ into three sets $V_{M_{1}},V_{M_{2}},V_{M_{3}}$, where
$|V_{M_{i}}|=2m_{i}k$, and we have $m_{1}+m_{2}+m_{3}=\frac{1}{2}$. We will
use the following notation: $M_{ij}=M_{i}\cup M_{j}$ and
$V_{M_{ij}}=V_{M_{i}}\cup V_{M_{j}}$. $M$ is defined as the perfect matching
for which $m_{1}+m_{2}$ is maximal, breaking ties by maximizing the value of
$m_{1}$ (and then breaking ties arbitrarily). We consider $m_{1},m_{2},m_{3}$
of the matching $M$ defined this way, as parameters in the template. The
reason for choosing the matching $M$ this way is that we get a good upper
bound on the total number of free edges. For example, we have the following
upper bound:

######  Lemma 5.13.

$e_{free}^{3}\leq\frac{1}{2}$

###### Proof.

Let $\\{u,v\\},\\{w,z\\}$ be two edges in the matching $M$. Between the
vertices $u,v,w,z$ there are four non-matching edges (i.e., not in $M$) -
$\\{u,w\\}$, $\\{u,z\\}$, $\\{v,w\\}$, $\\{v,z\\}$, which are adjacent to both
matching edges. For any non-matching edge $e$, there is exactly one pair of
distinct matching edges adjacent to $e$. Therefore, going over all pairs of
matching edges, and the four edges adjacent to them, we count each non-
matching edge exactly once. Since the fraction of matching edges is
negligible, it is enough to prove that for any pair of matching edges, at most
two edges out of $\\{u,w\\}$, $\\{u,z\\}$, $\\{v,w\\}$, $\\{v,z\\}$ are free.

We prove that at most one of the edges $\\{u,w\\},\\{v,z\\}$ is free (the
proof for the other pair is equivalent). Assume for the sake of contradiction
that both edges are free. We will introduce a matching $\bar{M}$ that
contradicts the maximality properties of $M$. There are no free edges queried
in round $3$, so the edges are in $Q_{1}\cup Q_{2}$. We divide into the
following cases:

  * •

Both $\\{u,w\\},\\{v,z\\}$ were queried in round 1. Suppose w.l.o.g that
$\\{u,w\\}$ is free because $u$ is covered by $M$ after $\\{u,w\\}$ is
answered, i.e., $\\{u,v\\}\in M_{23}$, so $\\{u,v\\}\in Q_{2}\cup Q_{3}$. We
define a matching $\bar{M}$ which is equal to $M$ except on the vertices
$u,v,w,z$. Instead of the edges $\\{u,v\\},\\{w,z\\}$, $\bar{M}$ contains
$\\{u,w\\},\\{v,z\\}$. Denote by $\bar{m}_{1},\bar{m}_{2},\bar{m}_{3}$ the
relative parts of the partition of $\bar{M}$ to rounds. Since
$\\{u,w\\},\\{v,z\\}\in Q_{1}$ and $\\{u,v\\}\in Q_{2}\cup Q_{3}$ we have:

$\displaystyle\bar{m}_{1}+\bar{m}_{2}$ $\displaystyle\geq m_{1}+m_{2}$
$\displaystyle\bar{m}_{1}$ $\displaystyle>m_{1}$

contradicting the maximality of $M$ (which maximizes $m_{1}+m_{2}$, breaking
ties by maximizing $m_{1}$).

  * •

At least one edge was queried on round 2. Suppose w.l.o.g that $\\{u,w\\}\in
Q_{2}$ and it is free because $u$ is covered by $M$ after $\\{u,w\\}$ is
answered, i.e., $\\{u,v\\}\in M_{3}$, so $\\{u,v\\}\in Q_{3}$. We use the same
matching $\bar{M}$ as in the previous case. Since $\\{u,w\\},\\{v,z\\}\in
Q_{1}\cup Q_{2}$, and $\\{u,v\\}\in Q_{3}$ we have:

$\bar{m}_{1}+\bar{m}_{2}>m_{1}+m_{2}$

contradicting the maximality of $M$.

Hence, at most one edge of each pair is free and
$e_{free}^{3}\leq\frac{1}{2}$. ∎

The edges in $M_{12}$ form a maximum matching in $K_{2}$ (since $m_{1}+m_{2}$
is maximal), so we can look at the Gallai-Edmonds decomposition after round
$2$. It is composed of the sets $C,S,R$, or the specific matching
representation - $C^{*+},C^{*-},S,D$ where $C^{*}=C^{*+}\cup C^{*+}$ (as
defined in Section 4.3). We partition further according to the partition of
$V(K)$ into $V_{M_{1}}\cup V_{M_{2}}\cup V_{M_{3}}$. We get the following sets
(see Figure 3):

  * •

$S$ decomposes to $S_{1}\cup S_{2}$ where $S_{i}=S\cap V_{M_{i}}$.

  * •

$C^{*+}$ decomposes to the sets $C^{*+}_{1},C^{*+}_{2}$ which are matched to
$S_{1},S_{2}$ respectively.

  * •

$C^{*-}=V_{M_{3}}$. In particular, $C^{*-}$ contains all isolated vertices in
$K_{2}$.

  * •

The set $D$ decomposes to $D_{1}\cup D_{2}$ where $D_{i}=D\cap V_{M_{i}}$.

Figure 3: Specific matching decomposition of $K$. The arrows indicate the
partition of $M$ according to the rounds and the decomposition.

The edges in $M_{2}$ form a maximum matching in $V_{M_{23}}$ after round $2$,
because if there was a larger matching we could add $M_{1}$ and get a matching
larger than $M_{12}$ in $K_{2}$. Therefore we can look at the GED of
$V_{M_{23}}$, and the specific matching decomposition. We denote the relevant
sets by $\tilde{C},\tilde{S},\tilde{R}$. We have that $\tilde{C}\subseteq
C\cap V_{M_{23}}$ because for any $v\in\tilde{C}$ there is a maximum matching
in $V_{M_{23}}$ in which $v$ does not participate. If we add $M_{1}$ to this
matching, we get a maximum matching in $K$ in which $v$ does not participate,
so $v\in C$. Therefore we have that $\tilde{S}=N(\tilde{C})\subseteq N(C)=S$,
so $\tilde{S}\subseteq S\cap V_{M_{23}}=S_{2}$, and also $R\cap
V_{M_{23}}\subseteq\tilde{R}$. Looking at the specific matching decomposition
$\tilde{C}^{*}=\tilde{C}^{*+}\cup\tilde{C}^{*-},\tilde{S},\tilde{D}$, we have
$\tilde{C}^{*-}=V_{M_{3}}$ and $\tilde{S}$ is matched to $\tilde{C}^{*+}$.
Since $\tilde{S}\subseteq S_{2}$ and $\tilde{C}^{*}\subseteq C^{*}\cap
V_{M_{23}}$ we get $D_{2}\subseteq\tilde{D}$, so we can write $\tilde{D}$ as
$D_{2}\cup\tilde{D_{2}}$ (see Figure 4).

For each vertex $v\in V(K)$, and $K^{\prime}\subseteq K$ we denote the degree
of $v$ in the graph $Q_{i}$ induced on $V(K^{\prime})$ by
$deg_{i}^{K^{\prime}}(v)$.

######  Lemma 5.14.

For every $v\in\tilde{C}$, $deg_{1}^{V_{M_{23}}}(v)=0$.

###### Proof.

First, suppose for contradiction that for some $v\in V_{M_{3}}$,
$deg_{1}^{V_{M_{23}}}(v)\geq 1$. All edges within $\tilde{C}^{*}$ are in
$Q_{3}$, so there must be $u\in\tilde{S}\cup\tilde{D}$ s.t. $\\{u,v\\}\in
Q_{1}$. Let $u^{\prime},v^{\prime}$ be the vertices matched to $u,v$. We have
$\\{u,u^{\prime}\\}\in Q_{2}$ and $\\{v,v^{\prime}\\}\in Q_{3}$. Hence, by
replacing the matching edges with $\\{u,v\\}$ and
$\\{u^{\prime},v^{\prime}\\}$ in the original full matching of $K$, we get a
matching in which $m_{1}+m_{2}$ is not smaller, but $m_{1}$ is larger, which
is a contradiction.

Now suppose there is $v\in\tilde{C}$ such that $deg_{1}^{V_{M_{23}}}(v)\geq
1$. This means there is $u\in V_{M_{23}}$ s.t. $\\{u,v\\}\in Q_{1}$.
$v\in\tilde{C}$ so by definition there is maximum matching of $V_{M_{23}}$ in
which $v$ is not matched. In this new matching, which might consist of a
different decomposition - $\tilde{C}^{*}_{new},\tilde{S},\tilde{D}_{new}$, it
must be that $u\notin\tilde{C}^{*}_{new}$, because there are only $Q_{3}$
edges in $\tilde{C}^{*}_{new}$. So $u\in\tilde{S}\cup\tilde{D}_{new}$. Now we
can apply the previous argument about $v\in V_{M_{3}}$ but using the new
matching and get a contradiction to $\\{u,v\\}\in Q_{1}$. ∎

Another parameter of the decomposition that we will use in the template, is
the size of the maximum $Q_{1}$ matching in $V_{M_{23}}$, denoted
$M_{1}^{\prime}$ (see Figure 4). The set of vertices covered by this matching
will be denoted $V_{M_{1}^{\prime}}$, and its size will be
$|V_{M_{1}^{\prime}}|=2m_{1}^{\prime}k$. Note that by Lemma 5.14,
$V_{M_{1}^{\prime}}\subseteq\tilde{S}\cup\tilde{R}$.

Figure 4: Specific matching decomposition of $V_{M_{23}}$ and $K$, including
$M_{1}^{\prime}$.

We will use the notation of $E_{i}(A,B)$ and $E_{i}(A)$ as the number of
$Q_{i}$ edges between $A$ and $B$ or within $A$. If no index is mentioned it
means all edges between the sets.

The decomposition described is rich enough to extract strong bounds on the
number of free edges. In order to do so, we replace the template parameters
$m_{1},m_{2}$ by the parameters $s_{1},d_{1},\tilde{s_{2}},\tilde{d_{2}}$
where $|S_{1}|=s_{1}k$, $|D_{1}|=2d_{1}k$, $|\tilde{S}|=\tilde{s_{2}}k$,
$|\tilde{D}|=2\tilde{d_{2}}k$. Note that $m_{1}=s_{1}+d_{1}$ and
$m_{2}=\tilde{s_{2}}+\tilde{d_{2}}$. In the three rounds setting, free edges
may be in either $Q_{1}$ or $Q_{2}$, and we start with the analysis of round 2
free edges, which is simpler (see Figure 5 for a summary of all free edges in
$K$).

##### Round 2 free edges

Any free edge of $Q_{2}$ must have an endpoint in $V_{M_{3}}$, which equals
$C^{*-}$ in the decomposition. Looking at $K_{2}$, $C^{*-}$ is an independent
set and has all neighbors in $S\cup D$. Moreover, any $v\in D$ satisfies
$\deg_{2}^{C^{*-}}(v)\leq 1$ (because the vertices of $C^{*-}$ belong to
different connected components in the G.E.D). Hence, $E_{2}(C^{*-},D)$ is at
most linear in $k$, and so neglecting low order terms we may assume the number
of free edges of $Q_{2}$ is bounded by $E_{2}(C^{*-},S)$. This can be further
reduced by looking at $M_{2}$ as a maximal matching of $V_{M_{23}}$ after
round 2. All $Q_{2}$ edges in $V_{M_{23}}$ with an endpoint in
$C^{*-}=\tilde{C}^{*-}$ have the other endpoint in $\tilde{S}\subseteq S_{2}$
(up to a linear in $k$ amount). Hence, the number of such free edges is
bounded by

$E_{2}(C^{*-},S_{1}\cup\tilde{S})\leq 2m_{3}k\cdot(s_{1}+\tilde{s_{2}})k\simeq
4m_{3}(s_{1}+\tilde{s_{2}}){k\choose{2}}$

##### Round 1 free edges

Free edges of $Q_{1}$ must have an endpoint in either $V_{M_{3}}$ or
$V_{M_{2}}$. A free edge $e$ that has an endpoint in $V_{M_{3}}$, must have
the other endpoint in $V_{M_{1}}$ (by Lemma 5.14). So up to low order terms,
the number of such edges is at most

$E_{1}(C^{*-},S_{1})\leq 2m_{3}k\cdot s_{1}k\simeq 4m_{3}s_{1}{k\choose{2}}$

Note that when we bound both $Q_{1}$ and $Q_{2}$ free edges, the $Q_{1}$ bound
is redundant because we have:

$E_{2}(C^{*-},S_{1}\cup\tilde{S})+E_{1}(C^{*-},S_{1})\leq
E(C^{*-},S_{1}\cup\tilde{S})\leq 4m_{3}(s_{1}+\tilde{s_{2}}){k\choose{2}}$

Assuming a free edge $e$ has no endpoints in $V_{M_{3}}$, it must have an
endpoint in $V_{M_{2}}$. For the case where the other endpoint is in
$V_{M_{1}}$ we have to bound $E_{1}(V_{M_{1}},V_{M_{2}})$. For any pair of
matching edges $(e_{1},e_{2})\in M_{1}\times M_{2}$, there are four non-
matching edges between the four vertices incident to $e_{1},e_{2}$, and at
most two of those edges are in $Q_{1}$. Otherwise, we could enlarge $m_{1}$ by
using two edges of $Q_{1}$ instead of $(e_{1},e_{2})$. Going over all pairs
$(e_{1},e_{2})\in M_{1}\times M_{2}$ and the edges between them, we count all
edges in $E(V_{M_{1}},V_{M_{2}})$ exactly once, so at most half of them are in
$Q_{1}$. Hence:

$E_{1}(V_{M_{1}},V_{M_{2}})\leq\frac{1}{2}\cdot 2m_{1}k\cdot 2m_{2}k\simeq
4(s_{1}+d_{1})(\tilde{s_{2}}+\tilde{d_{2}}){k\choose{2}}$

For the last case, where both endpoints are in $V_{M_{2}}$, we have to bound
$E_{1}(V_{M_{2}})$. By Lemma 5.14, $Q_{1}$ edges inside $V_{M_{2}}$ can be
only in $\tilde{S}\cup\tilde{D}$. We partition $\tilde{S}\cup\tilde{D}$ into
$V_{M_{1}^{\prime}}$ and
$[\tilde{S}\cup\tilde{D}]\setminus{V_{M_{1}^{\prime}}}$ (
$|[\tilde{S}\cup\tilde{D}]\setminus{V_{M_{1}^{\prime}}}|=(\tilde{s_{2}}+2\tilde{d_{2}}-2m_{1}^{\prime})k$).
Since $M_{1}^{\prime}$ is the maximum $Q_{1}$ matching in $V_{M_{2}}$, there
are no $Q_{1}$ edges within
$[\tilde{S}\cup\tilde{D}]\setminus{V_{M_{1}^{\prime}}}$, and at most half the
edges between the two sets are from $Q_{1}$. This is because if we look at the
GED of $Q_{1}$ in $V_{M_{2}}$, at most one endpoint of each maximum matching
edge can be connected to an unmatched vertex. Therefore there are at most
$\frac{1}{2}\cdot
2m_{1}^{\prime}k\cdot(\tilde{s_{2}}+2\tilde{d_{2}}-2m_{1}^{\prime})k\simeq
2m_{1}^{\prime}(\tilde{s_{2}}+2\tilde{d_{2}}-2m_{1}^{\prime}){k\choose{2}}$
such edges. The rest of the edges are those within $V_{M_{1}^{\prime}}$. There
are ${{2m_{1}^{\prime}k}\choose{2}}\simeq 4{m^{\prime}_{1}}^{2}{k\choose{2}}$
such edges, all may be in $Q_{1}$. We get

$E_{1}(V_{M_{2}})\leq[4{m^{\prime}_{1}}^{2}+2m_{1}^{\prime}(\tilde{s_{2}}+2\tilde{d_{2}}-2m_{1}^{\prime})]{k\choose{2}}=2m_{1}^{\prime}(\tilde{s_{2}}+2\tilde{d_{2}}){k\choose{2}}$

Figure 5: Free edges in $K$

######  Corollary 5.15.

We have the following bounds on $e_{free}^{2},e_{free}^{3}$:

$e_{free}^{2}\leq
2[2(s_{1}+d_{1})(\tilde{s_{2}}+\tilde{d_{2}})+m_{1}^{\prime}(\tilde{s_{2}}+2\tilde{d_{2}})]$
$e_{free}^{3}\leq
2[2m_{3}(s_{1}+\tilde{s_{2}})+2(s_{1}+d_{1})(\tilde{s_{2}}+\tilde{d_{2}})+m_{1}^{\prime}(\tilde{s_{2}}+2\tilde{d_{2}})]$

####  5.2.3 Tight bound for three rounds, restricted first rounds

Algorithm 4 (see Section 4.1) provides the lower bound
$\alpha_{*}(\delta,3)\geq 1+\frac{\delta}{2}$ for every $1\leq\delta<2$. As we
did in Section 5.1.3, we will show that Algorithm 4 is optimal among all
algorithms which query the same number of queries per round as Algorithm 4
does. Algorithm 4 queries roughly $n^{1-\frac{\delta}{2}}$ pairs in round 1,
$\theta(n)$ pairs in round 2, and $n^{\delta}$ pairs in round 3. We therefore
have $(\delta_{1},\delta_{2},\delta_{3})=(1-\frac{\delta}{2},1,\delta)$. We
prove the following theorem:

######  Theorem 5.16.

For every $1\leq\delta<2$:

$\alpha_{*}((1-\frac{\delta}{2},1,\delta),3)\leq 1+\frac{\delta}{2}$

###### Proof.

By Corollary 5.12 and Lemma 4.4, we get the following upper bound:

$\alpha_{*}((1-\frac{\delta}{2},1,\delta),3)\leq\max_{p\in\mathcal{S}_{I_{l-1}\leq\delta\log
n}}\min\\{\alpha_{1},\alpha_{2},\alpha_{3}\\}$

where $\alpha_{i^{*}}$ is the upper bound corresponding to round $i^{*}$. We
use the upper bounds proved in Corollary 5.15 on the number of free edges in
order to upper bound $\alpha_{2},\alpha_{3}$.

  * •

For $i^{*}=3$, i.e., there are no free vertices, we get:

$\displaystyle\alpha_{3}$
$\displaystyle=\frac{2\big{[}(1-\frac{\delta}{2})m_{1}+m_{2}+\delta
m_{3}\big{]}}{1-e_{free}^{3}}=$
$\displaystyle=\frac{2\big{[}(1-\frac{\delta}{2})m_{1}+m_{2}+\delta(\frac{1}{2}-m_{1}-m_{2})\big{]}}{1-e_{free}^{3}}=$
$\displaystyle=\frac{\delta-(3\delta-2)m_{1}-(2\delta-2)m_{2}}{1-e_{free}^{3}}\leq$
$\displaystyle\leq\frac{\delta-(3\delta-2)(s_{1}+d_{1})-(2\delta-2)(\tilde{s_{2}}+\tilde{d_{2}})}{1-2[2m_{3}(s_{1}+\tilde{s_{2}})+2(s_{1}+d_{1})(\tilde{s_{2}}+\tilde{d_{2}})+m_{1}^{\prime}(\tilde{s_{2}}+2\tilde{d_{2}})]}$

  * •

For $i^{*}=2$, i.e., the free vertices are those matched in round 3, we get:

$\displaystyle\alpha_{2}$
$\displaystyle=\frac{2\big{[}2m_{3}+(1-\frac{\delta}{2})m_{1}+m_{2}\big{]}}{1-e_{free}^{2}}=$
$\displaystyle=\frac{2\big{[}2(\frac{1}{2}-m_{1}-m_{2})+(1-\frac{\delta}{2})m_{1}+m_{2}\big{]}}{1-e_{free}^{2}}\leq$
$\displaystyle\leq\frac{2-(2+\delta)(s_{1}+d_{1})-2(\tilde{s_{2}}+\tilde{d_{2}})}{1-2[2(s_{1}+d_{1})(\tilde{s_{2}}+\tilde{d_{2}})+m_{1}^{\prime}(\tilde{s_{2}}+2\tilde{d_{2}})]}$

  * •

For $i^{*}=1$, i.e., the free vertices are those matched in rounds 2,3, and
there are no free edges. We get:

$\displaystyle\alpha_{1}$
$\displaystyle=2(1-(2-\delta_{1})m_{1})=2-(2+\delta)m_{1}$

This bound is stronger when $m_{1}$ is larger. $M_{1}$ is not a maximal
matching in $K_{1}$, so using the matching $M$ in this case is not optimal.
Instead, we look at $M_{1}\cup M_{1}^{\prime}$ which is a maximal matching in
$K_{1}$, of size $(m_{1}+m_{1}^{\prime})k$. We get the following stronger
bound:

$\displaystyle\alpha_{1}$
$\displaystyle=2-(2+\delta)(m_{1}+m_{1}^{\prime})=2-(2+\delta)(s_{1}+d_{1}+m_{1}^{\prime})$

By Lemma 4.4, the signatures set is restricted to the signatures in which
$I_{l-1}\leq\delta\log n$. Since the set
$C_{1}^{*+}\cup\tilde{C}^{*+}\cup\tilde{C}^{*-}$ is an independent set in
$K_{2}$, we have $(s_{1}+\tilde{s_{2}}+2m_{3})k\leq I_{l-1}\leq\delta\log n$
and therefore: $\alpha\leq\frac{\delta}{s_{1}+\tilde{s_{2}}+2m_{3}}$. Using
the lower bound $\alpha_{*}((1-\frac{\delta}{2},1,\delta),3)\geq
1+\frac{\delta}{2}$ implied by Algorithm 4, we may assume that $\alpha\geq
1+\frac{\delta}{2}$. We get:

$\displaystyle
1+\frac{\delta}{2}\leq\frac{\delta}{s_{1}+\tilde{s_{2}}+2m_{3}}$
$\displaystyle
s_{1}+\tilde{s_{2}}+2(\frac{1}{2}-(s_{1}+d_{1}+\tilde{s_{2}}+\tilde{d_{2}}))\leq\frac{2\delta}{2+\delta}$
$\Rightarrow
s_{1}+2d_{1}+\tilde{s_{2}}+2\tilde{d_{2}}\geq\frac{2-\delta}{2+\delta}$
($\ast$)

We now wish to find the signature which satisfies the constraint ($\ast$ ‣
5.2.3) and maximizes $\min\\{\alpha_{1},\alpha_{2},\alpha_{3}\\}$. We start
with the value of $d_{1}$, and prove the following lemma:

######  Lemma 5.17.

The maximum of $\min\\{\alpha_{1},\alpha_{2},\alpha_{3}\\}$ under the
following relaxation of ($\ast$ ‣ 5.2.3):

$2s_{1}+2d_{1}+\tilde{s_{2}}+2\tilde{d_{2}}\geq\frac{2-\delta}{2+\delta}$
($\ast\ast$)

is obtained when $d_{1}=0$.

###### Proof.

Suppose the maximum of $\min\\{\alpha_{1},\alpha_{2},\alpha_{3}\\}$ is
obtained for some signature
$(s_{1},d_{1},\tilde{s_{2}},\tilde{d_{2}},m_{1}^{\prime})=(a,b,c,d,e)$ where
$b>0$. We claim that for
$(s_{1},d_{1},\tilde{s_{2}},\tilde{d_{2}},m_{1}^{\prime})=(a+b,0,c,d,e)$,
$\min\\{\alpha_{1},\alpha_{2},\alpha_{3}\\}$ is not smaller and ($\ast\ast$ ‣
5.17) is satisfied. Note that $m_{1}=s_{1}+d_{1}$ is the same in both
signatures. Moreover, $\alpha_{1},\alpha_{2}$ and the constraint ($\ast\ast$ ‣
5.17) may be expressed with $m_{1}$ instead of $s_{1}$ and $d_{1}$ (so they
are the same for both signatures). Regarding $\alpha_{3}$, it is larger when
$(s_{1},d_{1})=(a+b,0)$ than when $(s_{1},d_{1})=(a,b)$. Hence,
$\min\\{\alpha_{1},\alpha_{2},\alpha_{3}\\}$ is not smaller using the
signature $(a+b,0,c,d,e)$, and the constraint ($\ast\ast$ ‣ 5.17) is
satisfied. (Note that this may not hold for the original constraint ($\ast$ ‣
5.2.3).) ∎

According to Lemma 5.17 we assume $d_{1}=0$, and maximize
$\min\\{\alpha_{1},\alpha_{2},\alpha_{3}\\}$ under the relaxed constraint
($\ast\ast$ ‣ 5.17). We can simplify the bounds further by using the lower
bound $\alpha_{*}((1-\frac{\delta}{2},1,\delta),3)\geq 1+\frac{\delta}{2}$
implied by Algorithm 4. Any signature $p$ for which the expression that bounds
$\alpha_{1}$ is smaller than $1+\frac{\delta}{2}$, is necessarily not the
signature which maximizes the objective. Hence, we may assume that:

$\displaystyle 1+\frac{\delta}{2}\leq 2-(2+\delta)(s_{1}+m_{1}^{\prime})$
$\displaystyle\Rightarrow$ $\displaystyle
m_{1}^{\prime}\leq\frac{1-\frac{\delta}{2}}{2+\delta}-s_{1}$

Both expressions that bound $\alpha_{2},\alpha_{3}$ are larger when
$m_{1}^{\prime}$ is larger. Therefore the bounds hold also when we assume
$m_{1}^{\prime}$ is maximal. We also have that
$m_{3}=\frac{1}{2}-(s_{1}+\tilde{s_{2}}+\tilde{d_{2}})$. We get the bound
$\alpha_{*}((1-\frac{\delta}{2},1,\delta),3)\leq\max_{s_{1},\tilde{s_{2}},\tilde{d_{2}}}\min\\{\alpha_{2},\alpha_{3}\\}$
when:

$\displaystyle\alpha_{3}\leq\frac{\delta-(3\delta-2)s_{1}-(2\delta-2)(\tilde{s_{2}}+\tilde{d_{2}})}{1-2[2(\frac{1}{2}-(s_{1}+\tilde{s_{2}}+\tilde{d_{2}}))(s_{1}+\tilde{s_{2}})+2s_{1}(\tilde{s_{2}}+\tilde{d_{2}})+\big{[}\frac{1-\frac{\delta}{2}}{2+\delta}-s_{1}\big{]}(\tilde{s_{2}}+2\tilde{d_{2}})]}$
$\displaystyle\alpha_{2}\leq\frac{2-(2+\delta)s_{1}-2(\tilde{s_{2}}+\tilde{d_{2}})}{1-2[2s_{1}(\tilde{s_{2}}+\tilde{d_{2}})+\big{[}\frac{1-\frac{\delta}{2}}{2+\delta}-s_{1}\big{]}(\tilde{s_{2}}+2\tilde{d_{2}})]}$

Under the constraints:

$\displaystyle s_{1},\tilde{s_{2}},\tilde{d_{2}}\geq 0$ $\displaystyle
s_{1}+\tilde{s_{2}}+\tilde{d_{2}}\leq\frac{1}{2}$ $\displaystyle
2s_{1}+\tilde{s_{2}}+2\tilde{d_{2}}\geq\frac{2-\delta}{2+\delta}$

We refer the reader to Appendix C for a description of the optimization method
we used to solve this problem. The signature which maximizes the objective is
as follows: $s_{1}=0$, $\tilde{s_{2}}=\frac{2-\delta}{2+\delta}$,
$\tilde{d_{2}}=0$. For this signature, which is equal to the one used in
Algorithm 4, the value of $\min(\alpha_{2},\alpha_{3})$ is
$1+\frac{\delta}{2}$. Hence, for every $1\leq\delta<2$:

$\alpha_{*}((1-\frac{\delta}{2},1,\delta),3)\leq 1+\frac{\delta}{2}$

∎

Since Algorithm 4 is a
$((1-\frac{\delta}{2},1,\delta),3,1+\frac{\delta}{2})$-algorithm, we have:

######  Corollary 5.18.

For every $1\leq\delta<2$:

$\alpha_{*}((1-\frac{\delta}{2},1,\delta),3)=1+\frac{\delta}{2}$

####  5.2.4 Bound for three rounds, $q_{1}=q_{2}=q_{3}$

In this section we give upper bounds on $\alpha_{*}(\delta,3)$ (i.e., when no
round is restricted) for several values of $\delta$. The bounds are achieved
using Corollary 5.12, Lemma 4.4, and Corollary 5.15.

$\alpha_{*}(\delta,3)\leq\max_{p\in\mathcal{S}_{I_{l-1}\leq\delta\log
n}}\min\\{\alpha_{1},\alpha_{2},\alpha_{3}\\}$

Where $\alpha_{i^{*}}$ is the upper bound corresponding to round $i^{*}$.

  * •

For $i^{*}=3$, i.e., there are no free vertices, we get:

$\displaystyle\alpha_{3}$ $\displaystyle=\frac{2\big{[}\delta m_{1}+\delta
m_{2}+\delta m_{3}\big{]}}{1-e_{free}^{3}}\leq$
$\displaystyle\leq\frac{\delta}{1-2[2m_{3}(s_{1}+\tilde{s_{2}})+2(s_{1}+d_{1})(\tilde{s_{2}}+\tilde{d_{2}})+m_{1}^{\prime}(\tilde{s_{2}}+2\tilde{d_{2}})]}$

  * •

For $i^{*}=2$, i.e., the free vertices are those matched in round 3, we get:

$\displaystyle\alpha_{2}$ $\displaystyle=\frac{2\big{[}2m_{3}+\delta
m_{1}+\delta m_{2}\big{]}}{1-e_{free}^{2}}=$
$\displaystyle=\frac{2\big{[}2(\frac{1}{2}-m_{1}-m_{2})+\delta m_{1}+\delta
m_{2}\big{]}}{1-e_{free}^{2}}\leq$
$\displaystyle\leq\frac{2-(4-2\delta)(s_{1}+d_{1}+\tilde{s_{2}}+\tilde{d_{2}})}{1-2[2(s_{1}+d_{1})(\tilde{s_{2}}+\tilde{d_{2}})+m_{1}^{\prime}(\tilde{s_{2}}+2\tilde{d_{2}})]}$

  * •

For $i^{*}=1$, as we did in the proof of Theorem 5.16, we use the matching
$M_{1}\cup M_{1}^{\prime}$ instead of $M_{1}$. We get the bound:

$\displaystyle\alpha_{1}$
$\displaystyle=2(1-(2-\delta)(m_{1}+m_{1}^{\prime}))=2-(4-2\delta)(s_{1}+d_{1}+m_{1}^{\prime})$

Note that the arguments we used in the proof of Theorem 5.16 regarding Lemma
4.4, the constraint ($\ast$ ‣ 5.2.3) and Lemma 5.17, hold similarly in the
current analysis (i.e., when $q_{1}=q_{2}=q_{3}$), so we may assume $d_{1}=0$
and maximize $\min\\{\alpha_{1},\alpha_{2},\alpha_{3}\\}$ under the constraint
($\ast\ast$ ‣ 5.17). We get the following optimization problem:

$\alpha_{*}(\delta,3)\leq\max_{s_{1},\tilde{s_{2}},\tilde{d_{2}},m_{1}^{\prime}}\min\\{\alpha_{1},\alpha_{2},\alpha_{3}\\}$
when:

$\displaystyle\alpha_{3}\leq\frac{\delta}{1-2[2(\frac{1}{2}-(s_{1}+\tilde{s_{2}}+\tilde{d_{2}}))(s_{1}+\tilde{s_{2}})+2s_{1}(\tilde{s_{2}}+\tilde{d_{2}})+m_{1}^{\prime}(\tilde{s_{2}}+2\tilde{d_{2}})]}$
$\displaystyle\alpha_{2}\leq\frac{2-(4-2\delta)(s_{1}+\tilde{s_{2}}+\tilde{d_{2}})}{1-2[2s_{1}(\tilde{s_{2}}+\tilde{d_{2}})+m_{1}^{\prime}(\tilde{s_{2}}+2\tilde{d_{2}})]}$
$\displaystyle\alpha_{1}=2-(4-2\delta)(s_{1}+m_{1}^{\prime})$

Under the constraints:

$\displaystyle s_{1},\tilde{s_{2}},\tilde{d_{2}},m_{1}^{\prime}\geq 0$
$\displaystyle s_{1}+\tilde{s_{2}}+\tilde{d_{2}}\leq\frac{1}{2}$
$\displaystyle m_{1}^{\prime}\leq\frac{\tilde{s_{2}}}{2}+\tilde{d_{2}}$
$\displaystyle
2s_{1}+\tilde{s_{2}}+2\tilde{d_{2}}\geq\frac{2-\delta}{2+\delta}$

We solved the optimization problem for several values of $\delta$, and we
refer the reader to Appendix C.3 for more details. We received the following
upper bounds:

$\delta$ | 1 | 1.1 | 1.2 | 1.3 | 1.4 | 1.5 | 1.6 | 1.7 | 1.8 | 1.9
---|---|---|---|---|---|---|---|---|---|---
$\alpha_{*}(\delta,3)\leq$ | 1.62 | 1.69 | 1.77 | 1.83 | 1.88 | 1.92 | 1.95 | 1.97 | 1.99 | 1.997

## Acknowledgements

This project has received funding from the European Research Council (ERC)
under the European Union’s Horizon 2020 research and innovation programme
(grant agreement No. 819702)

## References

  * [1] Ryan Alweiss, Chady Ben Hamida, Xiaoyu He and Alexander Moreira  “On the subgraph query problem”  In _Combinatorics, Probability and Computing_ 30.1 Cambridge University Press, 2021, pp. 1–16
  * [2] Amit Chakrabarti and Subhash Khot  “Improved lower bounds on the randomized complexity of graph properties”  In _International Colloquium on Automata, Languages, and Programming_ , 2001, pp. 285–296  Springer
  * [3] David Conlon, Jacob Fox, Andrey Grinshpun and Xiaoyu He  “Online Ramsey Numbers and the Subgraph Query Problem”  In _Building Bridges II_ Springer, 2019, pp. 159–194
  * [4] Gröger Hans Dietmar  “On the randomized complexity of monotone graph properties”  In _Acta Cybernetica_ 10.3, 1992, pp. 119–127
  * [5] Uriel Feige et al.  “Finding cliques using few probes”  In _Random Structures & Algorithms_ 56.1 Wiley Online Library, 2020, pp. 142–153
  * [6] Asaf Ferber, Michael Krivelevich, Benny Sudakov and Pedro Vieira  “Finding Hamilton cycles in random graphs with few queries”  In _Random Structures & Algorithms_ 49.4 Wiley Online Library, 2016, pp. 635–668
  * [7] Asaf Ferber, Michael Krivelevich, Benny Sudakov and Pedro Vieira  “Finding paths in sparse random graphs requires many queries”  In _Random Structures & Algorithms_ 50.1 Wiley Online Library, 2017, pp. 71–85
  * [8] Ehud Friedgut, Jeff Kahn and Avi Wigderson  “Computing graph properties by randomized subcube partitions”  In _International Workshop on Randomization and Approximation Techniques in Computer Science_ , 2002, pp. 105–113  Springer
  * [9] Jeff Kahn, Michael Saks and Dean Sturtevant  “A topological approach to evasiveness”  In _Combinatorica_ 4.4 Springer, 1984, pp. 297–306
  * [10] László Lovász and Michael D Plummer  “Matching theory”  American Mathematical Soc., 2009
  * [11] Laszlo Lovasz and Neal E Young  “Lecture notes on evasiveness of graph properties”  In _arXiv preprint cs/0205031_ , 2002
  * [12] Jay Mardia, Hilal Asi and Kabir Aladin Chandrasekher  “Finding Planted Cliques in Sublinear Time”  In _arXiv preprint arXiv:2004.12002_ , 2020
  * [13] David W Matula  “Employee party problem”  In _Notices of the American Mathematical Society_ 19.2, 1972, pp. A382–A382  AMER Mathematical SOC 201 Charles ST, Providence, RI 02940-2213
  * [14] Ryan O’Donnell, Michael Saks, Oded Schramm and Rocco A Servedio  “Every decision tree has an influential variable”  In _46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05)_ , 2005, pp. 31–39  IEEE
  * [15] Miklós Z Rácz and Benjamin Schiffer  “Finding a planted clique by adaptive probing”  In _arXiv preprint arXiv:1903.12050_ , 2019
  * [16] Ronald L Rivest and Jean Vuillemin  “A generalization and proof of the Aanderaa-Rosenberg conjecture”  In _Proceedings of the seventh annual ACM symposium on Theory of computing_ , 1975, pp. 6–11
  * [17] Robert Scheidweiler and Eberhard Triesch  “A lower bound for the complexity of monotone graph properties”  In _SIAM Journal on Discrete Mathematics_ 27.1 SIAM, 2013, pp. 257–265
  * [18] Andrew Chi-Chih Yao  “Lower bounds to randomized algorithms for graph properties”  In _Journal of Computer and System Sciences_ 42.3 Elsevier, 1991, pp. 267–287
  * [19] Andrew Chi-Chih Yao  “Monotone bipartite graph properties are evasive”  In _SIAM Journal on Computing_ 17.3 SIAM, 1988, pp. 517–520

##  Appendix A Proof of Lemma 4.4

###### Proof.

Let $\mathcal{A}$ be a $(\delta,l,\alpha)$-algorithm. We have:

$\displaystyle\frac{1}{2}$ $\displaystyle\leq\mathbb{P}(\mathcal{A}\text{
succeeds})\leq\sum_{p\in\mathcal{S}}\mathbb{P}(\mathcal{A}_{p}\text{
succeeds})=$ $\displaystyle=\sum_{p\in\mathcal{S}_{I_{l-1}\leq\delta\log
n}}\mathbb{P}(\mathcal{A}_{p}\text{
succeeds})+\sum_{p\in\mathcal{S}_{I_{l-1}>\delta\log
n}}\mathbb{P}(\mathcal{A}_{p}\text{ succeeds})$

Assume for contradiction that $\sum_{p\in\mathcal{S}_{I_{l-1}>\delta\log
n}}\mathbb{P}(\mathcal{A}_{p}\text{ succeeds})\geq\frac{1}{4}$. Let
$\mathcal{A}^{>}$ be an algorithm with the same queries as $\mathcal{A}$, that
succeeds if $\mathcal{A}_{p}$ succeeds for some
$p\in\mathcal{S}_{I_{l-1}>\delta\log n}$. We have:

$\mathbb{P}(\mathcal{A}^{>}\text{
succeeds})=\sum_{p\in\mathcal{S}_{I_{l-1}>\delta\log
n}}\mathbb{P}(\mathcal{A}_{p}\text{ succeeds})\geq\frac{1}{4}$

Let $\mathcal{A}_{1}$ be the (randomized) 1-round algorithm that queries the
same pairs as $\mathcal{A}^{>}$ queries in round $l$. $\mathcal{A}_{1}$
succeeds if it finds a clique of size $I_{l-1}$ for some $I_{l-1}>\delta\log
n$. Since $\mathcal{A}^{>}$ succeeds only if an independent set of size
$I_{l-1}$ in $K_{l-1}$ is a clique in $K_{l}$, we have that $\mathcal{A}^{>}$
succeeds only if $\mathcal{A}_{1}$ succeeds, so:

$\mathbb{P}(\mathcal{A}_{1}\text{
succeeds})\geq\mathbb{P}(\mathcal{A}^{>}\text{ succeeds})\geq\frac{1}{4}$

Denote $\alpha_{1}=\frac{I_{l-1}}{\log n}$, and assume $\alpha_{1}>\delta$. In
the proof of Lemma 4.1 we get a contradiction after assuming there is a
$(\delta,l,\alpha)$-algorithm when
$\alpha>\max_{p\in\mathcal{S}}\min_{j}\frac{2f_{1}^{j}(p)}{f_{2}^{j}(p)}$,
which in our case means $\alpha_{1}>\delta$. $\mathcal{A}_{1}$ is not a
$(\delta,1,\alpha_{1})$-algorithm, because it finds a clique of size
$\alpha_{1}\log n$ with probability $\frac{1}{4}$ and not $\frac{1}{2}$.
However, replacing the constant $\frac{1}{2}$ with $\frac{1}{4}$ in the proof
of Lemma 4.1 leads to the same contradiction.

Therefore, we have $\sum_{p\in\mathcal{S}_{I_{l-1}>\delta\log
n}}\mathbb{P}(\mathcal{A}_{p}\text{ succeeds})<\frac{1}{4}$, and we get:

$\frac{1}{4}\leq\sum_{p\in\mathcal{S}_{I_{l-1}\leq\delta\log
n}}\mathbb{P}(\mathcal{A}_{p}\text{ succeeds})$

Applying the proof of Lemma 4.1, again with $\frac{1}{4}$ instead of
$\frac{1}{2}$, we get:

$\alpha_{*}(\delta,l)\leq\max_{p\in\mathcal{S}_{I_{l-1}\leq\delta\log
n}}\min_{j}\frac{2f_{1}^{j}(p)}{f_{2}^{j}(p)}$

∎

##  Appendix B Theorem 5.9 calculations

######  Lemma B.1.

Let $\frac{6}{5}<\delta<2$, and denote
$m^{*}\coloneqq\frac{1-\frac{\delta}{2}}{1+\frac{\delta}{2}}$, and
$\alpha_{2}^{\delta}(m)\coloneqq\frac{\delta-(\frac{5}{2}\delta-3)m}{4m^{2}-2m+1}$.
The maximum of $\alpha_{2}^{\delta}(m)$ over the domain $0\leq m\leq m^{*}$ is
obtained when $m=m^{*}$, and in that case
$\alpha_{2}^{\delta}(m^{*})=1+\frac{\delta}{2}$.

###### Proof.

We start with showing that $\alpha_{2}^{\delta}(m^{*})=1+\frac{\delta}{2}$:

$\displaystyle\alpha_{2}^{\delta}(m^{*})$
$\displaystyle=\frac{\delta-(\frac{5}{2}\delta-3)\frac{1-\frac{\delta}{2}}{1+\frac{\delta}{2}}}{4\Big{(}\frac{1-\frac{\delta}{2}}{1+\frac{\delta}{2}}\Big{)}^{2}-2\Big{(}\frac{1-\frac{\delta}{2}}{1+\frac{\delta}{2}}\Big{)}+1}=\frac{\delta(1+\frac{\delta}{2})-(\frac{5}{2}\delta-3)(1-\frac{\delta}{2})}{4(1-\frac{\delta}{2})^{2}-2((1-\frac{\delta}{2})(1+\frac{\delta}{2}))+(1+\frac{\delta}{2})^{2}}(1+\frac{\delta}{2})=$
$\displaystyle=\frac{\delta+\frac{1}{2}\delta^{2}+\frac{5}{4}\delta^{2}-4\delta+3}{\delta^{2}-4\delta+4+\frac{1}{2}\delta^{2}-2+\frac{1}{4}\delta^{2}+\delta+1}(1+\frac{\delta}{2})=\frac{\frac{7}{4}\delta^{2}-3\delta+3}{\frac{7}{4}\delta^{2}-3\delta+3}(1+\frac{\delta}{2})=1+\frac{\delta}{2}$

Next, we want to show this value is maximal. Since $4m^{2}-2m+1>0$ for any
$m$, $\alpha_{2}^{\delta}(m)$ is continuous and therefore the maximum over the
interval $[0,m^{*}]$ is obtained either on the boundaries or on a local
maximum. For $m=0$ we have $\alpha_{2}^{\delta}(0)=\delta<1+\frac{\delta}{2}$,
so proving there are no roots of the derivative in the interval $(0,m^{*})$
will prove the lemma.

We calculate the derivative of $\alpha_{2}^{\delta}(m)$ by $m$:

$\frac{\partial\alpha_{2}^{\delta}(m)}{\partial
m}=\frac{-(\frac{5}{2}\delta-3)(4m^{2}-2m+1)-(8m-2)(\delta-(\frac{5}{2}\delta-3)m)}{(4m^{2}-2m+1)^{2}}=\frac{4(\frac{5}{2}\delta-3)m^{2}-8\delta
m+3-\frac{1}{2}\delta}{(4m^{2}-2m+1)^{2}}$

$\frac{\partial\alpha_{2}^{\delta}(m)}{\partial m}=0$ is obtained for:

$m=\frac{8\delta\pm\sqrt{(8\delta)^{2}-16(\frac{5}{2}\delta-3)(3-\frac{1}{2}\delta)}}{8(\frac{5}{2}\delta-3)}=\frac{4\delta\pm\sqrt{21\delta^{2}-36\delta+36}}{2(5\delta-6)}$

Since $5\delta-6>0$, the smaller root is the one with minus sign, so it is
enough to prove
$\frac{4\delta-\sqrt{21\delta^{2}-36\delta+36}}{2(5\delta-6)}\geq m^{*}$.
Assuming for contradiction the opposite we get:

$\displaystyle\frac{4\delta-\sqrt{21\delta^{2}-36\delta+36}}{2(5\delta-6)}<$
$\displaystyle\frac{1-\frac{\delta}{2}}{1+\frac{\delta}{2}}$
$\displaystyle(2+\delta)(4\delta-\sqrt{21\delta^{2}-36\delta+36})<$
$\displaystyle(2-\delta)(10\delta-12)$ $\displaystyle
14\delta^{2}-24\delta+24<$
$\displaystyle(2+\delta)\sqrt{21\delta^{2}-36\delta+36}$
$\displaystyle\sqrt{21\delta^{2}-36\delta+36}<$
$\displaystyle\frac{3}{2}(2+\delta)$ $\displaystyle 21\delta^{2}-36\delta+36<$
$\displaystyle\frac{9}{4}(2+\delta)^{2}$ $\displaystyle
75\delta^{2}-180\delta+108<$ $\displaystyle 0$ $\displaystyle
3(5\delta-6)^{2}<$ $\displaystyle 0$

Which is a contradiction.

∎

##  Appendix C Optimization method

In this section we discuss the optimization problems described in Section 5.2.
We start with the problem in the proof of Theorem 5.16 (for the problem
regarding the case $q_{1}=q_{2}=q_{3}$ see Appendix C.3). For every
$1\leq\delta<2$ we have:

$\alpha_{*}((1-\frac{\delta}{2},1,\delta),3)\leq\max_{s_{1},\tilde{s_{2}},\tilde{d_{2}}}\min\\{\alpha_{2},\alpha_{3}\\}$

where the bounds $\alpha_{2},\alpha_{3}$ are as follows:

$\displaystyle\alpha_{3}=\frac{\delta-(3\delta-2)s_{1}-(2\delta-2)(\tilde{s_{2}}+\tilde{d_{2}})}{1-2[2(\frac{1}{2}-(s_{1}+\tilde{s_{2}}+\tilde{d_{2}}))(s_{1}+\tilde{s_{2}})+2s_{1}(\tilde{s_{2}}+\tilde{d_{2}})+\big{[}\frac{1-\frac{\delta}{2}}{2+\delta}-s_{1}\big{]}(\tilde{s_{2}}+2\tilde{d_{2}})]}$
$\displaystyle\alpha_{2}=\frac{2-(2+\delta)s_{1}-2(\tilde{s_{2}}+\tilde{d_{2}})}{1-2[2s_{1}(\tilde{s_{2}}+\tilde{d_{2}})+\big{[}\frac{1-\frac{\delta}{2}}{2+\delta}-s_{1}\big{]}(\tilde{s_{2}}+2\tilde{d_{2}})]}$

and we have the following constraints:

$\displaystyle s_{1},\tilde{s_{2}},\tilde{d_{2}}\geq 0$ $\displaystyle
s_{1}+\tilde{s_{2}}+\tilde{d_{2}}\leq\frac{1}{2}$ $\displaystyle
2s_{1}+\tilde{s_{2}}+2\tilde{d_{2}}\geq\frac{2-\delta}{2+\delta}$

First, we note that for every $1\leq\delta<2$, the signature
$(s_{1},\tilde{s_{2}},\tilde{d_{2}})=(0,\frac{2-\delta}{2+\delta},0)$ (which
is also the signature of Algorithm 4) satisfies the constraints and the
corresponding $\alpha_{2},\alpha_{3}$ both equal $1+\frac{\delta}{2}$. We will
show that this signature maximizes $\min\\{\alpha_{2},\alpha_{3}\\}$. We look
at $\alpha_{2},\alpha_{3}$ as functions of the variables
$s_{1},\tilde{s_{2}},\tilde{d_{2}},\delta$ over the subset of $\mathbb{R}^{4}$
satisfying the constraints. We prove the following lemma:

######  Lemma C.1.

The only points in the domain of $\alpha_{2},\alpha_{3}$ for which

$\min\\{\alpha_{2}(s_{1},\tilde{s_{2}},\tilde{d_{2}},\delta),\alpha_{3}(s_{1},\tilde{s_{2}},\tilde{d_{2}},\delta)\\}\geq
1+\frac{\delta}{2}$

are the points along the path $\gamma\mathrel{\mathop{\mathchar
58\relax}}[1,2]\rightarrow\mathbb{R}^{4}$,
$\gamma(\delta)=(0,\frac{2-\delta}{2+\delta},0,\delta)$, and the point
$(s_{1},\tilde{s_{2}},\tilde{d_{2}},\delta)=(0,0,\frac{1}{2},1)\eqqcolon
v_{\tilde{d_{2}}=\frac{1}{2}}$ (for which $\alpha_{2}=\alpha_{3}=\frac{3}{2}$
as well).

######  Remark C.2.

Note that since we prove Lemma C.1 using a computer program and not
analytically, we only prove it up to a certain precision (of roughly
$10^{-6}$, which is the maximal error of the optimization algorithm we use).

The proof is divided into two phases. We sketch the proof process, and
elaborate in the following subsections. First, we show that for any point
which is not close to either the path $\gamma$ or the point
$v_{\tilde{d_{2}}=\frac{1}{2}}$, at least one of $\\{\alpha_{2},\alpha_{3}\\}$
satisfies $\alpha_{i}<1+\frac{\delta}{2}$. We prove this by finding Lipschitz
bounds on the functions $\alpha_{2},\alpha_{3}$ and then evaluating the
functions on a dense enough net of points over the whole domain (the density
of the net depends on the Lipschitz bounds, and it is higher in areas where
$1+\frac{\delta}{2}-\min\\{\alpha_{2},\alpha_{3}\\}$ is small). In the second
phase, we look at neighborhoods of $\gamma$ and
$v_{\tilde{d_{2}}=\frac{1}{2}}$. We go over all points in a dense net over
these neighborhoods, and for each point use a sequential least squares
programming algorithm to find a local maximum of
$\min\\{\alpha_{2},\alpha_{3}\\}$ around the point. All local maximum points
are either the point $v_{\tilde{d_{2}}=\frac{1}{2}}$ or on the path $\gamma$,
hence all points in the domain satisfy $\min\\{\alpha_{2},\alpha_{3}\\}\leq
1+\frac{\delta}{2}$.

###  C.1 Phase 1 - Lipschitz bounds

We start by proving Lipschitz bounds on the functions $\alpha_{2},\alpha_{3}$.
Given a function $f\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{d}\rightarrow\mathbb{R}$ for which $\forall
x\in\mathbb{R}^{d}\mathrel{\mathop{\mathchar
58\relax}}\,\mathinner{\\!\left\lVert\nabla{f}(x)\right\rVert}\leq L$, the
mean value theorem implies $\mathinner{\\!\left\lvert
f(x)-f(y)\right\rvert}\leq L\mathinner{\\!\left\lVert x-y\right\rVert}$.
Therefore we prove upper bounds on
$\mathinner{\\!\left\lVert\nabla{\alpha_{2}}(s_{1},\tilde{s_{2}},\tilde{d_{2}},\delta)\right\rVert}$
and
$\mathinner{\\!\left\lVert\nabla{\alpha_{3}}(s_{1},\tilde{s_{2}},\tilde{d_{2}},\delta)\right\rVert}$,
starting with the former. We have:

$\displaystyle\alpha_{2}(s_{1},\tilde{s_{2}},\tilde{d_{2}},\delta)$
$\displaystyle=\frac{2-(2+\delta)s_{1}-2(\tilde{s_{2}}+\tilde{d_{2}})}{1-2[2s_{1}(\tilde{s_{2}}+\tilde{d_{2}})+\big{[}\frac{1-\frac{\delta}{2}}{2+\delta}-s_{1}\big{]}(\tilde{s_{2}}+2\tilde{d_{2}})]}$
$\displaystyle=\frac{2-(2+\delta)s_{1}-2(\tilde{s_{2}}+\tilde{d_{2}})}{1-2[2s_{1}\tilde{s_{2}}+2s_{1}\tilde{d_{2}}+\frac{1}{2}\cdot\frac{2-\delta}{2+\delta}\tilde{s_{2}}+\frac{2-\delta}{2+\delta}\tilde{d_{2}}-s_{1}\tilde{s_{2}}-2s_{1}\tilde{d_{2}}]}$
$\displaystyle=\frac{2-(2+\delta)s_{1}-2(\tilde{s_{2}}+\tilde{d_{2}})}{1-2s_{1}\tilde{s_{2}}-\frac{2-\delta}{2+\delta}\tilde{s_{2}}-2\cdot\frac{2-\delta}{2+\delta}\tilde{d_{2}}}\eqqcolon\frac{f}{g}$

The function $f$ is bounded since $f\in[0,2]$, and the function $g$ equals
$1-e_{free}^{2}$ (assuming
$m_{1}^{\prime}=\frac{1-\frac{\delta}{2}}{2+\delta}-s_{1}$) so by Lemma 5.13
we have $g\in[\frac{1}{2},1]$. We compute the partial derivatives of $f,g$ and
bound them according to the constraints on the variables:

  * •

$\frac{\partial f}{\partial s_{1}}=-(2+\delta)\in[-4,-3]$ • $\frac{\partial
f}{\partial\tilde{s_{2}}}=-2$ • $\frac{\partial f}{\partial\tilde{d_{2}}}=-2$
• $\frac{\partial f}{\partial\delta}=-s_{1}\in[-\frac{1}{2},0]$

  * •

$\frac{\partial g}{\partial s_{1}}=-2\tilde{s_{2}}\in[-1,0]$ • $\frac{\partial
g}{\partial\tilde{s_{2}}}=-2s_{1}-\frac{2-\delta}{2+\delta}\in[-\frac{4}{3},0]$
• $\frac{\partial
g}{\partial\tilde{d_{2}}}=-2\cdot\frac{2-\delta}{2+\delta}\in[-\frac{2}{3},0]$
• $\frac{\partial g}{\partial\delta}=0$

The function $\alpha_{2}$ is differentiable on the whole domain (since
$g\geq\frac{1}{2}$) and we have the following bounds on its partial
derivatives (using interval arithmetic):

  * •

$\mathinner{\\!\left\lvert\frac{\partial\alpha_{2}}{\partial
s_{1}}\right\rvert}=\mathinner{\\!\left\lvert\frac{\frac{\partial f}{\partial
s_{1}}g-\frac{\partial g}{\partial
s_{1}}f}{g^{2}}\right\rvert}\in\mathinner{\\!\left\lvert\frac{[-4,-3]\cdot[\frac{1}{2},1]-[-1,0]\cdot[0,2]}{[\frac{1}{4},1]}\right\rvert}\subseteq\mathinner{\\!\left\lvert\frac{[-4,-\frac{3}{2}]+[0,2]}{[\frac{1}{4},1]}\right\rvert}\subseteq[0,16]$

  * •

$\mathinner{\\!\left\lvert\frac{\partial\alpha_{2}}{\partial\tilde{s_{2}}}\right\rvert}=\mathinner{\\!\left\lvert\frac{\frac{\partial
f}{\partial\tilde{s_{2}}}g-\frac{\partial
g}{\partial\tilde{s_{2}}}f}{g^{2}}\right\rvert}\in\mathinner{\\!\left\lvert\frac{-2\cdot[\frac{1}{2},1]-[-\frac{4}{3},0]\cdot[0,2]}{[\frac{1}{4},1]}\right\rvert}\subseteq\mathinner{\\!\left\lvert\frac{[-2,-1]+[0,\frac{8}{3}]}{[\frac{1}{4},1]}\right\rvert}\subseteq[0,8]$

  * •

$\mathinner{\\!\left\lvert\frac{\partial\alpha_{2}}{\partial\tilde{d_{2}}}\right\rvert}=\mathinner{\\!\left\lvert\frac{\frac{\partial
f}{\partial\tilde{d_{2}}}g-\frac{\partial
g}{\partial\tilde{d_{2}}}f}{g^{2}}\right\rvert}\in\mathinner{\\!\left\lvert\frac{-2\cdot[\frac{1}{2},1]-[-\frac{2}{3},0]\cdot[0,2]}{[\frac{1}{4},1]}\right\rvert}\subseteq\mathinner{\\!\left\lvert\frac{[-2,-1]+[0,\frac{4}{3}]}{[\frac{1}{4},1]}\right\rvert}\subseteq[0,8]$

  * •

$\mathinner{\\!\left\lvert\frac{\partial\alpha_{2}}{\partial\delta}\right\rvert}=\mathinner{\\!\left\lvert\frac{\frac{\partial
f}{\partial\delta}}{g}\right\rvert}\in\mathinner{\\!\left\lvert\frac{[-\frac{1}{2},0]}{[\frac{1}{2},1]}\right\rvert}\subseteq[0,1]$

Therefore, we get the following bound on
$\mathinner{\\!\left\lVert\nabla{\alpha_{2}}(s_{1},\tilde{s_{2}},\tilde{d_{2}},\delta)\right\rVert}$:

$\mathinner{\\!\left\lVert\nabla{\alpha_{2}}(s_{1},\tilde{s_{2}},\tilde{d_{2}},\delta)\right\rVert}\leq\sqrt{16^{2}+8^{2}+8^{2}+1^{2}}<19.7\eqqcolon
L_{2}$

We repeat the same calculations for $\alpha_{3}$:

$\displaystyle\alpha_{3}(s_{1},\tilde{s_{2}},\tilde{d_{2}},\delta)=\frac{\delta-(3\delta-2)s_{1}-(2\delta-2)(\tilde{s_{2}}+\tilde{d_{2}})}{1-2[2(\frac{1}{2}-(s_{1}+\tilde{s_{2}}+\tilde{d_{2}}))(s_{1}+\tilde{s_{2}})+2s_{1}(\tilde{s_{2}}+\tilde{d_{2}})+\big{[}\frac{1-\frac{\delta}{2}}{2+\delta}-s_{1}\big{]}(\tilde{s_{2}}+2\tilde{d_{2}})]}$
$\displaystyle=\frac{\delta-(3\delta-2)s_{1}-(2\delta-2)(\tilde{s_{2}}+\tilde{d_{2}})}{1-2[s_{1}+\tilde{s_{2}}-2s_{1}^{2}-4s_{1}\tilde{s_{2}}-2\tilde{s_{2}}^{2}-2\tilde{d_{2}}s_{1}-2\tilde{d_{2}}\tilde{s_{2}}+2s_{1}\tilde{s_{2}}+2\tilde{d_{2}}s_{1}+\frac{1}{2}\cdot\frac{2-\delta}{2+\delta}\tilde{s_{2}}+\frac{2-\delta}{2+\delta}\tilde{d_{2}}-s_{1}\tilde{s_{2}}-2\tilde{d_{2}}s_{1}]}$
$\displaystyle=\frac{\delta-(3\delta-2)s_{1}-(2\delta-2)(\tilde{s_{2}}+\tilde{d_{2}})}{1+4s_{1}^{2}+4\tilde{s_{2}}^{2}+6s_{1}\tilde{s_{2}}+4\tilde{d_{2}}s_{1}+4\tilde{d_{2}}\tilde{s_{2}}-2s_{1}-\frac{6+\delta}{2+\delta}\tilde{s_{2}}-2\cdot\frac{2-\delta}{2+\delta}\tilde{d_{2}}}\eqqcolon\frac{f}{g}$

  * •

$f\in[0,2]$ • $\frac{\partial f}{\partial s_{1}}=-(3\delta-2)\in[-4,-1]$ •
$\frac{\partial f}{\partial\tilde{s_{2}}}=-(2\delta-2)\in[-2,0]$ •
$\frac{\partial f}{\partial\tilde{d_{2}}}=-(2\delta-2)\in[-2,0]$ •
$\frac{\partial
f}{\partial\delta}=1-3s_{1}-2(\tilde{s_{2}}+\tilde{d_{2}})\in[-\frac{1}{2},1]$

  * •

$g\in[\frac{1}{2},1]$ • $\frac{\partial g}{\partial
s_{1}}=8s_{1}+6\tilde{s_{2}}+4\tilde{d_{2}}-2\in[-2,2]$ • ${\frac{\partial
g}{\partial\tilde{s_{2}}}=8\tilde{s_{2}}+6s_{1}+4\tilde{d_{2}}-\frac{6+\delta}{2+\delta}\in[-\frac{7}{3},2]}$
• $\frac{\partial
g}{\partial\tilde{d_{2}}}=4s_{1}+4\tilde{s_{2}}-2\cdot\frac{2-\delta}{2+\delta}\in[-\frac{2}{3},2]$
• $\frac{\partial g}{\partial\delta}=0$

  * •

$\mathinner{\\!\left\lvert\frac{\partial\alpha_{3}}{\partial
s_{1}}\right\rvert}=\mathinner{\\!\left\lvert\frac{\frac{\partial f}{\partial
s_{1}}g-\frac{\partial g}{\partial
s_{1}}f}{g^{2}}\right\rvert}\in\mathinner{\\!\left\lvert\frac{[-4,-1]\cdot[\frac{1}{2},1]-[-2,2]\cdot[0,2]}{[\frac{1}{4},1]}\right\rvert}\subseteq\mathinner{\\!\left\lvert\frac{[-4,-\frac{1}{2}]+[-4,4]}{[\frac{1}{4},1]}\right\rvert}\subseteq[0,32]$

  * •

$\mathinner{\\!\left\lvert\frac{\partial\alpha_{3}}{\partial\tilde{s_{2}}}\right\rvert}=\mathinner{\\!\left\lvert\frac{\frac{\partial
f}{\partial\tilde{s_{2}}}g-\frac{\partial
g}{\partial\tilde{s_{2}}}f}{g^{2}}\right\rvert}\in\mathinner{\\!\left\lvert\frac{[-2,0]\cdot[\frac{1}{2},1]-[-\frac{7}{3},2]\cdot[0,2]}{[\frac{1}{4},1]}\right\rvert}\subseteq\mathinner{\\!\left\lvert\frac{[-2,0]+[-4,\frac{14}{3}]}{[\frac{1}{4},1]}\right\rvert}\subseteq[0,24]$

  * •

$\mathinner{\\!\left\lvert\frac{\partial\alpha_{3}}{\partial\tilde{d_{2}}}\right\rvert}=\mathinner{\\!\left\lvert\frac{\frac{\partial
f}{\partial\tilde{d_{2}}}g-\frac{\partial
g}{\partial\tilde{d_{2}}}f}{g^{2}}\right\rvert}\in\mathinner{\\!\left\lvert\frac{[-2,0]\cdot[\frac{1}{2},1]-[-\frac{2}{3},2]\cdot[0,2]}{[\frac{1}{4},1]}\right\rvert}\subseteq\mathinner{\\!\left\lvert\frac{[-2,0]+[-4,\frac{4}{3}]}{[\frac{1}{4},1]}\right\rvert}\subseteq[0,24]$

  * •

$\mathinner{\\!\left\lvert\frac{\partial\alpha_{3}}{\partial\delta}\right\rvert}=\mathinner{\\!\left\lvert\frac{\frac{\partial
f}{\partial\delta}}{g}\right\rvert}\in\mathinner{\\!\left\lvert\frac{[-\frac{1}{2},1]}{[\frac{1}{2},1]}\right\rvert}\subseteq[0,2]$

$\mathinner{\\!\left\lVert\nabla{\alpha_{3}}(s_{1},\tilde{s_{2}},\tilde{d_{2}},\delta)\right\rVert}\leq\sqrt{32^{2}+24^{2}+24^{2}+2^{2}}<46.7\eqqcolon
L_{3}$

The bounds we proved on the gradients of $\alpha_{2},\alpha_{3}$ imply that
any points $x,y$ in the domain for which $\mathinner{\\!\left\lVert
x-y\right\rVert}\leq\epsilon$, satisfy
$\mathinner{\\!\left\lvert\alpha_{i}(x)-\alpha_{i}(y)\right\rvert}\leq
L_{i}\epsilon$. Therefore, if for some point $y$ we have that for at least one
$i\in\\{2,3\\}$, $\alpha_{i}(y)+L_{i}\epsilon\leq 1+\frac{\delta}{2}$, we
deduce that for any $x$ for which $\mathinner{\\!\left\lVert
x-y\right\rVert}\leq\epsilon$ we have
$\min\\{\alpha_{2}(x),\alpha_{3}(x)\\}\leq 1+\frac{\delta}{2}$.

We partitioned the domain into $4$-dimensional hypercubes with edges of size
$\epsilon$, and calculated the values of $\alpha_{2},\alpha_{3}$ on an
$\epsilon$-net of points which includes all centers of the hypercubes. Given a
point $x$ in the domain, let $y$ be the center of the hypercube containing
$x$. The distance between $x$ and $y$ on each coordinate is at most
$\frac{\epsilon}{2}$. Hence, $\mathinner{\\!\left\lVert
x-y\right\rVert}\leq\sqrt{4\Big{(}\frac{\epsilon}{2}\Big{)}^{2}}=\epsilon$.
For any center $y$ which satisfies $\alpha_{i}(y)+L_{i}\epsilon\leq
1+\frac{\delta}{2}$ for some $i\in\\{2,3\\}$, we deduce that all points in the
hypercube satisfy $\min\\{\alpha_{2}(x),\alpha_{3}(x)\\}\leq
1+\frac{\delta}{2}$. For $\epsilon=0.01/L_{3}$ this process eliminates most
area of the domain, and all remaining hypercubes are close to either $\gamma$
or $v_{\tilde{d_{2}}=\frac{1}{2}}$ (the distance is at most $0.041$). Since
all centers satisfy $\alpha_{i}(y)\leq 1+\frac{\delta}{2}$ for some
$i\in\\{2,3\\}$, this phase is enough for proving the weaker claim: $\forall
x\mathrel{\mathop{\mathchar
58\relax}}\,\min\\{\alpha_{2}(x),\alpha_{3}(x)\\}\leq
1+\frac{\delta}{2}+0.01$.

We chose $\epsilon=0.01/L_{3}$ in order to eliminate a large fraction of the
domain. However, an $\epsilon$-net of the domain includes roughly $10^{13}$
points, and evaluating $\alpha_{2},\alpha_{3}$ on all of them is
computationally heavy. Instead, we used a search tree to create a net in which
the density of points in some area depends on how close
$\alpha_{2},\alpha_{3}$ are to $1+\frac{\delta}{2}$ in that area. We start
with a sparse $\epsilon_{0}$-net for some large $\epsilon_{0}$. For any
hypercube with edge size $\epsilon_{i}$ (starting with initial ones of size
$\epsilon_{0}$), we evaluate $\alpha_{2},\alpha_{3}$ on the center $y$, and if
$\alpha_{i}(y)+L_{i}\epsilon_{i}\leq 1+\frac{\delta}{2}$, we deduce that all
points in the hypercube may be eliminated (we do not need a denser net in this
area). Otherwise, we partition the hypercube into $16$ hypercubes with edge
size $\epsilon_{i+1}\coloneqq\frac{\epsilon_{i}}{2}$ and process them
recursively (near the boundary of the domain we may partition into less than
$16$ hypercubes). In the search tree this means we either reach a leaf (i.e.,
we stop partitioning the relevant path), or we create $16$ children of the
current hypercube and continue the search on their subtrees. When we reach a
hypercube of edge size $\epsilon_{i}\leq\epsilon$ which needs to be
partitioned, we do not partition it further because we reached maximum
density. This process is more efficient, and it eliminates roughly the same
area as a full $\epsilon$-net.

###  C.2 Phase 2 - sequential least squares programming

In Phase 2 we prove that in any remaining hypercube all points satisfy
$\min\\{\alpha_{2},\alpha_{3}\\}\leq 1+\frac{\delta}{2}$. For each hypercube
we use a sequential least squares programming (SLSQP) algorithm which
maximizes a non linear function under non linear constraints. Since SLSQP
finds a local maximum, we do not use it over the whole domain, but rather on
small hypercubes (small in relation to the second derivatives of the
functions). The SLSQP algorithm works when the objective function and the
constraints are twice continuously differentiable. Our objective function is
not differentiable (minimum of two functions) so we modify the optimization
problem before applying SLSQP. Any point $x\in\gamma$ satisfies
$\alpha_{2}(x)=\alpha_{3}(x)=1+\frac{\delta}{2}$. Therefore, in order to find
$\max_{s_{1},\tilde{s_{2}},\tilde{d_{2}}}\min\\{\alpha_{2},\alpha_{3}\\}$ for
every $\delta$, it is enough to limit the search only to points in which
$\alpha_{2}\geq 1+\frac{\delta}{2}$ and $\alpha_{3}\geq 1+\frac{\delta}{2}$
(we used the same argument on $\alpha_{1}$). We get the following constraints:

$\displaystyle
1+\frac{\delta}{2}\leq\frac{\delta-(3\delta-2)s_{1}-(2\delta-2)(\tilde{s_{2}}+\tilde{d_{2}})}{1-2[2(\frac{1}{2}-(s_{1}+\tilde{s_{2}}+\tilde{d_{2}}))(s_{1}+\tilde{s_{2}})+2s_{1}(\tilde{s_{2}}+\tilde{d_{2}})+\big{[}\frac{1-\frac{\delta}{2}}{2+\delta}-s_{1}\big{]}(\tilde{s_{2}}+2\tilde{d_{2}})]}$
$\displaystyle
1+\frac{\delta}{2}\leq\frac{2-(2+\delta)s_{1}-2(\tilde{s_{2}}+\tilde{d_{2}})}{1-2[2s_{1}(\tilde{s_{2}}+\tilde{d_{2}})+\big{[}\frac{1-\frac{\delta}{2}}{2+\delta}-s_{1}\big{]}(\tilde{s_{2}}+2\tilde{d_{2}})]}$

We use SLSQP to show that the only points which satisfy all constraints are
either the point $v_{\tilde{d_{2}}=\frac{1}{2}}$ or they are on the path
$\gamma$. This will prove Lemma C.1. Given a remaining hypercube close to
$\gamma$, and assuming a point which satisfies all constraints exists in it,
we want to guarantee it will be found by the SLSQP algorithm, when it is
initialized in the center of the hypercube. We create a maximization problem
with the previous and new constraints, where the objective function is the
square of the distance from the path $\gamma$:

$\max_{s_{1},\tilde{s_{2}},\tilde{d_{2}},\delta}s_{1}^{2}+(\tilde{s_{2}}-\frac{2-\delta}{2+\delta})^{2}+\tilde{d_{2}}^{2}$

If the algorithm returns a point on $\gamma$ (i.e., with distance $0$ from the
path) this means that no point in the hypercube satisfies all constraints
(unless the hypercube intersects the path). Equivalently, for remaining
hypercubes close to $v_{\tilde{d_{2}}=\frac{1}{2}}$, the maximized objective
function will be the square of the distance from
$v_{\tilde{d_{2}}=\frac{1}{2}}$:

$\max_{s_{1},\tilde{s_{2}},\tilde{d_{2}},\delta}s_{1}^{2}+\tilde{s_{2}}^{2}+(\frac{1}{2}-\tilde{d_{2}})^{2}+(1-\delta)^{2}$

For each hypercube remaining after Phase 1 (roughly $2\cdot 10^{8}$
hypercubes) we applied SLSQP initialized in its center. No run of the
algorithm failed to find a maximizing point, and in all runs this point was on
the path $\gamma$ (or it was $v_{\tilde{d_{2}}=\frac{1}{2}}$ for the
hypercubes in its neighborhood). Therefore, there is no other point in any of
the remaining hypercubes which satisfies all constraints, and Lemma C.1
follows.

###  C.3 Optimization method for non-restricted case

We solve the optimization problem described in Section 5.2.4 for any $\delta$
of the form $\delta=1+0.1z$ for the integers $0\leq z\leq 9$. Since we do not
prove an upper bound that needs to hold for all $\delta$, we skip phase 1, and
instead use SLSQP in order to find all local maximum points of the objective
function. For $\epsilon=0.01$, we create an $\epsilon$-net spanning the domain
of the parameters $s_{1},\tilde{s_{2}},\tilde{d_{2}},m_{1}^{\prime}$, and for
each point in the net run SLSQP initialized in the point. Then we take the
maximum over all returned values. Since the objective function is not twice
continuously differentiable, we introduce a new variable $t$ and solve the
following equivalent optimization problem:

$\max t$

Under the constraints:

  * •

$t\leq\frac{\delta}{1-2[2(\frac{1}{2}-(s_{1}+\tilde{s_{2}}+\tilde{d_{2}}))(s_{1}+\tilde{s_{2}})+2s_{1}(\tilde{s_{2}}+\tilde{d_{2}})+m_{1}^{\prime}(\tilde{s_{2}}+2\tilde{d_{2}})]}$

  * •

$t\leq\frac{2-(4-2\delta)(s_{1}+\tilde{s_{2}}+\tilde{d_{2}})}{1-2[2s_{1}(\tilde{s_{2}}+\tilde{d_{2}})+m_{1}^{\prime}(\tilde{s_{2}}+2\tilde{d_{2}})]}$

  * •

$t\leq 2-(4-2\delta)(s_{1}+m_{1}^{\prime})$

  * •

$s_{1},\tilde{s_{2}},\tilde{d_{2}},m_{1}^{\prime}\geq 0$

  * •

$s_{1}+\tilde{s_{2}}+\tilde{d_{2}}\leq\frac{1}{2}$

  * •

$m_{1}^{\prime}\leq\frac{\tilde{s_{2}}}{2}+\tilde{d_{2}}$

  * •

$2s_{1}+\tilde{s_{2}}+2\tilde{d_{2}}\geq\frac{2-\delta}{2+\delta}$