On Learning Graphs with Edge-Detecting Queries
Hasan Abasi
HASSAN @ CS . TECHNION . AC . IL
Nader H. Bshouty BSHOUTY @ CS . TECHNION . AC . IL

arXiv:1803.10639v1 [cs.LG] 28 Mar 2018

Technion, Haifa, Israel
March 29, 2018

Abstract
We consider the problem of learning a general graph G = (V, E) using edge-detecting queries,
where the number of vertices |V | = n is given to the learner. The information theoretic lower
bound gives m log n for the number of queries, where m = |E| is the number of edges. In case
the number of edges m is also given to the learner, Angluin-Chen’s Las Vegas algorithm Angluin and Chen (2008) runs in 4 rounds and detects the edges in O(m log n) queries. In the other
harder case where
√ the number of edges m is unknown, their algorithm runs in 5 rounds and asks
O(m log n + m log2 n) queries. There have been two open problems: (i) can the number of
queries be reduced to O(m log n) in the second case, and, (ii) can the number of rounds be reduced
without substantially increasing the number of queries (in both cases).
For the first open problem (when m is unknown)
√ we give two algorithms. The first is an
O(1)-round Las Vegas algorithm that asks m log n + m(log[k] n) log n queries for any constant
k

k where log[k] n = log · · · log n. The second is an O(log∗ n)-round Las Vegas algorithm that
asks O(m log n) queries. This solves the first open problem for any practical n, for example,
n < 265536 . We also show that no deterministic algorithm can solve this problem in a constant
number of rounds.
To solve the second problem we study the case when m is known. We first show that any
non-adaptive Monte Carlo algorithm (one-round) must ask at least Ω(m2 log n) queries, and any
two-round Las Vegas algorithm must ask at least m4/3−o(1) log n queries on average. We then
give two two-round Monte Carlo algorithms, the first asks O(m4/3 log n) queries for any n and m,
and the second asks O(m log n) queries when n > 2m . Finally, we give a 3-round Monte Carlo
algorithm that asks O(m log n) queries for any n and m.
Keywords: Graphs Learning, Group Testing, Edge-Detecting Queries, Monte Carlo Algorithm,
Las Vegas Algorithm.

1. Introduction
We consider the problem of learning a general graph G = (V, E) using edge-detecting queries. In
edge-detecting queries the learning algorithm asks whether a subset of vertices Q ⊆ V contains an
edge in the graph G. That is, whether there are u, v ∈ Q such that {u, v} ∈ E. The learner knows
the number of vertices |V | = n.
Graph learning is a well-studied problem. It has been studied for general graphs, Angluin and
Chen (2008) and also for specific graph families (i.e. matching, stars, cliques and other) see Alon
and Asodi (2005); Alon et al. (2004). This problem has also been generalized to learning a hypergraph (where each edge consists of two or more vertices) see Abasi et al. (2018, 2014); Angluin and
1

L EARNING G RAPH

Chen (2006). The motivation behind studying some graph families relevant to the problem above,
was its various applications in different areas such molecular biology, chemistry and networks Bouvel et al. (2005); Angluin et al. (2010). For example, the general graph case is motivate by problems
from biology and chemistry where, given a set of molecules (chemicals), we need pairs that react
with each other. In this case, the vertices correspond to the molecules (chemicals), the edges to
the reactions, and the queries to experiments of putting a set of molecules (chemicals) together in
a test tube and determining whether a reaction occurs. When multiple molecules (chemicals) are
combined in one test tube, a reaction is detectable if and only if at least one pair of the molecules
(chemicals) in the tube react. The task is to identify which pairs react using as few experiments
as possible. One more example of a problem encountered by molecular biologists, is the problem
of finding a hidden match, when applying multiplex PCR in order to close the gaps left in a DNA
strand after shotgun sequencing. See Alon and Asodi (2005); Alon et al. (2004) and there references
for more details.
For a general graph, the information theoretic lower bound gives m log n for the number of
queries where m = |E| is the number of edges. In case the number of edges m is also given to the
learner, Angluin-Chen’s Las Vegas algorithm Angluin and Chen (2008) runs in 4 rounds and detects
the edges in O(m log n) queries. In the other harder case where the number of edges m is unknown,
√
their algorithm runs in 5 rounds and asks O(m log n + m log2 n) queries. There have been two
open problems: (i) can the number of queries be reduced to O(m log n) in the second case, and,
(ii) can the number of rounds be reduced without substantially increasing the number of queries (in
both cases).
For the first open problem (when m in unknown) we give two algorithms. The first is an O(1)√
round algorithm that asks m log n + m(log[k] n) log n queries for any constant k. Here log[k] n =
k

log · · · log n. The second is an O(log∗ n)-round algorithm that asks O(m log n) queries. This
solves the first open problem for any practical n, for example n < 265536 . We also show that no
deterministic algorithm can solve this problem in a constant number of rounds.
To solve the second problem we study the problem when m is known. We first show that any
non-adaptive (one-round) Monte Carlo algorithm must ask at least Ω(m2 log n) queries. We then
give two two-round Monte Carlo algorithms, the first asks O(m4/3 log n) queries for any n and
m, and the second asks O(m log n) queries when n > 2m . Then we give a 3-round Monte Carlo
algorithm that asks O(m log n) queries for any n and m. We also show that any two-round Las Vegas algorithm must ask at least m4/3 queries on average and any deterministic two-round algorithm
must ask at least Ω(m2 log n) queries. Finally, we give a four-round deterministic algorithm that
asks m2+ log n queries for any constant . The question whether there is an O(1)-round deterministic algorithm that asks O(m log n) queries remains open.
Our results are summarized in the following two tables
1.1. Results For Unknown m
Lower Bound
LV&MC Randomized
O(1)-Rounds
m log n
LV&MC Randomized
O(log∗ n)-Round

Upper Bound
√

m log n

m log n
m(log[k] n) log n
m log n

2

Poly. Time
√

m log n+
m(log[k] n) log n
m log n

L EARNING G RAPH

1.2. Results For Known m
Non-Adaptive
MC Randomized
Non-Adaptive
Deter. & LV Rand.
Two Rounds
MC Randomized
n→∞
Two Rounds
LV Randomized
Two Rounds
Deterministic
Three Rounds
MC Randomized
Three Rounds
LV Randomized
n→∞
Three Rounds
Deterministic
Four Rounds
LV Randomized
Five Rounds
Deterministic

Lower Bound
Thm.2
m2 log n
D’yachkov and Rykov (1983)
m3
log m log n

Upper Bound
⇒
2
m log n
⇒
3
m log n

Poly. Time
Thm. 1
m2 log n
Bshouty (2015)
m3 log n

⇒
OPEN
m log n

m4/3 log n

Thm.3&5
m4/3 log n
m log n
Thm. 1
m2 log n

OPEN
Thm.9
m2
log m log n

m log n
⇒
2
m log n
Thm.8
m2 log n

I.T.
m log n
I.T.
m log n
m log n

⇒
m log n
⇒
4/3
m log n
m log n

Thm. 4
m log n
Thm.3&6
m4/3 log n
m log n

OPEN
I.T.
m log n

OPEN
⇒
m log n
⇒
2+
m
log n

OPEN
Thm. 4
m log n
Thm.10
m2+ log n

OPEN

OPEN

2. Definitions and Preliminary Results
Let G = (V, E) be a simple (contains no loop or multiple edges) undirected graph with |V | = n
vertices and |E| ≤ m edges. We call G the target m-graph. The learner knows n. We study both
cases where m is known to the learner and when it is not. The learner can ask an edge-detecting
queries (or just a query) Q ⊆ V to an oracle OG . The answer to the query Q is OG (Q) =“YES” if
there are u, v ∈ Q such that {u, v} ∈ E and “NO” otherwise.
We say that a non-simple graph G = (V, E) is m-Loop if the graph contains at most m loops.
That is, the graph contains at most m edges where each edge connects a vertex to itself. Learning
m-Loop is equivalent to the problem of group testing Du et al. (2000); Kwang-ming and Ding-zhu
(2006).
For a graph G = (V, E) and a subset of vertices V 0 ⊆ V we define the neighbours of V 0 ,
ΓG (V 0 ), as the set of all vertices u in V \V 0 such that there is v ∈ V 0 where {u, v} ∈ E. When
V 0 = {v} then we write ΓG (v) and call it the neighbours of v. We say that V 0 is an independent set
if there are no edges between the vertices in V 0 . A set of vertices I ⊂ V is called independent set
in G = (V, E) if (I × I) ∩ E = ∅.
We will denote by [n] := {1, 2, . . . , n} and [m, n] = {m, m + 1, . . . , n}.

3

L EARNING G RAPH

2.1. Preliminary Results for Randomized Algorithms
The following lemma is from Angluin and Chen (2008):
Lemma 1 Let G = (V, E) be the target graph with n vertices and m edges. Let Q ⊆ V be a
random query where for each vertex i ∈ V , i is included in Q independently with probability p. Let
{u, v} 6∈ E. Then
1. If |ΓG ({u, v})| ≤ r, then with probability at least p2 (1 − rp − mp2 ), u, v ∈ Q and
OG (Q) =“NO”.
2. If |ΓG ({u, v})| ≥ r, then with probability at most p2 (1 − p)r , u, v ∈ Q and OG (Q) =“NO”.
Proof Let ΓG ({u, v}) = {w1 , . . . , wr0 }. Let {u1 , v1 }, . . . , {um−r0 , vm−r0 } be all the edges of G
that none of their endpoints are u or v. When r0 ≤ r,
Pr[u, v ∈ Q ∧ OG (Q) = “NO”] = Pr[u, v ∈ Q] Pr[OG (Q) = “NO” | u, v ∈ Q]
= p2 Pr[(∀i)wi 6∈ Q ∧ (∀j){uj , vj } 6⊆ Q]
= p2 (1 − Pr[(∃i)wi ∈ Q ∨ (∃j){uj , vj } ⊆ Q])
≥ p2 (1 − r0 p − (m − r0 )p2 )
≥ p2 (1 − rp − mp2 ).
and when r0 ≥ r,
Pr[u, v ∈ Q ∧ OG (Q) = “NO”] = p2 Pr[(∀i)wi 6∈ Q ∧ (∀j){uj , vj } 6⊂ Q]
≤ p2 Pr[(∀i)wi 6∈ Q]
0

= p2 (1 − p)r ≤ p2 (1 − p)r .

Lemma 2 Let G = (V, E) be the target graph with n vertices and m edges. Consider the algorithm
in Figure 1 with
2 ln n + ln(1/δ)
t := t(n, m, r, p, δ) = 2
.
p (1 − rp − mp2 )
Then for Er = {{u, v} : |ΓG ({u, v})| > r},
1. E ⊆ E(H).
2. With probability at least 1 − δ, E(H)\(E ∪ Er ) = ∅, i.e., all the edges {u, v} ∈ E(H)\E
satisfies |ΓG ({u, v})| > r.
3. E [|E(H)\(E ∪ Er )|] ≤ δ.
Proof Consider the algorithm in Figure 1. An edge {i, j} is removed from the graph H if and only
if i, j ∈ Q and OG (Q) =“NO”. Therefore, if {i, j} ∈ E then {i, j} ∈ E(H). This proves 1.
We now prove 2. Let {u, v} be such that |Γ({u, v})| ≤ r. The probability that {u, v} ∈
E(H)\E is the probability that for all the queries Q(i) , i = 1, . . . , t in the algorithm, either {u, v} 6⊆
4

L EARNING G RAPH

Algorithm
Learn First Round
1.
2.
3.
4.
5.
5.
6.
7.
8.

E(H) ← {{u, v} | u, v ∈ V, u 6= v}
Repeat t(n, m, r, p, δ) times
Choose Q ⊂ V s.t. for all i ∈ V , Pr[i ∈ Q] = p.
Answer← OG (Q)
If Answer=“NO” then
For every i, j ∈ Q.
E(H) ← E(H)\{(i, j)}.
End Repeat
Output(H = (V, E(H)))

Figure 1: First Round in the Algorithm.
Q(i) or OG (Q(i) ) =“YES”. By Lemma 1, this probability is at most (1 − p2 (1 − rp − mp2 ))t .
Therefore, the probability that there is {u, v} such that |Γ({u, v})| ≤ r and {u, v} ∈ E(H)\E is at
most
n2 (1 − p2 (1 − rp − mp2 ))t ≤ δ.
The expected number of edges in E(H)\(E ∪Er ) is also at most n2 (1−p2 (1−rp−mp2 ))t ≤ δ.

3. Non-Adaptive Algorithms when m is Known
In this section we study non-adaptive learning algorithms when m is known to the algorithm. We
first give a polynomial time Monte Carlo algorithm that asks O(m2 log n) queries and then prove the
lower bound Ω(m2 log n) for the number of queries. For the non-adaptive deterministic algorithm,
there is a polynomial time algorithm that asks O(m3 log n) queries and it is known that the lower
bound for the number of queries is Ω(m3 log n/ log m) Abasi et al. (2018); Kwang-ming and Dingzhu (2006). For Las Vegas algorithm, a non-adaptive algorithm must be deterministic because the
success probability is 1. Therefore, the bounds for the number of queries of deterministic algorithms
apply also for Las Vegas algorithms.
3.1. Upper Bound for Randomized Non-Adaptive Algorithm
We first state the following theorem:
Theorem 1 There is a non-adaptive Monte Carlo randomized learning algorithm with 1/poly(n)
error probability for m-Graph that asks O(m2 log n) queries.
There is a two-round Las Vegas randomized learning algorithm for m-Graph that asks O(m2 log n)
expected number of queries.

5

L EARNING G RAPH

Proof Consider the algorithm in Figure 1 with r = m, p = 1/(2m) and δ = 1/poly(n). Then by
Lemma 2, the number of queries is t(n, m, r, p, δ) = O(m2 log n). Again by Lemma 2, E ⊆ E(H)
and with probability at least 1 − δ all the edges {u, v} ∈ E(H)\E satisfies |Γ({u, v})| > m + 1.
Since G has at most m edges we must have |Γ({u, v})| ≤ m + 1 for any u, v ∈ V and therefore
with probability at least 1 − δ, E(H) = E.
For the Las Vegas algorithm we add another round that asks a query for each edge in E(H).
The number of expected edges is less than m + 1 and therefore the expected number of queries in
the second round is less than m + 1.

3.2. Lower Bound for Randomized Non-Adaptive Algorithm
Lemma 3 Any non-adaptive Monte Carlo randomized learning algorithm with error probability
at most 1/2 for m-Loop must ask at least Ω(m log n) queries.

n
. Therefore, by the information theoretic lower
Proof The number of m-loops with n vertices is m
bound and Lemma 2 in Abasi et al. (2014) the result follows.
Theorem 2 Any non-adaptive Monte Carlo randomized learning algorithm with error probability
at most 1/4 for m-Graph must ask at least Ω(m2 log n) queries.
Proof Let A(s, OG ) be a Monte Carlo randomized non-adaptive learning algorithm that learns mGraph over the vertices [n] with error probability at most 1/4, where s ∈ {0, 1}∗ is a random seed
and OG is the query oracle to the target graph G. Let As be the set of queries that are asked when
the random seed is s. Suppose, on the contrary, that for all s, |As | ≤ cm2 log n, for some c = o(1).
Let As,i , i = 1, . . . , m/2 be the set of queries Q in As that contains the vertex i and does not contain
any of the vertices in [m/2]\{i}. That is Q ∩ [m/2] = {i}. Then, over the uniform distribution,
(m/2)Ei∈[m/2] [|As,i |] ≤ |As | < cm2 log n. Therefore, Ei∈[m/2] [|As,i |] ≤ 2cm log n. Thus, by
Markov bound, we get Pri∈[m/2] [|As,i | ≥ 8cm log n] < 1/4 and Pri∈[m/2] [|As,i | < 8cm log n] >
3/4.
Now for any i ∈ [m/2] and J = {{j1 }, . . . , {jm/2 }}, m/2+1 ≤ j1 < j2 < · · · < jm/2 ≤ n we
define the set of graphs GJ,i (V, EJ,i ) where EJ,i := {{i}×([m/2]\{i})∪{{i, j1 }, . . . , {i, jm/2 }} | m/2+
1 ≤ j1 < j2 < · · · < jm/2 ≤ n}. Notice that any query Q in As \As,i gives no information about
the vertices j1 , . . . , jm/2 . That is because, either i 6∈ Q and then the answer is “NO” or i ∈ Q and
Q ∩ ([m/2]\{i}) 6= ∅ and then the answer is “YES”.
We now give an algorithm B that learns m/2-Loop over n − m/2 vertices that are labeled with
{m/2, . . . , n} with success probability at least 1/2 using at most 4cm log n queries. This gives a
contradiction to the result of Lemma 3 and then the result follows.
Algorithm B chooses a random uniform i ∈ [m/2] and runs algorithm A. Suppose the set
of m/2 loops of the target is J = {{j1 }, . . . , {jm/2 }}. The goal of algorithm B is to provide A
answers to its queries as if the target is GJ,i . Therefore, for each query Q that A asks, if i 6∈ Q then
algorithm B returns the answer “NO” to A and if i ∈ Q and Q ∩ ([m/2]\{i}) 6= ∅ then it returns
the answer “YES”. If Q ∩ [m/2] = {i} then algorithm B asks the query Q ∪ {i} and returns the
answer to A. Algorithm B halts if the number of queries is more than 8cm log n or A outputs a
0
graph H(V, E 0 ). If E 0 = {i} × ([m/2]\{i}) ∪ {{i, j10 }, . . . , {i, jm/2
}} then algorithm B outputs
0
0
G(V, {{j1 }, . . . , {jm/2 }}) otherwise it returns an empty graph.
6

L EARNING G RAPH

Algorithm
Learning the neighbours of v in the independent set I
1.
2.
3.
4.
5.
6.
7.

N =I
Repeat t times
Choose a random Q ⊆ I
where for every u ∈ I, Pr[u ∈ Q] = p.
Answer← OG (Q ∪ {v})
If Answer=“NO” then N ← N \Q
End Repeat
Output(N )

Figure 2: An algorithm that given an independent set I in V , finds the vertices in I that are neighbours of v.

Algorithm B fails if the number of queries is greater than 8cm log n or algorithm A fails. The
former happens with probability at most 1/4 and the latter with probability at most 1/4. Therefore
the error of the algorithm is at most 1/2.

4. Two and Three Round Randomized Learning - m is Known
In this section we study two-round randomized algorithms.
We first prove that there is a two-round Monte Carlo randomized learning algorithm (with
1/poly(n) error probability) for m-Graph that asks O(m4/3 log n) queries. Then we show that,
for n > mm , there is a two-round randomized Monte Carlo learning algorithm for m-Graph that
asks O(m log n) queries.
For Las Vegas algorithm we prove the above query complexities for three-round algorithms. We
then show that any two-round Las Vegas algorithm must ask at least Ω((m4/3 log1/3 n)/(log1/3 m))
queries. For m > (log n)ω(1) this lower bound is Ω(m4/3−o(1) log n).
4.1. Learning the Neighbours in an Independent Set
Lemma 4 Consider the Algorithm in Figure 2. Let I ⊂ V be an independent set in G. Let v 6∈ I
be a vertex in G. For p = 1/m and t = 4m(ln n + ln(1/δ)) with probability at least 1 − δ the
output N of the algorithm satisfies N = Γ(v) ∩ I. That is, N contains only the neighbours of v in
I.
Proof The output N is not the set of neighbors of v if and only if for some u 6∈ Γ(v) each query Q
in the algorithm satisfies: u 6∈ Q or Γ(v) ∩ Q 6= ∅. Therefore, the probability that output N is not
the set of neighbors of v is less than


1 t
m t
≤ δ.
n(1 − p(1 − p) ) ≤ n 1 −
4m
7

L EARNING G RAPH

4.2. Upper Bound for Randomized Two-Round Algorithm
√
Consider the algorithm in Figure 1 with p < 1/(8 m) and r = 1/(2p). By Lemma 2, E ⊆ E(H)
and for t = O((1/p)2 (log n + log(1/δ))), with probability at least 1 − δ, every edge {u, v} ∈
E(H)\E satisfies degG (u) + degG (v) > r + 1. Assume for now that this is true with probability
1.
Fact 1 Every edge {u, v} ∈ E(H)\E satisfies degG (u) + degG (v) > r + 1.
Figure 4 (in the appendix section) help you to follow the proof. Let VG := {v|{u, v} ∈ E},
VH := {v|{u, v} ∈ E(H)}. We partition the set of edges E(H)\E to three disjoint set E0 ∪E1 ∪E2
where Ei = {{u, v} ∈ E(H)\E : |{u, v} ∩ VG | = i}. Fact 1 immediately implies that
Fact 2 E0 = ∅. That is, every edge in E(H)\E, at least one of its endpoints is in VG .
Let u ∈ VH \VG . Then degG (u) = 0. Therefore, by Fact 1,
Fact 3 For any edge {u, v} ∈ E1 where u ∈ VH \VG we have degG (v) > r + 1.
Since the number of vertices in G that have degree greater than r + 1 is less than 2m/(r + 2) ≤ r/8,
the degree of each u ∈ VH \VG in the graph H is at most r/8.
Fact 4 If u ∈ VH \VG then degH (u) ≤ r/8. In particular, all the vertices of degree greater than
r/8 are in VG .
Now take any edge {u0 , v 0 } ∈ E(H)\E. By Fact 1, degG (u0 ) + degG (v 0 ) > r + 1 and therefore
either degG (u0 ) > r/2 or degG (v 0 ) > r/2. If degG (v 0 ) > r/2 then degH (v 0 ) > r/2 and by Fact 4,
v 0 ∈ VG . This with Fact 3 shows that
Fact 5 Every edge {u0 , v 0 } ∈ E2 , one of its endpoints is in VG and has degree at least r/2 in G
and therefore also in H.
Every edge {u0 , v 0 } ∈ E1 has one endpoint in VG , and a degree greater than r + 1 in G and
therefore also in H.
Denote by W the set of all vertices of degree greater than r/2 in H. Then
Fact 6 The number of vertices of degree more than r/2 in H is at most 8m/r. That is, |W | ≤
8m/r.
Proof Let u be a vertex in G of degree less than r/4. Then all its edges in H are in E2 ∪ E. This is
because if it has an edge in E1 then by Fact 5, its degree in G is more than r + 1. If {u, v} ∈ E2
then by Fact 5 the degree of v in G is at least r/2. Since the number of vertices in G of degree at
least r/2 is at most 2m/(r/2) < r/4 the degree of u in H is less than r/4 + r/4 = r/2. This shows
that a vertex in H of degree at least r/2 is of degree at least r/4 in G. Therefore the number of such
vertices is at most 2m/(r/4) = 8m/r.
We now prove
8

L EARNING G RAPH

Fact 7

8m2
.
r

|E2 | ≤

Proof By Fact 5, one of its endpoint vertices of an edges in E2 is in VG and has degree at least r/2
in G. There are at most 4m/r such vertices and each one can have at most |VG | ≤ 2m edges.
Now define for every vertex w ∈ W the set Iw that contains all the neighbours u ∈ ΓH (w)
where degH (u) ≤ r/8 and ΓH (u) ∩ ΓH (w) contains only vertices of degree more than r + 1 in H.
Fact 8 Iw is an independent set.
Proof If Iw contains {u, v} ∈ E(H) then degH (u), degH (v) < r/8. Since ΓH (u) ∩ ΓH (w)
contains v, we get degH (v) > r + 1. This gives a contradiction.
We now show
Fact 9 We have
E1 ⊆ EW :=

[

{{w, u} | u ∈ Iw }

w∈W

Proof If {w, u} ∈ E1 then, by the definition of E1 and Fact 5 and 4, one of the vertices, say w, is
in VG and is in W and the other vertex, u, is in VH \VG and has degree at most r/8 in H. Now we
show that u ∈ Iw . If u 6∈ Iw then ΓH (u) ∩ ΓH (w) contains a vertex v of degree less or equal to
r + 1. If v ∈ VH \VG then {u, v} is an edge in E0 and we get a contradiction to Fact 2. Therefore
v ∈ VG then since {v, u} is an edge in E1 and degH (u) ≤ r/8 we must have degH (v) ≥ r + 1 and
again we get a contradiction.
Since U := E(H)\EW ⊆ E ∪ E2 , by Fact 7, we get
Fact 10

8m2
.
r
Therefore, we first find W and for each w ∈ W learns the neighbours of w in Iw . This eliminates
all the edges of w that are not in the graph. In particular, it removes all the edges in E1 and some of
those in E2 . Then for each edge in U = E(H)\EW we ask a query.
We now can prove
|U | = |E(H)\EW | ≤ m +

Theorem 3 There is a two-round Monte Carlo randomized learning algorithm with 1/poly(n)
error probability for m-Graph that asks O(m4/3 log n) queries.
There is a three-round Las Vegas randomized learning algorithm for m-Graph that asks O(m4/3 log n)
expected number of queries.
Proof Consider the First round in Figure 1 and the second round in Figure 3. We choose p = 1/m2/3
and δ = 1/poly(n). Then r = m2/3 /2 and t = O(m4/3 log n).
By Fact 6, |W | ≤ 8m/r. By Lemma 4 finding the neighbours of each w ∈ W takes O(m log n)
queries. Therefore the total number of queries for steps 1-5 in the algorithm is O((m2 /r) log n) =
O(m4/3 log n). By Fact 10 the number of queries in steps 6-8 is at most m + 8m2 /r = O(m4/3 ).

9

L EARNING G RAPH

Algorithm
Learn Second Round
1.
2.
3.
4.
5.
6.
7.
8.
6.

W = {u | {u, v} ∈ E(H) and deg(u) > r/2}; U = E(H)\EW .
For every w ∈ W do
Learn the Neighbours of w in the independent set Iw
Let Nw be the output.
Remove from E(H) all {u, w} where w ∈ Iw \Nw .
For every {u, v} ∈ U
Answer← OG ({u, v})
If Answer=“NO” then E(H)\{{u, v}}.
Output(H = (V, E(H)))

Figure 3: Second Round in the Algorithm.
4.3. Randomized Three Rounds Monte Carlo Algorithm
In this section we show that when m is known to the algorithm then there is a three-round Monte
Carlo algorithm that asks O(m log n) queries.
In Angluin and Chen (2008), Angluin and Chen gave a three-round Monte Carlo randomized
√
algorithm that asks O(m log n + m log2 n) queries. We give here a three-round algorithm that
asks O(m log n + m1.5 ) queries. Both results imply
Theorem 4 There is a three-round Monte Carlo randomized learning algorithm with 1/poly(n)
error probability for m-Graph that asks O(m log n) queries.
There is a four-round Las Vegas randomized learning algorithm for m-Graph that asks O(m log n)
expected number of queries.
√
Proof If m ≥ log2 n then O(m log n + m log2 n) = O(m log n). Otherwise, m < log2 n and
then O(m log n + m1.5 ) = O(m log n).
Now we describe the algorithm. In the first round we run the algorithm in Figure 1 with p =
√
√
1/(16 m). By the facts in Section 4.2, for r = 8 m we have
√
1. All the edges {u, v} ∈ E(H)\E satisfies degG (u) + degG (v) > 8 m + 1.
√
2. E0 = ∅, |E2 | ≤ m1.5 + 1, E1 ⊂ EW , |W | ≤ m and |E(H)\EW | ≤ m1.5 + m + 1.
In the first round we ask O(1/p2 )(log n + log(1/δ)) = O(m log n) queries. Now for each w ∈ W
we need to find the neighbors ΓG (w) ∩ Iw of w in G. If we do that using the previous algorithm
we get O(m1.5 log n) queries. Instead, we will add another round that estimates the number of
neighbours of each w ∈ W in G (and in Iw ). We then learn the neighbour with O(degG (w) log n).
This is possible because Iw is ab independent set. The estimation can be done by doubling and
estimating with Chernoff bound. See Falahatgar et al. (2016). The estimation can be done with
O(log m log n) queries for each w ∈ W and success probability 1 − 1/poly(n) and therefore with
√
O(|W | log m log n) = O( m log m log n) queries. Then since |E(H)\EW | ≤ 2m1.5 + m + 1
10

L EARNING G RAPH

finding the other edges in the graph can be done in (round 2 or 3) with O(m1.5 ) queries. The total
number of queries is O(m log n + m1.5 ).
4.4. Two-Round Learning for Large n
In this section we prove
Theorem 5 Let w > m. There is a two-round randomized Monte Carlo learning algorithm with
1/wO(1) error probability for m-Graph that asks O(m2 log w + m log n).
In particular, when w = nc/m for any constant c (and therefore m < log n) the algorithm asks
O(m log n) queries.
Proof We first partition the set of vertices into u = poly(w) sets V1 , . . . , Vu . The probability that
each set contains at most one vertex of degree not equal zero is at least





1
2
2m − 1
m(2m − 1)
1
1−
(1)
1−
··· 1 −
≥1−
≥ 1 − O(1) .
u
u
u
u
w
Assuming the vertices that have degree greater than zero are in different sets, we learn the graph
over the u sets in one round with probability at least 1 − 1/wO(1) and O(m2 log u) = O(m2 log w)
queries using Theorem 1. That is, we assume that each set Vj is one vertex and we learn the graph
over the sets V1 , . . . , Vu . Then, for each query Q ⊆ [u] the algorithm asks the query ∪w∈Q Vw .
When the algorithm discover an edge {Vi , Vj } then it knows that there is an edge between one of
the vertices in Vi with one of the vertices in Vj . We will call the edge {Vi , Vj } a set edge and Vi a
set vertex.
Now, suppose there is a set of edges e with the set of endpoints vertices Vi and Vj . We can learn
the endpoints vertices of e deterministically with O(log n) queries. To learn the endpoint in Vj the
algorithm considers Vi as one vertex and runs the algorithm that learn 1-Loop in Vj . That is, for
each query Q ⊆ Vj the algorithm asks the query Vi ∪ Q. Therefore, in the second round, we can
deterministically learn the endpoints of all the edges in O(m log n) queries.
We now convert the above algorithm to a three-round Las Vegas algorithm.
We first give one definition and a lemma. For a query Q and a vertex u we define [u ∈ Q] = 1
if u ∈ Q and [u ∈ Q] = 0 if u 6∈ Q. We now prove
Lemma 5 There is a non-adaptive deterministic algorithm that asks O(log n) queries and if the
target is 0-Loop or 1-Loop then it learns the target and if it is k-Loop, k > 1, then it returns an
“ERROR”.
Proof We define the set of 2t queries {Q1 , . . . , Q2t } as follows. Each vertex i appears in exactly t
queries and no two vertices appears in the same set of queries. We must have 2tt ≥ n and therefore
it is enough to take 2t = log n + 2 log log n = O(log n).
Now if the target is 0-Loop then the vector of answers is ([i ∈ Q1 ], . . . , [i ∈ Q2t ]) is the
zero vector. If the target is 1-Loop, {i}, then the vector of answers is ([i ∈ Q1 ], . . . , [i ∈ Q2t ])
which uniquely determines i. This vector contains t ones and t zeros. When the target is k-Loop,
L = {{i1 }, . . . , {ik }}, k > 1, then the vector of answers is ∨kj=1 ([ij ∈ Q1 ], . . . , [ij ∈ Q2t ])
(bitwise or) which contains at least t + 1 ones. This indicates that the target is a k-Loop for some
k > 1.

11

L EARNING G RAPH

Theorem 6 There is a three-round randomized Las Vegas learning algorithm for m-Graph that
asks O(m2 log m + m log n) expected number of queries.
In particular, when n ≥ mm , the algorithm asks O(m log n) queries.
Proof We run the algorithm in the proof of Theorem 5 but in the second round we use the algorithm
in Lemma 5 for learning the endpoints vertices. If the algorithm fails at some round we run the
deterministic algorithm that asks O(m3 log n) queries in the third round. We now give more details.
We first partition the set of vertices into u = 2m4 (2m − 1) sets V1 , . . . , Vu . By (1), the probability that each set contains at most one vertex of degree not equal zero is at least 1 − 1/m3 .
Assuming success, by the proof of Theorem 1, the first round finds all the edges and an expected of
1/poly(u) more edges that are not in the target. The edges that are not eliminated are found by the
deterministic algorithm in the second round.
Suppose the first round fails to distribute the vertices of degree not equal zero in different sets.
We show how to discover that in the second round. We distinguish between two cases: The first
case is when there is an edge {u, v} where {u, v} ⊆ Vi for some i. The second case is when there is
no edge between two vertices in the same set but there is at least two nodes u and v of degrees not
equal to zero in the same set Vi . One of those two cases happens with probability less than 1/m3 .
If the first case happens, the algorithm in the first round will not be able to eliminate any of the
set edges {Vi , Vj } for all Vj . This is because when the set vertex Vi is in the query the answer is
always “YES”. Therefore, at the end of the first stage, there will be at least u > m set edges that are
not eliminated. That is, all the set edges {Vi , Vj } for all Vj . Then the algorithm knows that the first
case happens and it runs the deterministic algorithm that asks m3 log n queries in the second round.
Now suppose the second case happens. Suppose Vj contains two vertices v1 and v2 of non-zero
degree (with no edge between them). Let {u1 , v1 } and {u2 , v2 } be two edges in G. We here again
distinguish between two subcases. The first subcase is when u1 , u2 ∈ Vk , k 6= j. The second
subcase is when u1 ∈ Vk1 and u2 ∈ Vk2 , and k1 , k2 , j are distinct. In the first subcase, when the
algorithm consider the set Vk as one vertex and runs the algorithm in Lemma 5, the algorithm output
“ERROR” and then it knows that this subcase happens. In the second subcase, when the algorithm
consider the set Vk1 as one vertex and runs the algorithm in Lemma 5, it learns v1 and when the
algorithm consider the set Vk2 as one vertex it learns v2 6= v1 . Then the algorithm knows that
the second subcase happens. When the second case happens the algorithm runs the deterministic
algorithm that asks m3 log n queries in the third round.
The expected number of queries is


1
1
1 − 3 (m2 log u + m log n) + 3 m3 log n = O(m2 log m + m log n).
m
m

4.5. Lower Bound for Las Vegas Randomized Algorithm
In this section we prove
√
Theorem 7 Let log n < m = o( n). Any two-round Las Vegas learning algorithm for m-Graph
must ask at least
!
m4/3 log1/3 n
Ω
log1/3 m
12

L EARNING G RAPH

queries on average.
Proof Let A be a two-round Las Vegas learning algorithm for m-Graph. Notice that since the
algorithm succeeds with probability 1, the second round must be deterministic.
We define a distribution D over the targets as follows: we first choose r = m/2 (fixed) distinct
vertices V 0 = {v1 , . . . , vr }. Then randomly and uniformly choose 1 ≤ t ≤ r. Then randomly
uniformly choose s = m/2 − d distinct vertices U = {u1 , · · · , us } where U ∩ V 0 = ∅ and
d = (m2/3 log1/3 m)/(210 log1/3 n). Then randomly uniformly choose d (not necessarily distinct)
vertices W = {w1 , . . . , wd } ⊆ V \(V 0 ∪ U ). Then define the target
T = {{vt , vj } | j 6= t; j = 1, . . . , r} ∪ {{vt , uj }, {vt , wk } | j = 1, . . . , s; k = 1, . . . , d}.
Now let XA (y, OI ) be a random variable that is the number of queries asked by the algorithm A with a seed y and target I. If for any deterministic two-round algorithm B we have
EI∈D [XB (OI )] ≥ q where XB (OI ) is the number of queries asked by B then EI∈D [XA (y, OI )|y] ≥
q and then the query complexity of A is
max Ey [XA (y, OI )] ≥ EI∈D Ey [XA (y, OI )] = Ey EI∈D [XA (y, OI )|y] ≥ Ey [q] = q.
I

Therefore, what remains to prove is that for any two round deterministic algorithm B we have
EI∈D [XB (OI )] ≥ q.
Consider the first round of B with q = (m4/3 log1/3 n)/ log1/3 m queries Q1 , . . . , Qq . Consider
the set of queries Si = {Qi | Qi ∩ V 0 = {vi }} for i = 1, . . . , r. Then rEi [|Si |] ≤ q and therefore
at least 7/8 of the i ∈ [s] satisfies |Si | ≤ 8q/r. Therefore, with probability at least 7/8 we have
|St | ≤ 8q/r. Suppose we have chosen such t and after the first round we provide the algorithm vt .
Therefore, the algorithm only needs to learn U and W . We will show next that after the first round
even if we provide the learner U there will still be many vertices about which no information is
known, with high probability, W .
For the ease of notation we write Q(I) = 1 if Q ∩ I 6= ∅ and 0 otherwise. Now every query
Qi that satisfies Qi ∩ V 0 6= {vt } will give no information about ui or wi . Therefore, the queries
that are relevant to learning are only the queries in St . Let St = {Q01 , . . . , Q0` }. Since ` = |St | ≤
8q/r, the algorithm can get at most 2` ≤ 28q/r possible answers. For each vector of ` possible
answers a = (a1 , . . . , a` ) ∈ {0, 1}` to the queries in St we define Ia = {I ⊆ V \V 0 : |I| =
s, (Q01 (I), . . . , Q0` (I)) = a}. Let U ∈ Ia0 , i.e., (Q01 (U ), . . . , Q0` (U )) = a0 . Since



n−r
X
X
n−r
s
T :=
|Ia | =
,
|Ia | ≤
,
s
8
`
`+3
a,|Ia |≤T /2

a∈{0,1}

with probability at least 7/8, |Ia0 | ≥ T /2`+3 . Suppose the latter statement is true with probability
1. Let Za0 = ∪I∈Ia0 I. Notice that for every w ∈ Za0 there is I ∈ Ia0 such that w ∈ I and
therefore (bitwise) (Q01 (w), . . . , Q0` (w)) ≤ (Q01 (I), . . . , Q0` (I)) = a0 which implies that if (Q01 (U ∪
W ), . . . , Q0` (U ∪W )) = a0 no information is known about the vertices in Za0 after the first round. If
this happen then there are |Za0 | vertices where no information is known about them. We next prove
that with high probability W ⊆ Za0 and therefore (Q01 (U ∪ W ), . . . , Q0` (U ∪ W )) = a0 . Then in
the next round we must run a deterministic algorithm that learns the d vertices W in Za0 . This, by
Lemma 9, requires at least
d2 log |Za0 |
log d
13

(2)

L EARNING G RAPH

queries.
Now we estimate |Za0 | and prove that with high probability we have W ⊆ Za0 . We have



n−r
s(s − 1)
T
(n − r)s
s
1−
|Ia0 | ≥ `+3 ≥ `+3 ≥ `+3
.
2(n − r)
2
2
2 s!
On the other hand



|Za0 |
|Za0 |s
|Ia0 | ≤
≤
.
s
s!

Therefore,
n−r
|Za0 | ≥ (`+3)/s
2



s(s − 1) 1/s
n
1−
= (`+3)/s (1 − o(n)).
2(n − r)
2

The probability that |W | = d and W ⊆ Za0 is at least



d(d − 1)
|Za0 | − s d
1
7
1−
≥ (`+3)d/s (1 − o(1)) ≥ .
n−r−s
n−s−r
8
2
Therefore, if we provide the algorithm U after the first round, with probability at least 7/8 no
information is known about W . All the above is true with probability at least 1/2. By (2), in the
second round the algorithm needs to ask at least
!
d2 log |Za0 |
m4/3 log1/3 n
=Ω
log d
log1/3 m
queries.

5. Deterministic Algorithms when m is Known
In this section we study deterministic algorithms for learning m-graph when m is known. It
is known that any non-adaptive deterministic algorithm must ask at least Ω((m3 log n)/ log m),
D’yachkov and Rykov (1983), and there is a polynomial time non-adaptive algorithm that asks
O(m3 log n), Bshouty (2015). In this section we prove (non-constructively) that there is a tworound algorithm that asks O(m2 log n) queries and then give the lower bound Ω((m2 log n)/ log m)
for the number of queries. Finally, we give a four-round deterministic algorithm that asks O(m2+ log n)
queries for any constant .
5.1. Nonconstructive Upper Bound for Two-Round Deterministic Algorithm
We first prove the following three results.
Lemma 6 Let E = {e1 , . . . , et } be a set of edges. Let Q ⊆ V be a random query where for each
vertex i ∈ V , i is included in Q independently with probability p. Then
Pr[(∃i ∈ [t])ei ⊆ Q] ≥ p · (1 − (1 − p)t ).

14

L EARNING G RAPH

Proof Define the event Ak,j = [(∃i ∈ [k, j])ei ⊆ Q]. We prove the result by induction on t. For
t = 1 we have one edge e and Pr[e ⊆ Q] = p2 ≥ p · (1 − (1 − p)1 ). Let u ∈ e1 . Assume w.l.o.g
that u ∈ ei for i ∈ [`] and u 6∈ ei for i ∈ [` + 1, t]. Define the event B = [(∃i ∈ [`])(ei \{u}) ⊆ Q].
Then, by the induction hypothesis,
Pr[A1,t ] = Pr[u ∈ Q] Pr[A1,t |u ∈ Q] + Pr[u 6∈ Q] Pr[A1,t |u 6∈ Q]
= p Pr[B ∨ A`+1,t ] + (1 − p) Pr[A`+1,t ]
≥ p Pr[B] + (1 − p)p(1 − (1 − p)t−` )
= p(1 − (1 − p)` ) + (1 − p)p(1 − (1 − p)t−` )
= p(1 + (1 − p)(1 − (1 − p)`−1 ) − (1 − p)t−`+1 )
≥ p(1 + (1 − p)t−`+1 (1 − (1 − p)`−1 ) − (1 − p)t−`+1 )
= p · (1 − (1 − p)t ).

Lemma 7 Let E = {e1 , . . . , er } and E 0 = {e01 , . . . , e0t } be two disjoint sets of edges. Let Q ⊆ V
be a random query where for each vertex i ∈ V , i is included in Q independently with probability p.
Then
Pr[(∀i ∈ [r]) ei 6⊆ Q | (∃j ∈ [t])e0j ⊆ Q] ≥ (1 − p)r .
Proof The proof is by induction on the number of edges in E. Define the events B = [(∀i ∈
[r]) ei 6⊆ Q] and A = [(∃j ∈ [t])e0i ⊆ Q]. Assume w.l.o.g u ∈ ei for i ∈ [`], u 6∈ ei for
i ∈ [` + 1, r], u ∈ e0i for i ∈ [`0 ] and u 6∈ e0i for i ∈ [`0 + 1, t]. Here, ` ≥ 1 and `0 ≥ 0. Then
Pr[B|A] ≥ Pr[u 6∈ Q] · Pr[B|A and u 6∈ Q] = (1 − p) · Pr[B|A and u 6∈ Q]. If u 6∈ Q then ei 6⊆ Q
for all i ∈ [`] and then B = B 0 := [(∀j ∈ [` + 1, r])ej 6⊆ Q]. Also, e0i 6⊆ Q for all i ∈ [`0 ] and
the event [A and u 6∈ Q] is equivalent to [(A0 and u 6∈ Q)] where A0 := [∃i ∈ [`0 + 1, t]) e0i ⊆ Q].
Therefore Pr[B|A] = Pr[B 0 |A0 ]. By the induction hypothesis Pr[B 0 |A0 ] ≥ (1−p)r−` and therefore
Pr[B|A] ≥ (1 − p)r−`+1 ≥ (1 − p)r .
Lemma 8 Let G = (V, E) be the target graph with n vertices and m edges. Let Q ⊆ V be a
random query where for each vertex i ∈ V , i is included in Q independently with probability p. Let
e01 , . . . , e0t 6∈ E. Suppose the probability that there is i ∈ [t] such that e0i ⊆ Q is at least q. Then
Pr[(∃i ∈ [t]) e0i ⊆ Q and OG (Q) = “NO”] ≥ q(1 − p)m .
In particular,
Pr[(∃i ∈ [t]) e0i ⊆ Q and OG (Q) = “NO”] ≥ p · (1 − (1 − p)t )(1 − p)m .
Proof Let A := [(∃i ∈ [t]) e0i ⊆ Q]. Let E = {e1 , . . . , em }. Then the event OG (Q) = “NO” is
equivalent to the even B := [(∀j ∈ [m])ej 6⊆ Q]. Now by Lemma 6 and 7 we have
Pr[A and B] = Pr[A] · Pr[B|A] ≥ q(1 − p)m ≥ p · (1 − (1 − p)t )(1 − p)m .

We are now ready to prove our main result
15

L EARNING G RAPH

Theorem 8
There is a two-round deterministic learning algorithm for m-Graph that asks t = O(m2 log n)
queries.
Proof We will first show that there is a set of t queries Q1 , . . . , Qt that satisfies: For every graph
G = ([n], E = {e1 , . . . , em }) with m edges and for every set of m edges E 0 = {e01 , . . . , e0m } not in
G, there is a query Qj such that OG (Qj ) = “NO” and (∃i ∈ [m]) e0i ⊆ Qj .
Choose Q1 , . . . , Qt where each Qj ⊆ V is a random query where for each vertex i ∈ [n], i is
included in Q independently with probability 1/m. By Lemma 8, probability that above event is
not true for some graph G is at most
 n2 


 
 t
1
1 m
1 m
2
1−
1− 1−
1−
.
m
m
m
m
This is less than 1 for t = O(m2 log n). Therefore there are such queries.
In the first round, the algorithm defines E(H) = {{u, v}|u, v ∈ V, u 6= v} and asks all the
queries Q1 , . . . , Qt . For each query Qj with answer “NO” it eliminates from E(H) all the pairs
{u0 , v 0 } where u0 , v 0 ∈ Qj .
We now show that E(H) contains at most 2m edges. Assume for the contrary that E(H)
contains 2m + 1 edges. Take E 0 ⊆ E(H)\E of size m. There is a query Qj such that OG (Qj ) =
“NO” and (∃e ∈ E 0 ) e ⊆ Qj . This gives a contradiction. Now in the second round the algorithm
asks a query for each edge in E(H).

5.2. Lower Bound for Two-Round Deterministic Algorithm
In this subsection we give a lower bound. We first give two known facts from D’yachkov and Rykov
(1983); Füredi (1996).
Lemma 9 Any deterministic nonadaptive learning algorithm for m-Loop must ask at least Ω((m2 / log m) log n)
queries.
Lemma 10 Let Q be a set of queries that satisfies: for every set S ⊂ [n] of size m and every i ∈ S
there is a query Q ∈ Q such that S ∩ Q = {i}. Then |Q| = Ω((m2 / log m) log n).
We now prove
Theorem 9 Any two-round deterministic learning algorithm for m-Graph must ask at least Ω((m2 / log m) log n)
queries.
Proof Suppose there is a deterministic two-round deterministic learning algorithm for m-Graph
that asks t = o((m2 / log m) log n) queries. Let Q1 , . . . , Qt be the queries in the first round. Since
t = o((m2 / log m) log n), by Lemma 10, there must be a set of bm/2c elements S ⊆ [n] and
i ∈ S such that no query Qj satisfies S ∩ Qj = {i}. The adversary defines a set of bm/2c edges
E 0 = {{i, j} | j ∈ S\{i}}. The other dm/2e edges E 00 = {{i, j} | j ∈ S 0 , S 0 ⊆ [n]\S} will be
determined in the second round. The answers of the queries in the first round are determined only
by the edges E 0 . That is, if |Qj ∩ S| > 1 and i ∈ Qj then the answer is “YES”, and if i 6∈ Qj then
the answer is “NO”. After the first round no information is known about S 0 .
16

L EARNING G RAPH

In the second round we need to learn S 0 from queries Q that contain i. Otherwise, the answer is
“NO”and no information is gained about S 0 . When i ∈ Q then the problem is equivalent to learning
dm/2e-Loop, and by Lemma 9 we must ask at least Ω((m2 / log m) log n) queries.

5.3. Deterministic Five-Round Algorithm
In this section we give a deterministic five-round algorithm that asks O(m2+ log n) queries.
In the first round the algorithm finds a partition of [n] to w = O(m) sets S1 , . . . , Sw where no
edge of the target has both endpoint vertices in the same set. In the second round it learns the pairs
of sets {Si , Sj } for which there is an edge with one endpoint in Si and the other in Sj . In the third
and fourth rounds it finds the vertices in each set that are endpoints of some edge. Then in the fifth
round it learns the edges.
For the first round we use the following result from Bshouty (2015).
Lemma 11 There is a linear time algorithm that for every n and m constructs a t × n-matrix,
t = O(n log m), M with entries in [w], w = O(m), with the following property: Every two
columns in M are equal in at most t/(2m) entries.
We now prove
Lemma 12 Let M be the matrix in Lemma 11. There is a row vector u ∈ [w]n in M such that in the
partition {Su,1 , . . . , Su,w } of [n] where Su,i = {j|uj = i} no edge of the target has both endpoint
vertices in the same set.
Proof Let ei = {ui , wi }, i = 1, . . . , m be the edges of the target. By Lemma 11, there is at most
t/(2m) entries in columns ui and wi in the matrix that are equal. Therefore, there is at least one
entry (actually, at least t/2 entries) such that for all i = 1, . . . , m, columns ui and wi in the matrix
are not equal in that entry. This implies the result.
To know this row, for each row u in M and for each j ∈ [w], the algorithm asks the query OG (Su,j ).
Obviously, if no edge of the target has both endpoint vertices in the same set then the answers are
zeros for all j ∈ [w]. The number of queries in this round is wt = O(m2 log n).
After the first round we have a partition of [n] to w = O(m) sets S1 , . . . , Sw where no edge
of the target has both endpoint vertices in the same set. In the second round we ask the query
OG (Si ∪ Sj ) for all i 6= j. If OG (Si ∪ Sj ) = 1 then the algorithm knows that there is an edge
with one endpoint in Si and the other in Sj . Since w = O(m), this takes O(m2 ) queries. If
OG (Si ∪ Sj ) = 1 then we call {Si , Sj } a set edge. Obviously, there are at most m set edges.
In the third and fourth rounds, the algorithm runs Cheraghchi’s two-round algorithm, Cheraghchi (2013), to find the vertices in each Si that are endpoints of some edge. This algorithm is a
two-round algorithm for m-Loop. It asks O(m1+ log n) queries for any constant . We use Cheraghchi’s algorithm as follows: if {Si , Sj } is a set edge then each query Si ∪ (Q ∩ Sj ) for the graph
is the query Q ∩ Sj for the m-Loop that contains the vertices in Sj that are endpoints of the edges.
Therefore, running Cheraghchi’s two-round algorithm for each set edge {Si , Sj } gives all the vertices that are endpoints of some edge in the cut (Si ; Sj ). Since the number of edge sets is at most m
this takes O(m2+ log m) queries.
In the fifth stage the algorithm exhaustively asks a query about each possible pair. That is, if for
the edge set {Si , Sj } we have learned that V1 ⊆ Si and V2 ⊆ Sj are the endpoints of some edge in
17

L EARNING G RAPH

the cut (Si ; Sj ), then we ask the queries OG ({v1 , v2 }) for each v1 ∈ V1 and v2 ∈ V2 . This takes at
most m2 /2 = O(m2 ) queries.
The above algorithm implies
Theorem 10 There is a five-round deterministic learning algorithm for m-Graph that asks O(m2 log n)
queries.

6. Unknown m - Upper Bounds
In this section we prove two results when m is not known to the learner.
Here log[0] n = n and log[k] n = log log[k−1] n. When we say w.h.p (with high probability) we
mean with probability at least 1 − 1/poly(n).
Theorem 11 For every constant k > 1 there is an O(1)-round Las Vegas randomized learning
√
algorithm for m-Graph that asks O(m log n + m(log[k] n) log n) queries.
Theorem 12 There is a (log∗ n)-round Las Vegas randomized learning algorithm for m-Graph
that asks O(m log n) queries.
We recall Chernoff Bound
Lemma 13 (Chernoff Bound). Let X1 , . . . , Xt be independent random variables that takes values
in {0, 1}. Let X = (X1 + · · · + Xt )/t and µ = E[X]. Then for any 0 < δ < 1,
Pr[|X − µ| ≥ δµ] ≤ 2e−δ

2 µt/3

,

and for any δ ≥ 1
Pr[X ≥ (1 + δ)µ] ≤ 2e−δµt/3 .
Let Q ⊆ V be a p-random query. Let NG (p) be the probability that OG (Q) = 0. It is easy to
see that (see Angluin and Chen (2008))
1 − mp2 ≤ NG (p) ≤ 1 − p2 .

(3)

Consider pi -random queries Qi for i = 1, 2. Then Q1 ∪ Q2 is a (p1 + p2 − p1 p2 )-random query.
Now
NG (p1 + p2 − p1 p2 ) = Pr[OG (Q1 ∪ Q2 ) = 0]
≤ Pr[OG (Q1 ) = 0 and OG (Q2 ) = 0]
= NG (p1 ) · NG (p2 ).
It is shown in Angluin and Chen (2008) that for any G the function NG (x) is continuous monotonic
decreasing function. Therefore
Lemma 14 For any 0 ≤ q1 < q2 ≤ 1 we have NG (q1 ) > NG (q2 ) and for any 0 ≤ p1 + p2 ≤ 1
we have
NG (p1 + p2 ) < NG (p1 + p2 − p1 p2 ) ≤ NG (p1 ) · NG (p2 ).
In particular, for any integer k ≥ 2
NG (kp) < NG (p)k .
18

L EARNING G RAPH

Let p∗ be such that NG (p∗ ) = 1/2. By (3) we have
1
1
√
≤ p∗ ≤ √ .
2m
2
Our first goal is to estimate p∗ . Consider the following procedure

(4)

Estimate(OG , M )
√
For each pi = 1/2i , i = 0, 1, 2, · · · , such that 2i ≤ 22.5 M
For t = Θ(log n) independent pi -queries Qi,1 , . . . , Qi,t do:
qi = (OG (Qi,1 ) + · · · + OG (Qi,t ))/t.
Choose the first p0 := pi0 /2 such that 1 − qi0 > 1/2.
If no such i0 exists then output(“m > M ”).
Otherwise output(p0 ) \ ? p∗ ≥ p0 ≥ p∗ /8 ? \.

1.
2.
3.
4.
5.
6.
We now show

Lemma 15 Let M ∈ [n] be any integer. The procedure Estimate(OG , M ), w.h.p, asks Θ((log M )(log n))
queries and either outputs p0 such that p∗ ≥ p0 ≥ p∗ /8 or proclaims that m > M .
Proof Let k be such that p∗ /2 < pk ≤ p∗ . Then pk−2 > 2p∗ and therefore, by Lemma 14, for all
i ≤ k − 2, NG (pi ) ≤ NG (pk−2 ) < NG (2p∗ ) < NG (p∗ )2 ≤ 1/4. Therefore, by Chernoff bound
(Xj = 1 − OG (Qi,j ), t = Θ(log n), µ = NG (pi ) ≤ 1/4 and δµ = 1/4)
Pr[i0 ≤ k − 2] ≤ Pr[(∃i ≤ k − 2) 1 − qi > 1/2] ≤ 1/poly(n).
Therefore, w.h.p i0 ≥ k − 1. Also pk+1 = pk /2 ≤ p∗ /2 and therefore, by Lemma 14, NG (pk+1 ) >
NG (p∗ /2) > NG (p∗ )1/2 > 0.7. Therefore, by Chernoff bound, (Xj = 1 − OG (Qk+1,j ), t =
Θ(log n), µ = NG (pk+1 ) ≥ 0.7 and δµ = 0.2)
Pr[i0 ≥ k + 2] ≤ Pr[1 − qk+1 < 1/2] ≤ 1/poly(n).
Therefore, w.h.p k − 1 ≤ i0 ≤ k + 1 and then 2p∗ ≥ pk−1 ≥ pi0 ≥ pk+1 ≥ p∗ /4. Therefore w.h.p
p∗ ≥ p0 = pi0 /2 ≥ p∗ /8.

√
0
0
Let i0 be such that 2i ≤ 22.5 M < 2i +1 . If i0 does not exist then w.h.p i0 ≤ k and therefore
by (4),
√
√
1
4
0
22.5 M < 2i +1 ≤ 2k+1 =
≤
= 4 2m
pk+1
p∗
and then m > M .
The following procedure estimates p∗ in k rounds
1.
2.
3.
4.
5.
6.

k-Estimate(OG )
For j = k − 1 downto 0
Mj ← (log[j] n)2 .
Estimate(OG , Mj )
If the output is p0 then Goto 6.
EndFor.
Output(p0 ) \ ? p∗ ≥ p0 ≥ p∗ /8 ? \.

19

L EARNING G RAPH

We now show
Lemma 16 The procedure k-Estimate(OG ) runs in k rounds and w.h.p asks
O((log[k] n)(log n) + m log n)
queries and outputs p0 such that p∗ ≥ p0 ≥ p∗ /8.
Proof For j = 0 we have M0 = (log[0] n)2 = n2 and since m < M0 the algorithm must stops and
output such p0 . It remains to prove the query complexity.
If Estimate(OG , Mk−1 ) returns p0 then, by Lemma 15, the algorithm w.h.p asks
Θ((log Mk−1 )(log n)) = Θ((log[k] n)(log n))
queries. Otherwise, m > Mk−1 . Let j be such that Mj+1 < m ≤ Mj . Then p0 is returned by some
Estimate(OG , Mj 0 ) where j 0 ≥ j. Therefore, by Lemma 15, w.h.p the number of queries is O of
k
X

p
(log Mi )(log n) ≤ 2(log Mj )(log n) = 4 Mj+1 log n ≤ 4m log n.

i=j

In particular,
Corollary 13 The procedure log∗ n-Estimate(OG ) runs in log∗ n rounds, w.h.p asks O(m log n)
queries and outputs p0 such that p∗ ≥ p0 ≥ p∗ /8.
The following is Lemma 4.1 in Angluin and Chen (2008)
Lemma 17 Suppose I is an independent set in G and let Γ(I) be the set of neighbors of the vertices
in I. For a p-random query Q we have
Pr[OG (Q) = 0 | I ⊆ Q] ≥ (1 − p)|Γ(I)| · NG (p) ≥ (1 − p)|Γ(I)| · (1 − mp2 ).
The following is Lemma 5.2 in Angluin and Chen (2008). We give the proof for completeness
Lemma 18 Let p∗ ≥ p0 ≥ p∗ /8. For any constant c0 there is a constant c such that: If {u, v} 6∈
E(G) and degG (u) + degG (v) ≤ c0 /p0 then for p0 -random query Q
Pr[OG (Q) = 0 and {u, v} ⊆ Q] ≥ cp02 .
√
0
Proof First notice that since p0 ≤ p∗ ≤ 1/ 2 we have (1 − p0 )1/p ≥ (1 − p∗ )1/p∗ ≥ 0.17. By
Lemma 17, the probability that OG (Q) = 0 and {u, v} ⊆ Q is equal to
0

0

Pr[{u, v} ⊆ Q] · Pr[OG (Q) = 0 | {u, v} ⊆ Q] ≥ p02 (1 − p0 )c /p NG (p0 )
0

≥ p02 (0.17)c NG (p∗ ) = cp02 .

We use Lemma 18 for the following
20

L EARNING G RAPH

Split(OG )
E(H) ← {{u, v} | u, v ∈ V, u 6= v}.
Choose t = Θ((1/p0 )2 log n) p0 -random queries Q1 , . . . , Qt
For each query Qi .
If OG (Qi ) = 0 then
For every u, v ∈ Qi do E(H) ← E(H)\{{u, v}}
EndFor.
V1 (H) ← {u ∈ V | degH (u) ≥ 3/p0 }, V2 (H) = V \V1

1.
2.
3.
4.
5.
6.
7.

Lemma 19 Let p∗ ≥ p0 ≥ p∗ /8. The procedure Split(OG ) asks at most O(m log n) queries and
w.h.p the following hold:
1. For all u, v ∈ V2 (H), {u, v} ∈ E(H) if and only if {u, v} ∈ E(G).
In particular,
2. If degG (u) ≤ 1/p0 and {u, v} ∈ E(H)\E(G) then degG (v) > 1/p0 .
Proof By (4), the number of queries is O((1/p02 ) log n) = O((1/p2∗ ) log n) = O(m log n).
If OG (Qi ) = 0 and u, v ∈ Qi then {u, v} is not an edge in G. Therefore, procedure Split(OG )
only removes edges in E(H) that are not in E(G). Therefore, if {u, v} ∈ E(G) then {u, v} ∈
E(H). Suppose u, v ∈ V2 (H) and {u, v} 6∈ E(G). Since degH (u), degH (v) < 3/p0 we also have
degG (u), degG (v) < 3/p0 . Therefore, by Lemma 18,
Pr[{u, v} ∈ E(H)] = Pr[(∀i) OG (Qi ) = 1 or {u, v} 6⊆ Q]
t
1
≤ 1 − cp02 =
.
poly(n)

The following is Lemma 5.4 in Angluin and Chen (2008). We give the proof for completeness
√
Lemma 20 Let p∗ ≥ p0 ≥ p∗ /8. There are at most 2/p0 ≤ 16/p∗ ≤ 16 2m vertices in G that
have degree more than 1/p0 .
Proof Suppose h vertices, v1 , . . . , vh , have degree more than 1/p0 . Let Q be a p0 -random query.
Then
1
2

= NG (p∗ ) ≤ NG (p0 ) = Pr[OG (Q) = 0]
= Pr[OG (Q) = 0 | (∃i)vi ∈ Q] · Pr[(∃i)vi ∈ Q]
+ Pr[OG (Q) = 0 | (∀i)vi 6∈ Q] · Pr[(∀i)vi 6∈ Q]
0

≤ (1 − p0 )1/p (1 − (1 − p0 )h ) + (1 − p0 )h
0

≤ e−1 + (1 − e−1 )(1 − p0 )h ≤ e−1 + (1 − e−1 )e−p h .
Therefore h ≤ 2/p0 .

21

L EARNING G RAPH

Lemma 21 Let V3 = {v ∈ G | degG (v) ≥ 1/p0 }. √
Then w.h.p V1 (H) ⊆ V3 .
In particular, w.h.p |V1 (H)| ≤ |V3 | ≤ 1/p0 ≤ 8 2m.
Proof CHECK AGAIN If v 6∈ V3 then degG (v) < 1/p0 . Now if {u, v} is an edge in H but not in
G then by Lemma 19, deg(u) ≥ 1/p0 . Since by Lemma 20 the number of vertices of degree more
than 1/p0 is less than 2/p0 we have degH (v) < degG (v) + 2/p0 ≤ 3/p0 . Therefore v 6∈ V1 (H).
Therefore, it remains to learn the edges of the vertices in V1 (H). Since V1 (H) ⊆ V3 we have
that
Lemma 22 For every v ∈ V1 (H), dv := degG (v) ≥ 1/p0 .
This is one of the main properties that we will use in the sequel.
Let Q be a p-random query and u ∈ V be a vertex of degree du ≥ 1/p0 . Let Nu,G (p) be
the probability that OG (Q ∪ {u}) = 0. As before, Nu,G (p) is monotonically decreasing and
Nu,G (kp) ≤ Nu,G (p)k . Let pu be the probability such that
Nu,G (pu ) = e−1 .

(5)

Next, we show that estimating pu implies estimating du . Since
e−1 = Nu,G (pu ) ≤ (1 − pu )du ≤ e−pu du
we have pu ≤ 1/du ≤ p0 . Notice that NG (pu ) ≥ NG (p0 ) ≥ NG (p∗ ) = 1/2. Now by Lemma 17,
1
e−1 = Nu,G (pu ) ≥ (1 − pu )du NG (pu ) ≥ (1 − du pu ).
2
Therefore
1−

2
≤ pu du ≤ 1.
e

(6)

Lemma 23 Let M ∈ [0, n]. The procedure EstimateDegree(OG , u, M ) asks Θ((log M )(log n))
queries and either output p0u ≥ 1/(2M ) such that pu ≥ p0u ≥ pu /8 and then du ≤ 32M or
proclaims that du > M .

1.
2.
3.
4.
5.
6.

EstimateDegree(OG , u, M )
For each pu,i = 1/2i such that 2i ≤ 16M
for t = Θ(log n) independent pu,i -queries Qi,1 , . . . , Qi,t do:
qu,i = (OG (Qi,1 ∪ {u}) + · · · + OG (Qi,t ∪ {u}))/t.
Choose the first p0u := piu,0 /2 such that 1 − qu,iu,0 > 1/e.
If no such iu,0 exists then output(“du > M ”).
Otherwise output(p0u ) \ ? pu ≥ p0u ≥ pu /8 ? \.

Proof Let k be such that pu /2 < pu,k ≤ pu . Then pu,k−2 > 2pu and therefore for all i ≤ k − 2,
Nu,G (pu,i ) ≤ Nu,G (pu,k−2 ) < Nu,G (2pu ) < Nu,G (pu )2 ≤ 1/e2 . Therefore, (E[1 − qu,i ] =
Nu,G (pu,i ) ≤ 1/e2 )
Pr[iu,0 ≤ k − 2] ≤ Pr[(∃i ≤ k − 2)1 − qu,i > 1/e] ≤ 1/poly(n).
22

L EARNING G RAPH

Therefore, w.h.p, iu,0 ≥ k − 1. Now, pu,k+1 = pu,k /2 ≤ pu /2 and therefore Nu,G (pu,k+1 ) >
Nu,G (pu /2) > Nu,G (pu )1/2 > 0.6. Therefore
Pr[iu,0 ≥ k + 2] ≤ Pr[1 − qu,k+1 < 1/e] ≤ 1/poly(n).
Therefore, w.h.p k−1 ≤ iu,0 ≤ k+1 and then 2pu ≥ pu,k−1 ≥ pu,iu,0 ≥ pu,k+1 ≥ pu /4. Therefore
w.h.p
pu ≥ p0u = pu,iu,0 /2 ≥ pu /8.
Now, by (6) and step 1 in the procedure,
du ≤
0

1
1
2
≤ 0 =
≤ 32M.
pu
pu
pu,iu,0
0

Let i0 be such that 2i ≤ 16M and 2i +1 > 16M . If no such iu,0 exists then i0 ≤ k and therefore
by (6),
4
4du
1
0
≤
≤
16M < 2i +1 ≤ 2k+1 =
pu,k+1
pu
(1 − 2/e)
and then m ≥ du > M .

1.
2.
3.
4.
5.
6.

k-EstimateDegree(OG , u)
For j = k − 1 downto 0
Mj ← (log[j] n)2 .
EstimateDegree(OG , u, Mj )
If the output is p0u then Goto 6.
EndFor.
Output(p0u ) \ ? pu ≥ p0u ≥ pu /8 ? \.

We now show
Lemma 24 The procedure k-EstimateDegree(OG , u) runs in k rounds, with probability 1 −
1/poly(n), asks
√
O((log[k] n)(log n) + m log n)
queries and outputs p0u such that pu ≥ p0u ≥ pu /8.
Proof For j = 0 we have M0 = (log[0] n)2 = n2 and since m < M0 , by Lemma 23, the algorithm
must stop and output such p0u . It remains to prove the query complexity.
If EstimateDegree(OG , u, Mk−1 ) returns p0u then, by Lemma 23, the algorithm asks
Θ((log Mk−1 )(log n)) = Θ((log[k] n)(log n))
queries. Otherwise, m ≥ du > Mk−1 . Let j be such that Mj+1 < m ≤ Mj . Then p0u is returned
by some EstimateDegree(OG , u, Mj 0 ) where j 0 ≥ j. Therefore the number of queries is O of
k
X

p
√
(log Mi )(log n) ≤ 2(log Mj )(log n) = 4 Mj+1 log n ≤ 4 m log n.

i=j 0

23

L EARNING G RAPH

In particular,
Corollary 14 The procedure log∗ n-EstimateDegree(OG ) runs in log∗ n rounds, with probability
√
1 − 1/poly(n), asks O( m log n) queries and outputs p0u such that pu ≥ p0u ≥ pu /8.
In particular
Lemma 25 The degrees of all the vertices u in V1 (H) can be estimated with probability 1 −
1/poly(n) by 1/p0u that falls in the range [du , 31du ] with
√
1. k-round algorithm that asks at most O((log[k] n) m log n + m log n) queries.
2. log∗ n-round algorithm that asks at most O(m log n) queries.
√
Proof By Lemma 21, w.h.p |V1 (H)| = O( m) and by (6) and Lemma 24, for every u ∈ V1 (H),
the value of 1/p0u is bounded by
du ≤

1
1
8
8du
≤ 0 ≤
≤
≤ 31du .
pu
pu
pu
1 − 2/e

After estimating the degree the algorithm finds the edges of each v ∈ V1 (H) in G.
We first have (the proof is the same as of Lemma 17)
Lemma 26 Suppose I is an independent set in G and let Γ(I) be the set of neighbors of the vertices
in I. Let u be a vertex in G such that u 6∈ Γ(I). For a p-random query Q we have
Pr[OG (Q ∪ {u}) = 0 | I ⊆ Q] ≥ (1 − p)|Γ(I)| · Nu,G (p).
We now prove
Lemma 27 The edges of each v ∈ V1 (H) can be learned with probability 1 − 1/poly(n) in
O(m log n) queries
Proof Let u ∈ V1 (H). Let Q be a p0u -random query and {u, v} 6∈ E. By Lemma 26, Lemma 24,
(5)
Pr[OG (Q ∪ {u}) = 0 and v ∈ Q] = Pr[v ∈ Q] · Pr[OG (Q ∪ {u}) = 0 | v ∈ Q]
0

= p0u · (1 − p0u )1/pu Nu,G (p0u )
pu
0
≥
(1 − p0u )1/pu Nu,G (pu )
8
1 − 2/e 1 −1
≥
e
8du 4
0.003
≥
.
du

24

L EARNING G RAPH

Therefore each p0u -random query discover that {u, v} is not an edge with probability at least 0.003/du .
Therefore O(du log n) queries are enough to find all the neighbours of u with probability 1 −
1/poly(n). The total number of queries is O of
X
du log n ≤ 2m log n.
u∈V1 (H)

The following is the procedure

1.
2.
3.
4.
5.
6.
7.

FindEdges(OG ,V1 (H))
For each u ∈ V1 (H) do.
Choose t = Θ((1/p0u ) log n) p0u -random queries Q1 , . . . , Qt
For each query Qi .
If OG (Qi ∪ {u}) = 0 then
For every v ∈ Qi do E(H)\{{u, v}}
EndFor
Return (V, E(H)).

7. Open Problems
In this section we give some open problems
1. The problem of whether there is a O(1)-round learning algorithm for m-Graph with O(m log n)
queries when m is unknown to the learner is still open.
2. Find a tight lower bound for two-round Monte-Carlo algorithm.

References
Hasan Abasi, Nader H. Bshouty, and Hanna Mazzawi. On exact learning monotone DNF from
membership queries. In Peter Auer, Alexander Clark, Thomas Zeugmann, and Sandra Zilles,
editors, Algorithmic Learning Theory - 25th International Conference, ALT 2014, Bled, Slovenia,
October 8-10, 2014. Proceedings, volume 8776 of Lecture Notes in Computer Science, pages
111–124. Springer, 2014. ISBN 978-3-319-11661-7. doi: 10.1007/978-3-319-11662-4 9. URL
https://doi.org/10.1007/978-3-319-11662-4_9.
Hasan Abasi, Nader H. Bshouty, and Hanna Mazzawi. Non-adaptive learning of a hidden hypergraph. Theor. Comput. Sci., 716:15–27, 2018. doi: 10.1016/j.tcs.2017.11.019. URL
https://doi.org/10.1016/j.tcs.2017.11.019.
Noga Alon and Vera Asodi. Learning a hidden subgraph. SIAM J. Discrete Math., 18(4):
697–712, 2005. doi: 10.1137/S0895480103431071. URL https://doi.org/10.1137/
S0895480103431071.

25

L EARNING G RAPH

Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, and Benny Sudakov. Learning a hidden
matching. SIAM J. Comput., 33(2):487–501, 2004. doi: 10.1137/S0097539702420139. URL
https://doi.org/10.1137/S0097539702420139.
Dana Angluin and Jiang Chen. Learning a hidden hypergraph. Journal of Machine Learning Research, 7:2215–2236, 2006. URL http://www.jmlr.org/papers/v7/angluin06a.
html.
Dana Angluin and Jiang Chen. Learning a hidden graph using o(logn) queries per edge. J. Comput.
Syst. Sci., 74(4):546–556, 2008. doi: 10.1016/j.jcss.2007.06.006. URL https://doi.org/
10.1016/j.jcss.2007.06.006.
Dana Angluin, James Aspnes, and Lev Reyzin. Inferring social networks from outbreaks. In
Marcus Hutter, Frank Stephan, Vladimir Vovk, and Thomas Zeugmann, editors, Algorithmic Learning Theory, 21st International Conference, ALT 2010, Canberra, Australia, October 6-8, 2010. Proceedings, volume 6331 of Lecture Notes in Computer Science, pages 104–
118. Springer, 2010. ISBN 978-3-642-16107-0. doi: 10.1007/978-3-642-16108-7 12. URL
https://doi.org/10.1007/978-3-642-16108-7_12.
Mathilde Bouvel, Vladimir Grebinski, and Gregory Kucherov. Combinatorial search on graphs
motivated by bioinformatics applications: A brief survey. In Dieter Kratsch, editor, GraphTheoretic Concepts in Computer Science, 31st International Workshop, WG 2005, Metz, France,
June 23-25, 2005, Revised Selected Papers, volume 3787 of Lecture Notes in Computer Science,
pages 16–27. Springer, 2005. ISBN 3-540-31000-2. doi: 10.1007/11604686 2. URL https:
//doi.org/10.1007/11604686_2.
Nader H. Bshouty. Linear time constructions of some d -restriction problems. In Vangelis Th.
Paschos and Peter Widmayer, editors, Algorithms and Complexity - 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings, volume 9079 of Lecture Notes
in Computer Science, pages 74–88. Springer, 2015. ISBN 978-3-319-18172-1. doi: 10.1007/
978-3-319-18173-8 5. URL https://doi.org/10.1007/978-3-319-18173-8_5.
Mahdi Cheraghchi. Noise-resilient group testing: Limitations and constructions. Discrete Applied
Mathematics, 161(1-2):81–95, 2013. doi: 10.1016/j.dam.2012.07.022. URL https://doi.
org/10.1016/j.dam.2012.07.022.
Dingzhu Du, Frank K Hwang, and Frank Hwang. Combinatorial group testing and its applications,
volume 12. World Scientific, 2000.
AG D’yachkov and VV Rykov. Bounds on the length of disjunctive codes. PROB. INFO. TRANSMISSION., 18(3):166–171, 1983.
Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapati, and
Ananda Theertha Suresh. Estimating the number of defectives with group testing. In IEEE
International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, July 10-15, 2016,
pages 1376–1380. IEEE, 2016. ISBN 978-1-5090-1806-2. doi: 10.1109/ISIT.2016.7541524.
URL https://doi.org/10.1109/ISIT.2016.7541524.

26

L EARNING G RAPH

𝑉𝐺

𝑉𝐻
𝑑𝐻 𝑢1

𝑑𝐺 𝑢1 = 0
𝑟
≤
8 𝑢1

𝑢2

𝑑𝐺 𝑣2 > 𝑟 + 1

𝑢3

𝑣2

𝑑𝐺 𝑣1 > 𝑟 + 1

𝑣1

𝐸

𝑣6

𝑑𝐺 𝑣3 > 𝑟 + 1

𝑣9

𝑢5

𝐸0 = ∅
8𝑚2
𝐸2 ≤
𝑟

𝐼𝑣1

𝑣11

𝐸1

𝑟
𝑑𝐺 (𝑣5 ) ≥
2

𝑣7

𝑣3
𝑢4

𝑣8

𝑑𝐺 𝑣11 > 𝑟 + 1

𝑣4

𝐸2

𝑑𝐺 (𝑣4 ) ≥

𝑣5

𝑣10
𝑟
2

𝐸 𝐻 = 𝐸1 ∪ 𝐸2 ∪ 𝐸
𝑊 = {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 , 𝑣11 }
= {𝑢1 , 𝑢2 , 𝑢3 , 𝑣7 }
𝐼𝑣2 = {𝑢3 , 𝑣4 }

𝐼𝑣3 = {𝑢1 , 𝑢4 , 𝑢5 , 𝑣7 }

𝐼𝑣4 = {𝑣6 , 𝑣7 }

Figure 4: An Example
Zoltán Füredi. On r-cover-free families. J. Comb. Theory, Ser. A, 73(1):172–173, 1996. doi:
10.1006/jcta.1996.0012. URL https://doi.org/10.1006/jcta.1996.0012.
Hwang Frank Kwang-ming and Du Ding-zhu. Pooling designs and nonadaptive group testing:
important tools for DNA sequencing, volume 18. World Scientific, 2006.

27

