A Nearly-Quadratic Gap Between Adaptive and Non-Adaptive Property Testers Citation Hurwitz, Jeremy Scott (2012) A Nearly-Quadratic Gap Between Adaptive and Non-Adaptive Property Testers. Master's thesis, California Institute of Technology. doi:10.7907/W178-HP57. https://resolver.caltech.edu/CaltechTHESIS:11302011-091414252 Abstract We show that for all integers t ≥ 8 and arbitrarily small ε > 0, there exists a graph property Π (which depends on ε) such that ε-testing Π has non-adaptive query complexity Q = Θ(q 2-2/t ), where q = Õ(ε -1 ) is the adaptive query complexity. This resolves the question of how beneficial adaptivity is, in the context of proximity-dependent properties ([GR07]). This also gives evidence that the canonical transformation of Goldreich and Trevisan ([GT03]) is essentially optimal when converting an adaptive property tester into a non-adaptive property tester. To do so, we consider the property of being decomposable into a disjoint union of subgraphs, each of which is a (possibly unbalanced) blow-up of a given base-graph H. In [GR09], Goldreich and Ron proved that when H is a simple t-cycle, the non-adaptive query complexity is Ω(ε -2+2/t , even under the promise that G has maximum degree O(εN). In this thesis, we prove a matching upper bound for the non-adaptive complexity and a tight (up to a polylogarithmic factor) upper bound on the adaptive complexity. Specifically, we show that for all H, testing whether G is a collection of blow-ups of H and has maximum degree O(εN) requires only O(ε -1 lg 3 ε -1 ) adaptive queries or O(ε -2+1/(δ+2) +ε -2+2/W ) non-adaptive queries, where δ = Δ(H) is the maximum degree of H and W< |H| 2 is a bound on the size of witnesses against H. Item Type: Thesis (Master's thesis) Subject Keywords: Sublinear-Time Algorithms, Property Testing, Dense-Graph Model, Adaptive vs Non-adaptive Queries, Hierarchy Theorem Degree Grantor: California Institute of Technology Division: Engineering and Applied Science Major Option: Computer Science Thesis Availability: Public (worldwide access) Research Advisor(s): Umans, Christopher M. (co-advisor) Schulman, Leonard J. (co-advisor) Thesis Committee: Unknown, Unknown Defense Date: December 2011 Funders: Funding Agency Grant Number NSF UNSPECIFIED Record Number: CaltechTHESIS:11302011-091414252 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:11302011-091414252 DOI: 10.7907/W178-HP57 Related URLs: URL URL Type Description https://resolver.caltech.edu/CaltechAUTHORS:20200529-111433160 Related Item Book Chapter Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 6741 Collection: CaltechTHESIS Deposited By: Jeremy Hurwitz Deposited On: 06 Jan 2012 22:42 Last Modified: 29 May 2020 18:17 Thesis Files Preview PDF (Master's Thesis) - Final Version See Usage Policy. 642kB Repository Staff Only: item control page

A Nearly-Quadratic Gap Between Adaptive and Non-Adaptive Property Testers Thesis by Jeremy Hurwitz In Partial Fulllment of the Requirements for the Degree of Master Of Science California Institute of Technology Pasadena, California 2011 (Submitted November 18, 2011) ii c 2011 Jeremy Hurwitz All Rights Reserved iii To my friends and family. iv Acknowledgements I would rst like to thank my adviser, Prof. Chris Umans, for many helpful discussions throughout this entire process, from initially nding a project through formal publication and writing this thesis. I would like to also thank Prof. Oded Goldreich for encouraging me to extend the lower-bound into a hierarchy theorem. I would also like to thank my adviser, Prof. wandering interests. Leonard Schulman, for supporting my frequently- v Abstract We show that for all integers t ≥ 8 and arbitrarily small  > 0, there exists a graph property Π (which depends on ) such that -testing Π has non-adaptive query complexity Q e 2−2/t ), = Θ(q −1 ) is the adaptive query complexity. This resolves the question of how benecial e where q = O( adaptivity is, in the context of proximity-dependent properties ([GR07]). This also gives evidence that the canonical transformation of Goldreich and Trevisan ([GT03]) is essentially optimal when converting an adaptive property tester into a non-adaptive property tester. To do so, we consider the property of being decomposable into a disjoint union of subgraphs, each of which is a (possibly unbalanced) blow-up of a given base-graph H . In [GR09], Goldreich and −2+2/t ), even Ron proved that when H is a simple t-cycle, the non-adaptive query complexity is Ω( under the promise that G has maximum degree O(N ). In this thesis, we prove a matching upper bound for the non-adaptive complexity and a tight (up to a polylogarithmic factor) upper bound on the adaptive complexity. Specically, we show that for all H , testing whether G is a collection of blow-ups of H and has −1 lg3 −1 ) adaptive queries or O(−2+1/(δ+2) + −2+2/W ) maximum degree O(N ) requires only O( non-adaptive queries, where δ = ∆(H) is the maximum degree of H and W < |H| the size of witnesses against H . 2 is a bound on vi Contents Acknowledgements iv Abstract v 1 Introduction 1 1.1 Sublinear Algorithms and Property Testing . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Adaptivity, Non-adaptive, and Canonical Algorithms . . . . . . . . . . . . . . . . . . 3 1.3 Graph Blow-Ups and Blow-Up Collections . . . . . . . . . . . . . . . . . . . . . . . . 5 2 A Hierarchy of Tradeos Between Adaptive and Non-adaptive Query Complexities 8 2.1 Notation and Basics 2.2 Adaptively Testing BU C(H) Given a Promise 2.4 8 . . . . . . . . . . . . . . . . . . . . . . 10 Proof of Lemma 14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Non-adaptively Testing BU C(H) Given a Promise . . . . . . . . . . . . . . . . . . . . 16 2.3.1 Proof of Lemma 20 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Removing the Low-Degree Promise . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2.1 2.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 An Alternate Proof that CliqueCollection has Adaptive Query Complexity e −1 ) O( 24 3.1 24 The Adaptive Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 3.2 Proof Of Lemma 26 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4 Towards Proving an Upper Bound on the Adaptive Query Complexity of BU C(H) for Arbitrary H 29 4.1 Basic Behavior of SubTest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.2 Sketch of the Reconstruction Procedure . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.3 The Reconstruction Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.3.1 Cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.3.2 General H . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5 Conclusions and Open Problems 38 Bibliography 39 1 Chapter 1 Introduction 1.1 Sublinear Algorithms and Property Testing In recent decades, the amount of data being generated and processed has grown exponentially. As a result, in many situations polynomial-time is no longer a sucient criteria for an algorithm to be considered ecient. Indeed, even quasi-linear time can be prohibitively slow for many datasets. In other situations, such as biology or sociology, the total amount of data may be only moderately large, but obtaining a single piece of data requires running an expensive experiment. Sublinear algorithms attempt to circumvent these diculties by considering only a minuscule random subset of the data, in the hopes of getting an approximately-correct answer far faster than would be required to obtain the exact answer. A classic example of this tradeo is determining the mean of a list of numbers. Calculating the mean exactly requires linear time. However, by randomly sampling −2 ) times, we can obtain an answer that is accurate to within a multiplicative from the list O( factor of 1 +  with high probability. This observation provides the statistical justication to most population surveys. More modern examples include estimating the weight of the minimum spanning tree of a graph ([CRT05]) and estimating the distance from uniform of a given distribution ([GR00]). In addition to estimating large-scale parameters of the input, we also might be interested in determining structural properties for the data. For example, given a list of numbers, we may wish to determine whether the list is sorted. As in the case of calculating the mean, determining the answer with certainty requires inspecting the entire input. However, unlike when approximating the mean, the answer in this case is boolean and so the idea of approximating the answer no longer makes sense. We overcome this by moving the approximation from the output to the input. Originally 2 formalized in [BLR90] and [RS96], a property tester attempts to dierentiate inputs which satisfy the property (the list is sorted) from inputs which are far from satisfying the property (at least an -fraction of the elements are out of place). For inputs which are close to satisfying the property, either answer is allowed  technically, the list is not sorted, but for all practical purposes it might as well be. The formal denition of a property tester is as follows. Let FN be the set of functions [N ] → R, for some range R. A property Π is an arbitrary subset of S∞ N =1 FN . We say that a function f : [N ] → R -far from Π if, for any g ∈ Π, |{x ∈ [N ] : f (x) 6= g(x)}| > N . is  For example, viewing f ∈ FN as dening a list, we can let Π be the set of sorted lists. Then a function f is -far from Π if at least N elements are incorrectly sorted. Denition 1 (Property Tester). An algorithm A is a property tester for Π if, given  > 0 and query access to f , • Pr[A(f ) = 1] > 23 for all f ∈ Π • Pr[A(f ) = 1] < 23 for all f which are -far from Π. The tester is considered ecient if the query-complexity Q = Q(N, ) is a function of only . If Pr[A(f ) = 1] = 1 for all f ∈ Π, the tester is said to have one-sided error ; otherwise, it has two-sided error. This framework was rst applied to combinatorial structures in [GGR98], specically with respect to graph properties. A graph property is a property which is preserved under permutation of the underlying graph (ie, the property is of the graph itself, and not of the particular labeling of the graph). In this context, graphs are generally represented using one of three dierent models, according to the standard edge-density of the graphs under consideration and the types of queries which will be allowed. In the dense-graph model ([GGR98], the graph is viewed as a function f : [N ] × [N ] → {0, 1}. In other words, the tester is given access to the graph via its adjacency matrix. Note that the domain has size N 2 and so a graph is -far from a given property if at least N 2 edges must be added or removed to correct the graph. This model is most appropriate for situations in which graphs typically have degree Ω(N ). The bounded-degree model ([GR97]), on the other hand, is used for constant-degree graphs. In this 3 model, the graph is represented via a series of incidence lists. Formally, the tester has access to a function f : [N ] × [d] → [N ] ∪ {⊥}, where f (x, i) = y means that y is the i-th neighbor of x and f (x, i) =⊥ means that x has less than i neighbors. Since the domain has size dN , a graph is -far from a given property if at least dN edges must be added or removed to correct the graph. When analyzing the eciency of a tester in the bounded-degree model, d is generally viewed as a (small) constant. More recently, [PR02] and [KKR04] have proposed a general-graph model in which the tester is given query access to both the adjacency-matrix and the incidence-list representations of the input graph. Distance, in this model, is measured with respect to |E|, which means that the absolute number of allowable incorrect edges cannot be a priori bounded. In this thesis, we focus exclusively on the dense-graph model. 1.2 Adaptivity, Non-adaptive, and Canonical Algorithms Query algorithms can be broadly classied into two types according to how the queries are determined. In an adaptive algorithm, the results of previous queries may be used when determining which query to make next. A non-adaptive algorithm, on the other hand, determines all of its queries in advance. In general, adaptive algorithms require far fewer queries than non-adaptive algorithms. For example, −1 ) adaptive approximating the threshold value of a step function to within  requires only O(lg  −1 ) non-adaptive queries (since there must be a query queries (by binary search) but requires Ω( within every interval of diameter 2). Indeed, in the bounded-degree model, any graph property √ which does not depend solely on the degree distribution requires Ω( n/d) queries ([RS06]). In the dense graph model, however, the maximum gap between the adaptive and non-adaptive query complexities are separated by at most a quadratic factor. Theorem 2 (canonical-testers). Let Π be a property which is testable in the dense-graph model using at most q = q(N, ) (adaptive) queries. Then there exists a non-adaptive tester for Π with query complexity O(q 2 ). Furthermore, this non-adaptive tester operates by querying the entire subgraph induced by 2q random vertices. The theorem follows immediately from the observation that any algorithm that makes q queries 4 touches at most 2q vertices. By applying a random permutation to G before running the adaptive algorithm, the set of touched vertices is uniformly random. It therefore suces to query a random induced subgraph and then simulate the adaptive algorithm locally. An algorithm of this form is known as a canonical algorithm. e Let q denote the adaptive query-complexity, Q denote the non-adaptive query complexity, and Q e . Theorem 2 shows that Q e = O(q denote the canonical query complexity. By denition, q ≤ Q ≤ Q 2 ). A natural question, then, is to determine the exact relationship between these parameters. 2 e = Ω(Q ). Specically, let Π consist solely of the It is easy to see that there exist properties with Q −2 ) random edges clearly suces to dierentiate the empty graph from empty graph. Querying Ω( one with at least N 2 edges. However, any canonical algorithm must touch Ω(−1 ) vertices, and −2 ). Indeed, [GR09] showed that any non-trivial property has therefore has query complexity Ω( −2 ). canonical query complexity Ω( Similarly, we can consider the relative power of adaptive versus non-adaptive (but not necessarily canonical) property testers. It is widely believed that the canonical transformation remains optimal, in the worst case, even for this more modest goal. In other words, it is believed that there exist properties such that Q = Ω(q 2 ). However, proving such a separation between the adaptive and non-adaptive complexities has proven elusive  no unconditional gap was known until Goldreich e and Ron demonstrated a property where Q = Ω(q 3/2 ) in [GR09]. In light of this diculty, researchers have considered two modications of the problem. The rst approach, used by [GR07], considers proximity-dependent properties, properties which depend (nat- urally) on the tolerance parameter . In particular, they considered the combined property of being e bipartite and having degree at most O(N ), and achieved a gap of Q = Θ(q The second approach, used by [GR09], is to consider 4/3 ). promise problems. In this context, the au- thors showed that there exist properties such that Q = Ω(q 2−δ ) for all δ > 0, exhibiting the rst nearly-quadratic gap between adaptive and non-adaptive queries in the dense-graph model. More specically, the authors demonstrated a hierarchy of gaps of the form Q = Θ(q 2−2/t ) for each integer t ≥ 2. Unfortunately, the promise they use, while natural, is quite strong, and it is currently unclear how to remove the promise. In this thesis, we achieve a nearly-quadratic gap without using a promise, at the expense of making the properties proximity-dependent. This proves that for all δ > 0 and arbitrarily small , there 5 exists a property Π (which depends on ), such that -testing Π requires Q > q 2−δ non-adaptive queries, where q is the adaptive query complexity. As in [GR09], we also strengthen the result and establish a hierarchy of relationships between the adaptive and non-adaptive query complexities. Theorem 3 (Main Theorem). For all t ≥ 8 and arbitrarily small , there exists a graph property Π e 2−2/t ), where (which depends on ) such that -testing Π has non-adaptive query complexity Q = Θ(q e −1 ) is the adaptive query complexity. q = Θ( Theorem 3 and [GR09] both provide strong evidence that the canonical transformation is optimal in the general case. Although each result technically leaves open the possibility of a better transformation between adaptive and non-adaptive testers, each does so in a dierent, and very restricted, way. As a result, any such transformation would have to be very unnatural and would have to depend sensitively on the internal structure of the adaptive tester. 1.3 Graph Blow-Ups and Blow-Up Collections Informally, a graph blow-up consists of replacing each vertex of a graph with a cluster of vertices and replacing each edge with a complete bipartite graph (a rigorous denition is given in section 2.1). This operation has been used frequently in studying the dense-graph model, for constructing both upper- and lower-bounds (see, for example, [Alo01], [AS06], and [GKNR09]). The complexity of testing whether a graph is a blow-up of a xed graph H was essentially resolved in [Avi09] (see also [AG11]), where it is shown that, for any H , the adaptive query complexity is e −1 ). O(−1 ) and the non-adaptive query complexity is O( A graph is a blow-up collection if it can be partitioned into disjoint subgraphs, each of which is a blow-up of H . This notion was implicitly introduced in [GR09], which showed the following lower bound. Lemma 4 ([GR09], Lemma 5.6). Let H be a simple t-cycle, with t ≥ 4. Testing whether G is a blow-up collection of H requires Ω(−(2−2/t) ) non-adaptive queries, even given the promise that G has maximum degree 2tN . −4/3 ) when H is a single loop. The authors also showed a lower bound of Ω( To prove a nearly-quadratic gap between adaptive and non-adaptive query complexities, it therefore 6 −1 ) upper-bound on the adaptive query complexity for testing whether a e suces to show an O( graph is a blow-up collection, for arbitrary H . In [GR09], the authors showed such an upper bound for the cases where H is a single loop and H is a single edge. Unfortunately, they were unable to show such an upper bound for larger H . In this thesis, we prove tight upper-bounds for both the adaptive and non-adaptive cases under the promise that G has maximum degree O(N ). Specically, we show that a tester can determine whether G is a blow-up collection of any given H , given that promise on the degrees, using only O(−1 ) adaptive queries or O(−2+1/(∆+2) + −2+2/W ) non-adaptive queries, where ∆ and W are H. parameters depending only on When H is a simple t-cycle, ∆ = 2 and W = t, and the −2+2/t ), matching the lower bound in Lemma 4. non-adaptive upper bound reduces to O( Indeed, our result holds even if G is only O()-close to satisfying the promise. Since [GR07] gives an ecient non-adaptive tester for the property of having maximum degree O(N ), we obtain the following two theorems. Theorem 5 (Adaptive Tester). For all graphs H and constants c > 1, there exists an adaptive property tester (with two-sided error) for the (proximity-dependent) combined property of having maximum degree cN and being a blow-up collection of H . The tester has query complexity O(−1 lg3 −1 ). −1 ) queries, Theorem 5 is optimal up to a polylogarithmic factor. Since any tester must make Ω( Theorem 5, combined with Lemma 4, suces to show a gap of size Q = Ω(q 2−δ ) for all δ > 0. In the following theorem, we strengthen this result by proving a tight upper-bound on the non-adaptive query complexity. This shows that there is an innite hierarchy of achievable relationships between the adaptive and non-adaptive query complexities of proximity-dependent properties. Theorem 6 (Non-Adaptive Tester). For all graphs H and constants c > 1, there exists a nonadaptive property tester (with two-sided error) for the (proximity-dependent) combined property of having maximum degree cN and being a blow-up collection of H . The tester has query complexity O(−2+1/(∆+2) + −2+2/W ), where ∆ = deg(H) is the maximum degree of H and W < |H|2 is a bound on the size of a witness against H (see Denition 12). The proofs of Theorems 5 and 6 are given in Chapter 2. As mentioned previously, when H is a simple t-cycle, ∆ = 2 and W Theorems 5 and 6 with Lemma 4 yields Theorem 3. = t. Therefore, combining 7 Treating c and |H| as constants, we note that the algorithms in both theorems have running time polynomial in the query complexity. In the adaptive case, the query complexity can also be made polynomial in c and |H|, although we do not do so here. 8 Chapter 2 A Hierarchy of Tradeos Between Adaptive and Non-adaptive Query Complexities In this chapter, we prove theorems 5 and 6, thereby establishing theorem 3. 2.1 Notation and Basics All graphs are assumed to be undirected. Following standard graph-theoretic notation, we let Γ(v) = {u : (u, v) ∈ E} denote the neighbors of v . Given S ⊂ V , we let G|S denote the subgraph induced by S and ΓS (v) = Γ(v) ∩ S denote the neighbors of v in S . Given S, T ⊂ V , we let E(S, T ) = {(u, v) ∈ E : u ∈ S, v ∈ T } denote the set of edges between S and T and S M T denote the symmetric dierence of S and T . Denition 7 (Graph Blow-Up). A graph G = ([N ], E) is a blow-up of the graph H = ([h], F ) if there exists a partition of [N ] into V1 , . . . , Vh such that for every i, j ∈ [h] and (u, v) ∈ Vi × Vj , (u, v) ∈ E if and only if (i, j) ∈ F . We denote the set of blow-ups of H by BU(H). Note that no requirement is made as to the relative sizes of the Vj . In particular, we allow the case where |Vj | = 0. Also note that H is allowed to contain self-loops, in which case G is obtained from H by replacing the vertices with self-loops with cliques instead of independent sets. Denition 8 (Blow-Up Collection). A graph G = ([N ], E) is a blow-up collection of the graph H if there exists a partition of [N ] into V 1 , . . . , V k , for some k, such that V i ∈ BU(H) for all i and E(V i , V j ) = ∅ for all i 6= j . We denote the set of blow-up collections of H by BU C(H). 9 When H is a single loop, [GR09] refers to BU C(H) as edge, they refer to BU C(H) as clique collection. Similarly, when H is a single biclique collection. Throughout this thesis, H will be an arbitrary xed graph and c > 1 will be an arbitrary xed constant. We let h = |H| denote the number of vertices in H and ∆ = deg(H) denote the maximum degree of H . Denition 9 (Low-Degree Graph). Given c > 1 and  > 0, let LDc = {G : deg(G) ≤ cN } denote the set of graphs with maximum degree cN . To prove Theorems 5 and 6, we will repeatedly use the concept of a vertex being (k, α) -partitionable. Informally, a vertex is (k, α)-partitionable if almost all of its neighbors can be partitioned into k groups, such that all of the vertices within a part have essentially the same neighbors in G. The formal denition is given in Denition 11, after we introduce notation for such partitions. Denition 10. Given v ∈ V and α > 0, let Cv,α (u) = {w ∈ Γ(v) : |Γ(w) M Γ(u)| < αN }. In other words, Cv,α (u) consists of all vertices in Γ(v) which have essentially the same neighbors as u. When v and α are clear from context, we will omit the subscripts and write C(u) for Cv,α (u). Denition 11 ((k, α)-Partitionable). A vertex v is (k, α)-partitionable if there exist representatives u1 , . . . , uk ∈ Γ(v) such that Sk i=1 Cv,α (ui ) ≥ |Γ(v)| − αN . Note that if G ∈ BU C(H), then every vertex is (deg(H), 0)-partitionable. Finally, we need the idea of a minimal witness against BU C(H). Informally, a minimal witness is a set of vertices such that the induced subgraph proves that G is not a valid blow-up collection, while any subset does not suce. Denition 12 (Minimal Witness). A set S ⊆ V is a minimal witness against BU C(H) if G|S 6∈ BUC(H), but for any S 0 ( S , G|S 0 ∈ BU C(H). Note that, for any S ⊆ G, G|S 6∈ BUC(H) implies that G 6∈ BU C(H). Furthermore, any minimal witness against BU C(H) must be connected, since we could otherwise replace the witness with one of its connected components. Given H , we let W = W (H) denote the maximum size of a minimal witness. It is easy to see that
W < (h + 1) + h+1 < h2 . When H is a simple t-cycle, t ≥ 4, W = |H|. 2 10 Handling Technicalities exposition. Throughout this thesis, we allow some small informalities for ease of For example, we often state that an event occurs with high probability, without specifying the exact failure probability. This is taken to mean that the probability of failure is small enough that taking a union-bound over all (constantly-many) such cases yields a total failure probability of at most, say, 0.01. Similarly, when selecting a random set of vertices, we treat the sampling as being performed with replacement. Since these sets will always be of size O(1) and we will only perform such sampling O(1) times (as a function of N ), the odds of a collision are negligible. 2.2 Adaptively Testing BUC(H) Given a Promise We begin by showing how to adaptively test whether a graph G is in BU C(H), given the promise that G is O()-close to LD c . We view G and  as inputs to the algorithm, and H and c as xed parameters. The algorithm consists of two stages. The rst stage (steps 2-8 of Algorithm 13) tests whether most vertices are (∆, 0)-partitionable, where ∆ = deg(H). To do so, it repeatedly selects a vertex and then attempts to nd ∆ + 1 neighbors of that vertex which have mutually distinct neighborhoods (see Figure 2.1(a)). If it nds such a set of vertices, they act as a witness against being in BU C(H) and the algorithm can reject with certainty in step 7. If the algorithm fails to nd such a witness, then most vertices must be (∆, α)-partitionable, where α is a small constant. This implies that the graph must be close to being a blow-up of some base graph. In other words, almost all of the vertices can be clustered such that each pair of clusters is either almost disjoint or almost forms a complete bipartite graph. The second stage of the algorithm (steps 9-16) checks if this high-level structure is consistent with BU C(H) (see Figure 2.1(b)). It does so by performing a random search in G for W neighbor of the previously selected vertices. = W (H) steps, where each step selects a random If the resulting W vertices form a witness against BUC(H), the algorithm rejects in step 15. Algorithm 13. AdaptiveBlowUpCollectionTestH,c (G; ) 1: Let ∆ = deg(H), W = W (H), and α = (16∆ |H|2 )−1 . \\ Test whether most vertices are (∆, 0)-partitionable. 2: for O(c) iterations do 3: Select a random vertex v . 11 Γ(𝑢1 ) △ Γ(𝑢2 ) ... Γ(𝑢𝑖 ) △ Γ(𝑢𝑗 ) 𝑤𝑖𝑖 𝑤12 Γ(𝑢Δ ) △ Γ(𝑢Δ+1 ) ... 𝑤Δ,Δ+1 ... 𝐶𝑣,𝛼 (𝑢1 ) 𝑢1 𝑢2 𝐶𝑣,𝛼 (𝑢2 ) Γ(𝑣) 𝑣 𝑢Δ 𝑢Δ+1 𝐶𝑣,𝛼 (𝑢Δ ) 𝐶𝑣,𝛼 (𝑢Δ+1 ) (a) A witness against v being (∆, 0)-partitionable consists of two sets of vertices.
The rst set consists of ∆ + 1 vertices u1 , . . . , u∆+1 ∈ Γ(v). The second set consists of ∆+1 vertices 2 wij such that wij ∈ Γ(ui ) M Γ(uj ) for each i 6= j . When v is not (∆, α)-partitionable, there exist αN choices for each ui such that ui 6∈ Cv,α (uj ) for any j 6= i, so Algorithm 13 can nd such vertices eciently. Having chosen such a set, there exist αN choices for wij for each i 6= j , allowing algorithm 13 to complete the witness eciently. Steps 2-8 search for witnesses of this type. 𝑣1 𝑉1𝑖 𝑉2𝑖 𝑣2 𝑣4 𝑣3 𝑉4𝑖 𝑉3𝑖 (b) If G has not been rejected by the rst half of Algorithm 13, then V can be partitioned into clusters Vji , such that each pair of clusters either nearly forms a complete bipartite graph or is nearly disjoint. A minimal witness against having the correct high-level structure consists of a representative vertex from each set such that the induced subgraph is inconsistent with BUC(H). For example, when H = K4 is the complete graph on 4 vertices, the four vertices shown here form a minimal witness. Steps 9-16 search for witnesses of this type. Figure 2.1: The two types of witnesses used by Algorithm 13 to determine whether G is a member of BUC(H). In each diagram, a line indicates that the algorithm queried that edge, with a solid line indicating the presence of an edge and a dashed line indicating the absence of an edge. 12 4: 5: 6: 7: Select a random set S of O(∆α −1 −1 ) vertices, and query {v} × S . Let S be a random subset of ΓS (v) of size (at most) c∆α −1 . 2 −1 −1 ) vertices, and query S × T . Select a random set T of O(∆ α If the current view of G is inconsistent with BU C(H), Reject. Specically, reject if there exist u1 , . . . , u∆+1 ∈ S such that ΓT (ui ) 6= ΓT (uj ) for all i, j . 8: end for \\ If G has not yet been rejected, most vertices must be (∆, α)-partitionable. \\ Test that G has a high-level structure consistent with H . 9: for O(W c)O(W ) iterations do 10: Select v1 at random, and let U = {v1 }. 11: for j = 2 to W do −1 ) vertices, and query U × T . 12: Select a random set Tj of O(∆ j 13: If ΓTj (U ) = ∅, break. Otherwise, randomly select vj ∈ ΓTj (U ) and let U = U ∪ {vj }. 14: end for 15: If G|U 6∈ BU C(H), . 16: end for 17: If the algorithm hasn't yet rejected, Reject Accept. Algorithm 13 has query complexity O( −1 ), as desired. Furthermore, it only rejects if it nds a witness against BU C(H), so the algorithm accepts valid blow-up collections with probability 1. The following lemma asserts that it rejects graphs which are far from BU C(H) with high probability. Lemma 14. Let G be 8 -close to LDc and -far from BU C(H). Then Algorithm 13 rejects with probability at least 2/3. The proof is the content of section 2.2.1. 2.2.1 Proof of Lemma 14 We rst note that if G contains many vertices which are not (∆, α)-partitionable, then G is rejected with high probability. Lemma 15. Let ∆ = deg(H), W = W (H), and α = (16∆ |H|2 )−1 . Suppose that G is 8 -close to LDc and contains at least 4c1 N vertices which are not (∆, α)-partitionable. Then Algorithm 13 rejects in step 7 with probability at least 2/3. Proof. Consider the 4c1 N vertices which are not (∆, α)-partitionable. By assumption, at most 8c1 N of them have degree greater than 3cN . For otherwise, 2cN edges would have to be deleted from each such vertex to make G low-degree, meaning that G would have distance at least from LD c . 1  2 1 2 ·2cN · 8c N = 8 N 13 Therefore, with high probability, some iteration chooses a vertex v in step 3 that is not (∆, α)partitionable and has degree at most 3cN . Consider that iteration. Note that since v is not (∆, α)-partitionable, |Γ(v)| > αN . We view S in step 4 of the algorithm as S1 ∪ . . . ∪ S∆+1 , with |Si | = α −1 −1 . With high probability, ΓS1 (v) 6= ∅, so let u1 be an arbitrary vertex in ΓS1 (v). Since v is not (∆, α)-partitionable, Γ(v) 0 such that |Γ(u ) M Γ(u0 )| > αN , and so with high probability 1 contains at least αN vertices u ΓS2 (v) contains such a vertex. Let u2 be that vertex. We continue in this manner, selecting vertices u3 , . . . , u∆+1 such that |Γ(ui ) M Γ(uj )| > αN for all i 6= j . If |ΓS (v)| < c∆α −1 , then S = Γ (v). Otherwise, the probability that each vertex in S is a valid S choice for ui , given u1 , . . . , ui−1 , is at least α 3c , so with high probability S contains the desired ∆ + 1 vertices. Viewing T as S∆+1 i,j=1 Tij , we see that, with high probability, T contains a vertex in Γ(ui ) M Γ(uj ) for all i 6= j . The resulting view of G is therefore inconsistent with BU C(H) and the algorithm rejects, as desired. We now show that if G has at most 1 4c N vertices which are not (∆, α)-partitionable, then G can be partitioned into components such that, for each pair of components, either the edges between them almost form a complete bipartite graph or the components are almost disjoint. Lemma 16. Let ∆ = deg(H) and α = (16∆ |H|2 )−1 . Suppose that G is 8 -close to LDc and contains at most 4c1 N vertices which are not (∆, α)-partitionable. Then G is 58 -close to a graph e = (V, E) e for which the following holds: V can be partitioned into S V i ∪ L such that G i,j j e 1. Γ(v) = ∅ for all v ∈ L, 2. E(V i , V i ) = ∅ for all i 6= i0 , 0 e e 3. For all i, j , Γ(u) = Γ(v) for all u, v ∈ Vji , and  4. Vji > 16∆ N for all i, j , where V i = S i e e j Vj and Γ(u) is the neighborhood of u in G. Furthermore, e V i (u) < αN for all u ∈ V i . ΓV i (u) M Γ Proof. First, delete all edges adjacent to any vertex which is not (∆, α)-partitionable and add those vertices to L. The total cost of doing so is at most 1  2 3 2  4c N · cN + 8 N = 8 N , since G is 8 close to 14 LDc . The construction now proceeds in stages, with each stage constructing a V i = S i j Vj such that e i , V \V i ) = ∅. E(V To construct V into 1 = S  1 j Vj , choose an arbitrary vertex v with |Γ(v)| > 8 N and (∆, α)-partition Γ(v) S∆  1 i j=1 C(uj ). For any j such that |C(uj )| > 16∆ N , add C(uj ) to V as a distinct Vj . Note that since |Γ(v)| >  8 N , there must be at least one partition of that size. While there exists a uj in V 1 such that notation, we relabel uj to v . Let from V \V S∆ j=1 C(uj ) be a (∆, α)-partitioning of Γ(v). Again, there must  N . We add those C(uj )\V 1 to V 1 as distinct Vji s. C(uj )\V 1 > 16∆ be a component such that Once every uj in V Γ(uj )\V 1 > 8 N , choose such a vertex. For consistency of Γ(uj )\V 1 < 8 N , we are ready to nalize V 1 . We begin by separating V 1 1 has 1 by deleting E(V 1 , V \V 1 ), at a cost per vertex of at most  N + αN . We next ensure 8 1 1 × V 1 or the empty set, for all j, j 0 . This can be easily shown to require j0 1 that E(Vj , Vj 0 ) is either Vj at most αN edits per vertex. Note that V 1 now satises conditions 2-5, by construction. 2 3 We now repeat this entire process on the remaining vertices, creating V , V , . . ., until every vertex in V has either been covered or has degree at most leftover vertices, at a cost of  8 N . Finally, we delete all edges adjacent to the  8 N per vertex, and add those vertices to L. The total cost of this procedure is bounded by (  2 5 2  8 N + 2αN )N < 4 N , for a nal cost of 8 N , as desired. Note that the bound on e V i (u) in the lemma implies that G e is  -close to having maximum ΓV i (u) M Γ 8 degree 2cN , since G is  8 -close to having maximum degree cN and the degree of each vertex e . Therefore, conditions 3 and 4 imply that most increases by at most αN when going from G to G i of the components Vj are connected to at most 32c∆ other components and have size at most 2cN . i Intuitively, these conditions allow us to view each cluster Vj as a supernode and each bipartite e becomes a bounded-degree graph, with maximum degree graph as an edge. From this viewpoint, G 32c∆. Since each supernode contains Ω(N ) vertices (by condition 4 in the lemma), we can simulate −1 ) random vertices and choosing a random neighbor. Furthermore, neighbor queries by querying O( e is Ω()-far from BU C(H) when viewed as a dense graph, the corresponding bounded-degree if G graph is Ω(1)-far from BU C(H). 15 e covers a constant To formalize this intuition, we rst show that the set of witnesses against G fraction of V . Lemma 17. Let Ge be as in Lemma 16, and suppose that Ge is 38 -far from BU C(H). Then there fk = exist at least (16W c2 )−1 disjoint sets W S ik fk is a witness against BU C(H). ` Vjk,` such that G|W e is in LD2c . Note that the resulting graph is still  -far Proof. First, delete 8 N 2 edges so that G 4 from BUC(H). fk . Completely disconnecting all vertices contained in W fk requires at most W (2cN ) Consider some W 2 deletions, since there are at most W components and, by Lemma 16, each component contains at most 2cN vertices and each vertex has degree at most 2cN . 2 −1 disjoint W fk , the total cost of deleting all witnesses in Therefore, if there are less than (16W c ) e is at most (16W c2 )−1 · W (2cN )2 =  N 2 . This contradicts the assumed distance to BU C(H), G 4 and the lemma follows. We are now ready to show that the second half of Algorithm 13 nds a witness against G with high probability. Informally, by Lemma 17, step 10 of the algorithm selects a vertex v1 ∈ Vji1 corresponding to a witness with high probability. Having chosen v1 , we wish to bound the probability that v2 , . . . , vW are chosen so as to form a complete witness. there must exist a v2 Recalling that any minimal witness is connected, e. ∈ Vji2 which extends the witness in G By condition 3 of Lemma 16, any i can be used in place of v to extend the witness. However, since 2 vertex in Vj 2  N and Vji2 > 16∆ e V i (u) < αN < 1 V i , at least half of V i is a valid choice to extend the witness in ΓV i (u) M Γ j2 j2 2W G. Furthermore, most of these must have degree O(cN ). Iterating this procedure, we see that there are always at least Ω(  ∆ N ) choices for vj which extend the witness in G. Furthermore, since each previous vj 0 was chosen to have degree O(cN ), there are at most O(W cN ) potential choices for vj . Therefore, with probability Ω((W 2 c)−1 ), Algorithm 13 chooses a good vj at each step and nds a complete witness in G. The formal proof is as follows. Proof of Lemma 14. If G is rejected with probability at least 2/3 by the rst part of Algorithm 13, then we are done. So suppose otherwise. e satisfying the Then by Lemma 15, there exists G 16 e is at least conclusion of Lemma 16. Since G is -far from BU C(H), G 2 −1 sets W fk = By Lemma 17, there exist (16W c ) S 3 8 -far from BU C(H). ik f ` Vjk,` corresponding to witnesses. Call a Wk k fk contains  N vertices of degree greater than 65∆W c2 N . ⊂ W high-degree if, for some Vjik,` 64∆ fk are high-degree. Otherwise, G would have distance at least We note that at most half of the W 1 2 −1 · 64∆W c2 N ·  N =  N 2 to LD , contrary to assumption. c 2 · (16W c ) 64∆ 32 2 −1 witnesses which are not high-degree. We therefore restrict our attention to the (32W c ) i i e . In other words, Let V1 , . . . , V` , ` < W , be components corresponding to a partial witness in G ∗ ∗ (V1i , . . . , V`i ) = (Wji1 , . . . , Wji` ), for some i∗ and j1 , . . . , j` . Let v1 , . . . , v` be arbitrary vertices in i V1i , . . . , V`i , respectively, such that |Γ(vj )| < 65∆W c2 N for each j ≤ `. Let V`+1 be a component S` i e adjacent to j=1 Vj which extends the partial witness in G. Such a component must exist, since witnesses are connected. Since   i e ). Recall > 16∆ V`+1 N , there are at least 16∆ N vertices which extend the witness (in G i i i e , then every vertex in V must be adjacent in G to all but at most that if Vj is adjacent to Vj 0 in G j αN vertices in Vji0 (and similarly if Vji is not adjacent to Vji0 ). Therefore, since W < 21 |H|2 and   i α = (16∆ |H|2 )−1 , there must be at least 16∆ N − W αN > 32∆ N choices for v`+1 ∈ V`+1 such that e j , v`+1 ) for all j ≤ `, which means that v`+1 extends the witness in G as well. Of E(vj , v`+1 ) = E(v these, at least  2 64∆ N must also have degree at most 65∆W c N . −1 −1 ), with high probability Γ (U ) contains such a vertex in step 13. Since each Ti Since |Ti | = O(∆ of the ` vertices selected so far is adjacent to at most 65cN vertices, there are at most `65cN candidates for v`+1 , and so the probability that the selected v`+1 extends the witness in G is at least /32∆ 2 −1 `65c = Ω((W c) ). Therefore, with high probability, the algorithm nds a complete witness in some iteration of steps 10-14 and rejects G. 2.3 Non-adaptively Testing BUC(H) Given a Promise We now show how to non-adaptively test whether a graph is in BU C(H), given the promise that G is O()-close to LD c . As in the adaptive case, the rst stage of the algorithm veries that most vertices are (∆, α)- 17 partitionable. Assuming the graph passes the rst stage, the second stage checks that the high-level structure of G is consistent with BU C(H). Since we can no longer adaptively restrict our queries to neighbors of a given vertex, we instead rely on the birthday paradox to achieve sub-quadratic query complexity. Recall that the birthday paradox says that, given a discrete domain D , O(|D|1−1/k ) uniformly-chosen samples suce to obtain a k -wise collision with high probability. We give a slightly generalized version here that will be useful for the following proofs. Lemma 18 (Birthday Paradox). Let D be a nite domain, and let {µi } be a set of probability distributions over D with µi (d) = Ω(1/ |D|) for all i and d ∈ D. Suppose that the i-th sample is drawn according to µi . Then O(|D|1−1/k ) samples suce to obtain a k-wise collision with high probability. c Proof. By assumption, there exists a xed 0 < c < 1 such that µi (d) > |D| for all i and d ∈ D . Let c α = |D| . Considering the following process. At step i, we select a sample according to µi . For each d ∈ D , we keep the sample with probability α µi (d) and discard it otherwise. Note that this process is equivalent to sampling from the distribution µ e over D ∪ {⊥} which selects d ∈ D with probability α and ⊥ with probability 1 − c and discarding any ⊥s. −1 M samples from µ e suce to obtain M non-discarded samples. Since With high probability, 2c the non-discarded samples are uniformly distributed, it follows from the standard birthday paradox −1 · O(|D|1−1/k ) = O(|D|1−1/k ) samples from µ e suce to obtain a k -wise collision with high that 2c probability. Since discarding samples can only increase the number of samples required to achieve a k -wise collision, the lemma follows. Very informally, in our setting a collision will correspond to choosing multiple vertices from a single witness in such a way that a W -wise collision corresponds to a complete witness. Assuming that the −1 ) and that we can sample from that set with only constant set of disjoint witnesses has size O( overhead, the birthday paradox implies that O(−1+1/W ) random vertices suce to nd all W vertices corresponding to a complete witness. Querying the entire induced subgraph then yields the 18 desired result. The primary challenge, therefore, is to show that when G is -far from BU C(H), the algorithm can eciently sample from the space of witnesses. The structure of the non-adaptive algorithm parallels the structure of the adaptive algorithm, especially with regards to proving correctness. Steps 2-4 of Algorithm 19 correspond to steps 2-8 of Algorithm 13 and check that most vertices are (∆, 0)-partitionable, where ∆ = deg(H). Steps 5-6 correspond to steps 9-16 of Algorithm 13 and check that the high-level structure of G is consistent with BUC(H). Algorithm 19. NonAdaptiveBlowUpCollectionTestH,c (G; ) 1: Let ∆ = deg(H), W = W (H), and α = (16∆ |H|2 )−1 . \\ Check that most vertices are (∆, 0)-partitionable. 2: Select a set S of O((α)−1+1/(∆+2) ) random vertices, and query S × S . 3: Select a set T of O(∆2 α−1 −1 ) random vertices, and query S × T . 4: If the current view of G is inconsistent with BU C(H), . Specically, reject if there exist v ∈ S and u1 , . . . , u∆+1 ∈ ΓS (v) such that ΓT (ui ) 6= ΓT (uj ) for all i, j . Reject \\ Check that G has a high-level structure consistent with H . 5: Select a set S of O((∆c2 )−1+1/W ) random vertices and query S × S . 6: If G|S 6∈ BUC(H), . 7: If the algorithm hasn't yet rejected, . Reject Accept −2+1/(∆+2) + −2+2/W ), as desired. Since it only rejects if it Algorithm 19 has query complexity O( nds a witness against G, it accepts all graphs in BU C(H) with probability 1. It remains to show that it rejects graphs which are far from BU C(H) with high probability. α Lemma 20. Let α = (16∆ |H|−2 )−1 , as in Algorithm 19, and let G be 16c -close to LDc and -far from BUC(H). Then Algorithm 19 rejects with probability at least 2/3. The proof is the content of section 2.3.1. 2.3.1 Proof of Lemma 20 The proof closely follows the structure of the proof for the adaptive case given in section 2.2.1. Because the arguments used in the non-adaptive case are more sensitive to the degrees of selected vertices than in the adaptive case, we will assume that G is α 16 -close to LD c , instead of only being  8 -close as in the adaptive case, where α < 1 is a xed constant. As in the adaptive case, we begin by noting that if G contains many vertices which are not (∆, α)partitionable, then G is rejected with high probability. 19 α Lemma 21. Let ∆ = deg(H), W = W (H), and α = (16∆ |H|2 )−1 . Suppose that G is 16c -close to LDc and contains at least 4c1 N vertices which are not (∆, α)-partitionable. Then Algorithm 19 rejects in step 4 with probability at least 2/3. Proof. For ease of exposition, we begin by proving the claim under the stronger assumption that G ∈ LDc . We then show how to modify the argument to only require that G be O()-close to LDc . We view the algorithm as choosing S one vertex at a time until a particular event occurs. We emphasize that this is merely a proof technique, since the algorithm is non-adaptive, and so the actual queries performed will be a superset of the ones described in the proof. Since witnesses are preserved under additional queries, this suces to prove the lemma. −1 ) sets, such As the samples are chosen, we will maintain an approximate partitioning of V into Θ( that each vertex belongs to at most ∆ sets and each set has size Ω(N ), and therefore a constant fraction of V is always covered. Intuitively, selecting a vertex from the k -th set will correspond to selecting the next vertex in the k -th witness, until a complete witness has been found. Formally, we initially partition the with |Uk | = S(α) 1 k=1 4c N vertices which are not (∆, α)-partitionable into −1 Uk , α 4c N . For each k , we initially say that Uk is uninitialized. The rst time that we select v ∈ Uk , we say that Uk becomes initialized with seed v , after which we will require that Uk ⊆ Γ(v). We now proceed to sample vertices at random. If the selected vertex u does not belong to any Uk , we discard that sample and try again. If u ∈ Uk for some k , we update the partitioning as follows. If Uk is uninitialized, then u must not be (∆, α)-partitionable (by construction), and we set Uk = Γ(u). Note that since u is not (∆, α)-partitionable, |Uk | > αN as required. update the remaining uninitialized Uk0 by removing any vertex v We also ∈ Uk0 such that v ∈ Γ(u) or |Γ(u) M Γ(v)| < 21 αN . Finally, we rebalance the sizes of the uninitialized Uk0 . Supposing for the moment that G ∈ LD c , we remove at most |Γ(u)| · cN/ S 1 2 −1 2 αN < 2c α N vertices in total from Uk . If Uk has been initialized with seed v , we proceed as follows. Let u1 , . . . , u` ∈ Γ(v), ` ≤ ∆, be the (non-seed) vertices which have been selected from Uk so far. We set Uk = Γ(v)\ ` [ Cv,α (ui ). i=1 Note that this ensures that ui ∈ Γ(v) and |Γ(ui ) M Γ(uj )| > αN for all i, j . Furthermore, since the 20 seed v is not (∆, α)-partitionable, we have |Uk | > αN . All other Uk0 are unchanged. We continue this way until either (i) ∆ + 2 samples have been chosen from a single Uk or (ii) at least half of the vertices in some initialized Uk belong to at least ∆ other initialized Uk0 . We claim −1+1/(∆+2) ) steps. that this occurs, with high probability, within O( 3 −1 )−1 of the To see this, suppose that condition (ii) has not occurred. First note that either (8c α 1 Uk have been initialized, or at least 8c N vertices are contained in the uninitialized Uk . Therefore, [ Uk > (8c3 α−1 )−1 · k so O(1) samples from V suce to sample from paradox, it follows that O(( α α2 N = 3 N = Ω(N ), 2∆ 8c S k Uk with high probability. By the birthday ∆ −1+1/(∆+2) ) = O(−1+1/(∆+2) ) samples suce to obtain the desired α ) (∆ + 2)-wise collision, with high probability. −1+1/(∆+2) ) steps, either In other words, after O( condition (ii) has occurred or we have selected v, u1 , . . . , u∆+1 from some Uk . Suppose that we selected v, u1 , . . . , u∆+1 from some Uk . Then with high probability, T contains a vertex from Γ(ui ) M Γ(uj ), for each i, j , and the algorithm rejects in step 4. If, instead, condition (ii) occurred, then there exist the seed vertices. With high probability, corresponding seed vertices. α 2 N vertices which are adjacent to ∆ + 1 of T contains such a vertex u. Recall that, by construction, Let v1 , . . . , v∆+1 be the |Γ(vi ) M Γ(vj )| > 12 αN for all seed vertices vi , vj . Therefore, with high probability, T contains a vertex in Γ(vi ) M Γ(vj ) for each i 6= j , and the algorithm rejects in step 4. Note that in the preceding argument, we only assumed that G ∈ LD c when bounding the number of vertices discarded after each step from the unitialized Uk0 . Note, however, that each additional discarded vertex implies an additional 1 α 2 αN distance from LD c . Since G was assumed to be 16c - close to LD c , we therefore delete at most an additional all steps. S It follows that | S 1 Uk , in total over 16c N vertices from k Uk | = Ω(N ), as required, and the rest of the proof goes through unchanged. By Lemma 21, either G is rejected with high probability by step 4 or we can apply Lemma 16 (since 21 α  e 16c < 8 ) to obtain G, as in the adaptive case. By Lemma 17, it follows that there are many disjoint e , which allows us to again apply the birthday paradox. witnesses against G fk } be the set of witnesses guaranteed by Lemma 17. As was shown in the Specically, let D = {W fk , there exist at least adaptive case, for any choice of v1 , . . . , v` corresponding to some W  32∆ N 2 fk in G. Therefore, O(W c ∆) samples suce to obtain choices for v`+1 which correctly extend W a vertex which extends some witness. Applying the birthday paradox, we see that step 5 nds a complete witness with high probability, in which case the algorithm rejects in step 6. We now formalize this argument. Proof of Lemma 20. If G is rejected with probability at least 2/3 by the rst part of Algorithm 19, then we are done. So suppose otherwise. Then by Lemma 21, G contains at most 1 4c N vertices e satisfying the conclusion of Lemma 16. So which are not (∆, α)-partitionable, and so there exists G 2 by Lemma 17, there exist at least (8W c ) i −1 distinct witnesses W fk . i As in the proof of Lemma 14, let V1 , . . . , V` , ` < W , be components corresponding to a partial witness in e. G In other words, ∗ ∗ (V1i , . . . , V`i ) = (Wji1 , . . . , Wji` ), for some i∗ and j1 , . . . , j` . Let i be a component adjacent to v1 , . . . , v` be arbitrary vertices in V1i , . . . , V`i , respectively. Let V`+1 S` i e j=1 Vj which extends the partial witness in G. Such a component must exist, since minimal witnesses are connected. Since   i e ). Also recall > 16∆ V`+1 N , there are at least 16∆ N vertices which extend the witness (in G i i i e , then every vertex in V must be adjacent in G to all but at most that if Vj is adjacent to Vj 0 in G j  1 2 i i i0 vertices in Vj 0 (and similarly if Vj is not adjacent to Vj 0 ). Therefore, since W < h , there 2 16∆h2 must be at least    e 16∆ N − W 16∆h2 N > 32∆ N choices for v`+1 such that E(vj , v`+1 ) = E(vj , v`+1 ) for all j ≤ `, which means that v`+1 extends the witness in G as well. k k ik We now map step 5 onto the birthday paradox. Given vertices v1 , . . . , v` in Vj ik tively, let Uk ⊆ Vj k,`+1 k,1 k , respec, . . . , Vjik,` fk in G. be the set of vertices which extend W We let D = {Uk } and µi be the probability distribution induced by selecting vertices uniformly at random. Since |Uk | >  2 32∆ N for all k and the Uk are disjoint, O(W c ∆) samples from V suce to −1+1/W ) samples suce to obtain a complete obtain a sample from D . Therefore, by Lemma 18, O( witness, which means that S contains a complete witness with high probability and the algorithm rejects in step 6. 22 2.4 Removing the Low-Degree Promise We now show how to test the combined property of being a valid blow-up collection and having low-degree. −1 )-query algorithm for testing whether the input has maximum e In [GR07], the authors give an O( degree O(N ). Lemma 22 ([GR07], Theorem 3). Fix c > 1 and β > 0. There exists a non-adaptive tester with e −1 ) and two-sided error which accepts graphs with maximum degree cN with query complexity O( probability at least 2/3 and rejects graphs which are β-far from having maximum degree cN with probability at least 2/3. To test whether G is in BU C(H) ∩ LD c , we therefore run the tester from Lemma 22, and if it accepts, we then run either the adaptive or non-adaptive tester for BU C(H). All that remains is to show that if G is -far from BU C(H) ∩ LD c , then it must be Ω()-far from BUC(H) or Ω()-far from LDc .   Lemma 23. Suppose that G is 18c∆ 2 -close to LD and 3 -close to BU C(H). Then G is -close to LD ∩ BUC(H).   Proof. Let 1 ≤ 18c∆ 2 be the distance to LD c and 2 ≤ 3 be the distance to BU C(H). Let V = S Vji be an optimal decomposition of G with respect to BU C(H).  Vji < 3∆ N . Next, we delete all superuous edges S i 2 and add all missing edges so that G ∈ BU C(H), at total cost at most 2 N . Note that since Vj is i First, we completely disconnect all Vj such that an optimal decomposition, every vertex must have been connected to at least half of its neighbors (otherwise we could reduce the cost by assigning that vertex to its own component). Therefore, at worst this doubled the degree of every vertex, thereby doubling the distance to LD . Note that G is now a valid blow-up collection. The total cost of the edits so far is bounded by 2 N 2 + P  Vji ∆ 3∆ N = 2 N 2 + 3 N 2 , since each component is adjacent to at most ∆ other components. For each i, j , if Vji > cN , delete Vji − cN vertices from Vji . This clearly preserves membership in BUC(H). Furthermore, the cost of doing the deletion is exactly equal to the decrease in distance i to LD c . To see this, note that every neighbor of Vj needed to delete at least Vji − cN into Vji to 23 become low-degree, and so without loss of generality, we can assume that they all delete the edges going to the same Vji − cN vertices. i Finally, while any high-degree vertices remain, we do the following. First, choose u ∈ Vj such that |Γ(u)| > cN and v ∈ Γ(u), and delete v . Note that the cost of doing so is, at most, cN · ∆ and the decrease in distance is at least  Vji > 3∆ N , for a net multiplicative overhead of 3c∆2 . 2 · 2 N 2 , which 1 The total cost of removing the high-degree vertices is therefore bounded by 3c∆ means that the nal cost is bounded by (2 N 2 +  N 2 ) + (3c∆2 · 2 N 2 ) ≤ N 2 as desired. 1 3 We now prove Theorems 5 and 6. Proof of Theorems 5 and 6. We rst run the tester from Lemma 22 with β = (18c∆(H)2 )−1 . If it accepts, we then run Algorithm 13 (in the adaptive case) or Algorithm 19 (in the non-adaptive case) with tolerance  3. If G ∈ LD c ∩ BU C(H), then the low-degree tester accepts with probability at 2/3 and blow-up collection tester accepts with probability 1. So G is accepted with probability at least 2/3. Suppose that G is -far from LD ∩ BUC(H). By Lemma 23, either G is is  -far from LD or G 18c∆2  3 -far from BU C(H). In the rst case, the low-degree tester rejects with probability at least 2/3. In the second case, the blow-up collection tester rejects with probability at least 2/3, by Lemma 14 (in the adaptive case) or Lemma 20 (in the non-adaptive case). 24 Chapter 3 An Alternate Proof that CliqueCollection has Adaptive Query e −1) Complexity O( −1 ), without any promise e In [GR09], the authors prove that testing the complexity of BU C(H) is O( on the degree bound, for the special cases where H is a self-loop and or H is a single edge. In the rst case, this corresponds to partitioning the graph into a disjoint collection of cliques, while the second case corresponds to a disjoint collection of bicliques. In both cases, the proof of correctness in [GR09] proceeds by assuming that the algorithm accepts with probability at least 1 3 and then constructs a partitioning with few incorrect edges. We now give an alternate proof for the case that H is a self-loop. Rather than show how to construct a good partitioning from the assumption that the graph was accepted with high probability, we instead directly show that if G is -far from BU C(H), then G is rejected with high probability. 3.1 The Adaptive Algorithm Informally, the algorithm begins by guessing the distribution of edits. It then nds a vertex with many adjacent edits. Finally, it queries a small neighborhood of that vertex in order to verify the proposed witness. Although the algorithm stated here uses polylogarithmically fewer queries than the one given in [GR09], it is best viewed as a slight rephrasing of the one given in [GR09]. Algorithm 24. CliqueCollection(G; ) 1: for i = 1 to lg 1 + O(1) do 25 2: for O(2i ) trials do 3: Select u at random. 1 1 i 4: Select S at random, with |S| = O( lg /2 ).   5: Query (u, s) for all s ∈ S . 6: Select T ⊂ ΓS (u), with |T | = O(1). 7: Query T × T , and if any queries return 0. 8: Query T × S\T , and if any queries return 1. 9: end for 10: end for 11: . Reject Reject Accept The query complexity is clearly O( 1 2 1  lg  ). The algorithm clearly accepts all G ∈ CC . It remains to show that it rejects with probability at least 2/3 whenever G is -far from CC . Theorem 25. If G is -far from CC , then CliqueCollection rejects with probability at least 2/3. To prove Theorem 25, we will frequently refer to the number of edits adjacent to a vertex. Formally, e = arg minH∈CC d(G, H), we dene the number of edits to be letting G e Γ(u) M Γ(u) . The key lemma for proving Theorem 25 is the following. e ≤ 2γi N , Lemma 26. Let γi = lg2i 1 . If the vertex u selected in step (3) has γi N ≤ Γ(u) M Γ(u) then CliqueCollection rejects with probability at least 1/3.  Proof of Theorem 25. Note that since G is -far from CC , there exists p, γ , with  ≤ p, γ ≤ 1 and pγ ≥ / lg 1 , such that at least pN vertices are adjacent to between γN and 2γN edits. Consider the iteration of the outer loop in which 2 i ≈ p. With high probability, Ω(1) vertices are selected in step (3) which are adjacent to between γN and 2γN vertices. Therefore, by Lemma 26, CliqueCollection rejects with probability at least 1 − ( 32 )Ω(1) > 2/3. 3.2 Proof Of Lemma 26 The proof is essentially a case analysis of the ways in which G can be -far from BU C(H). Given a graph G, let G = arg minH∈CC d(G, H) be the clique collection closest to G. By a slight abuse of notation, we refer to the induced V i as the cliques of G. We will generally refer to the V i without explicit reference to G .1 1 We assume that ties are broken in a canonical way, so this is well-dened. 26 For ease of notation, we let Γi (u) = Vi ∩Γ(u), Γi (v) = V i \Γ(u), and Γ0 (u) = Γ(u)\V i , where u ∈ V i . Since G minimizes d(G, G), we have the following observations. Observation 27. For all Γ ⊂ V i , E(Γ, V i \Γ) ≥ 12 |Γ| V i \Γ . Observation 28. For all i 6= j , E(V i , V j ) ≥ 12 V i V j . i For Observation 27, we could otherwise reduce the distance by splitting V . For Observation 28, we could otherwise reduce the distance by joining V i and V j . Lemma 29. Given Γ = {v1 , . . . , vn } such that V i < n/6 for all i such that Γ∩V i 6= ∅, Pr[(vj , vk ) ∈ E] < 43 . Proof. Let p = Pr[(vj , vk ) ∈ E], and let ni = V i ∩ Γ . Then the cost of moving Γ into its own clique is bounded above by X ni V i − ni 2
 + (1 − p) n2
 − p n2 i
− X ni 2
 i which is bounded by n· This is negative for p ≥

n + (1 − p) n2 − p n2 < 23 n2 − pn2 + pn 6 3 4 and suciently large n. We are now ready to prove the lemma. Let u be a vertex selected in step 3 which is adjacent to between γN and 2γN edits. Note that since |S| = Ω(1/γ), with high probability S contains Ω(1) vertices v such that (u, v) is an incorrect g ). edge (ie, is in Γ(u) M Γ(u) Let V i be the clique containing u. Case 1: Γi (u) ≥ |Γ0 (u)| Since |Γi (u)| ≥ Γi (u) , it follows that, with high probability, |Γi (u) ∩ ΓS (u)| ≥ 14 |ΓS (u)|. thermore, |ΓS (u)| = Ω(1), since |Γi (u)| > γ 2 N . Therefore, with high probability, T contains Ω(1) i vertices in V . Since Fur- Γi (u) ≥ γ2 N , Γi (u) ∩ S = Ω(1), with high probability. 27 We therefore have that step (8) contains Ω(1) queries between Γi (u) and Γi (u). By Observation 27, each of these queries causes the algorithm to reject with probability at least 1/2. Case 2: γ |V i | ≥ 100 N and Γi (u) < |Γ0 (u)| First, note that since γ 1 V i > 100 N and |Γ0 (u)| < 2γN , |Γi (u)| ≥ 200 |Γ0 (u)|. Therefore, with high i probability, G contains Ω(1) vertices in V . j Next, note that with high probability, there exists v ∈ ΓS (u) ∩ V , for some j 6= i. We have multiple cases, depending on the values of Γi (u), Γi (v), Γj (u), and Γj (v). We rst note that if Γi (v) > 0.9ni , then V j ≥ 0.8 V i . For if not, the cost of moving v to V i would be upper-bounded by 0.1ni + nj − 0.9ni < 0.8ni − 0.8ni = 0. Case 2a: Γi (u) < 0.95 V i Then Γi (u) ∩ S = Ω(1), with high probability. We therefore make Ω(1) queries between Γi (u) and Γi (u) in step (7). By Observation 27, each of these causes the algorithm to reject with probability at least 1/2. Case 2b: Γi (u) > 0.95 V i and Γi (v) < 0.9 V i Then Γi (u) ∩ Γi (v) ∩ S = Ω(1), with high probability. We therefore reject in step (7) with cer- tainty. Case 2c: Γi (u) > 0.95 V i , Γi (v) > 0.9 V i , and Γj (u) < 0.75 V j First, note that V j > 0.8 V i , for otherwise we would move v into V i . Therefore, with high probability, S contains a vertex w ∈ Γj (u). Since v was uniformly chosen from Γj (u), Pr[(v, w) ∈ E] ≥ 1 2 , by Observation 27. Case 2d: Γi (u) > 0.95 V i , Γi (v) > 0.9 V i , and Γj (v) ≥ 0.6 V j With high probability, S contains Ω(1) vertices in Γj (v). We therefore query Ω(1) random edges between 0.95V i and 0.6V j in step (7). But E(V i , V j ) ≤ 1 2 V i V j , so each such query cause a 28 rejection with probability at least 0.95 V i · 0.6 V j − 21 V i V j ≈ 0.12 0.95 |V i | · 0.6 |V j | Case 2e: Γi (u) > 0.95 V i , Γi (v) > 0.9 V i , Γj (u) > 0.75 V j and Γj (v) < 0.6 V j Since γ N , with high probability S contains Ω(1) such vertices. Each Γj (u) ∩ Γj (v) > 0.15 V j ≥ 25 2 of these causes the algorithm to reject with certainty. Case 3: γ N , Γi (u) < |Γ0 (u)| |V i | < 100 0 We have two subcases, depending on whether Γ (u) is primarily contained in large or small cliques. 0 Given v ∈ Γ (u), let V j 3 v. Case 3a: Pr[ V j ≥ 24γ N ] ≥ 1/2 With high probability, T contains a vertex v ∈ V Note that j such that γ V j ≥ 24 N. γ N . So with high probability, there exists w ∈ S ∩ Γj (u). By Observation 27, Γj (u) > 100 Pr[(v, w) ∈ E] ≥ 12 , so the algorithm rejects in step (8) with high probability. Case 3b: Pr[ V j ≥ 24γ N ] < 1/2 0 e = {v ∈ Γ (u) Let Γ e ≥ γ N . With high probability, T contains : V j > γ8 N }. By assumption, Γ 4 e . Therefore, in step (7), we makes Ω(1) queries from Γ e×Γ e , each of which causes Ω(1) vertices in Γ the algorithm to reject with probability at least 1/4, by Lemma 29. 2  Case 2e cannot actually happen. For if Γi (v) > 0.9ni and Γj (v) < 0.6nj , then the cost of moving v to V i is bounded by 0.1ni + 0.6nj − 0.9ni − 0.4nj = 0.2nj − 0.8ni , which means that nj > 4ni . But then the cost of moving u to V j is bounded by ni + 0.25nj − 0.75nj < 0.25nj + 0.25nj − 0.75nj < 0. 29 Chapter 4 Towards Proving an Upper Bound on the Adaptive Query Complexity of BU C(H) for Arbitrary H Although the results given in [GR09] and Chapter 2 provide strong evidence that the canonical transformation is essentially optimal, proving that result for properties which are neither promise problems nor proximity-dependent remains open. In this section, we restate the main structural lemmas of [GR09], used in that paper for proving the query complexity of BU C(H) when H is a single loop or single edge, in the context of general H . Although these proofs are essentially direct adaptations of those given in [GR09], we feel that formally stating the general case yields additional insight as to the key combinatorial diculties. The two key concepts needed to discuss blow-up collections of an arbitrary base graph are and skeletons inconsistent edges. Informally, a skeleton is a set of vertices which are believed to belong to dierent components of the blow-up collection. An inconsistent edge, relative to a skeleton, is an edge which contradicts the proposed decomposition. Denition 30 (Skeleton). A set T ⊆ V is a skeleton if ΓT (u) 6= ΓT (v) for all u, v ∈ T . Given S ⊆ V , skeleton(S) ⊆ S is the largest skeleton contained in S . Note that a skeleton of size |H| + 1 is a witness against BU(H) and a connected skeleton is a witness against BUC(H). Also note that if S is connected, skeleton(S) is connected. Denition 31 (Inconsistent Edge). Fix T ⊆ V . An edge (v, w) is inconsistent with T if ΓT 0 (v) 6= ΓT 0 (u) for all u ∈ T , where T 0 = T ∪ {v, w}. 30 Given these two denitions, we conjecture that the following algorithm, informally described in [GR09] for the case that H is a simple cycle, correctly tests BU C(H) for all H . Algorithm 32. SubTest(u; δ) 1: Let T = {u}. 2: while |T | ≤ |H| do 1 3: Choose O( ) vertices S . δ 4: Query T × S . 1 5: Choose O( ) edges uniformly from ΓS (T ) × ΓS (T ) and query them. δ 1 6: Choose O( ) edges uniformly from ΓS (T ) × S\ΓS (T ) and query them. δ 7: If an inconsistent edge (v, w) was found in steps 4-6, T ← skeleton(T ∪ {v, w}). 8: Else break. 9: end while 10: If G|T 6⊆ H , . Otherwise, . reject accept Algorithm 33. BlowUpCollection(G; ) 1: for i = 1 to lg 1 + O(1) do SubTest 2: Run (u; 2i ) for O(2i ) randomly chosen u. 3: end for 4: if all calls to accepted. if any call rejected. Accept 4.1 SubTest Reject Basic Behavior of SubTest Before stating the key lemmas, we formally dene the two ways in which a graph can fail to be a valid blow-up collection. Denition 34. Given C ⊆ V , let EI (C) = d(G|C , BU C(H)) be the number of edits required to make C a valid blow-up collection of H , and let EE (C) = |E(C, V \C| be the number of edits needed to disconnect C from the rest of G. Let E(C) = EI (C) + EE (C). Given a skeleton T ⊆ C such that C = Γ(T ), note that E(C) is at most the number of edges in C that are inconsistent with T . Given a skeleton T , we say that T is terminal if SubTest terminates on T . Unless otherwise specied, all skeletons are assumed to be terminal. Let CT = {u ∈ Γ(T ) : |Γ(u)\Γ(T )| < 1 5 |Γ(T )|}. The following 3 lemmas and their proofs are essentially restatements of the proofs in [GR09], Claims 3.2.2 and 3.2.4 (and the surrounding discussion). 31 Lemma 35. Fix T such that |Γ(T )| > δN and steps 4-6 fail to nd any inconsistent edges with δ probability 1/3. Then |Γ(T )\CT | < 10 N. Proof. Suppose otherwise. Then there are α |Γ(T )| vertices connected to βN external edges, where |Γ(T )| δN α = 10|Γ(T )| and β = 10N . By a Cherno bound, S contains at least 1 α |Γ(T )| c c · · > 2 N δ 8 such vertices with high probability. Consider such a high-degree vertex u. By a Cherno bound, |Γ(u) ∩ S| > β2 δc with high probability Therefore, with high probability, (Γ(T ) ∩ S) × (S\Γ(T )) contains at least β δ α |Γ(T ) ∩ S| · |S\Γ(T )| > |Γ(T ) ∩ S| · |S\Γ(T )| 2 2 16 edges. So with high probability, step 6 nds such an edge. Lemma 36. Fix T such that |Γ(T )| > δN and steps 4-6 fail to nd any inconsistent edges with probability 1/3. Then EE (CT ) < δ |CT | N . δ Proof. By lemma 35, |E(CT , Γ(T )\CT )| ≤ |CT | |Γ(T )\CT | < 10 N |CT |. We claim that |E(CT , V \Γ(T ))| < δ 2 N |CT |. Suppose otherwise. Then there must be at least α |Γ(T )| vertices in CT which are connected to at least βN vertices in V \Γ(T ), where αβ = δ 1 δN 4 . Note that since βN < 5 |Γ(T )|, α > 4|Γ(T )| . Therefore, by the same calculation as in the proof of lemma 35, with high probability step 6 nds such an edge. Lemma 37. Fix T such that |Γ(T )| > δN and steps 4-6 fail to nd any inconsistent edges with probability 1/3. Then EI (CT ) < δ |CT | N . Proof. Suppose otherwise, and let ρ= δ |Γ(T )| N δN δ |CT | N > 2 = |Γ(T )| |Γ(T )| 2 |Γ(T )| 32 denote the lower bound on the fraction of inconsistent edges in Γ(T ) × Γ(T ). Clearly, E[|ΓS (T )|] = |Γ(T )| c )| c · δ , and so with high probability, |ΓS (T )| > |Γ(T · 2δ . We assume that N N this is the case, and let n = |ΓS (T )|. Note that |ΓS (T )| > c 2. ∈ ΓS (T ), dene an indicator variable ζij which is 1 if (vi , vj ) is P P inconsistent with T . By assumption, E[ζij ] ≥ ρ. We now bound V[ ζij ]/ E[ ζij ]2 ; it then follows For each pair of vertices vi , vj that the fraction of inconsistent edges in ΓS (T ) × ΓS (T ) is at least ρ/2 with high probability, and so step 5 nds such an edge with high probability. Note that ζij and ζi0 j 0 are independent if {vi , vj } ∩ {vi0 , vj 0 } = ∅. Let ρ e = E[ζij ]. We have E X  ζij i,j   n g n2 ρe = rho > 2 3 and V X  ζij = E  X ij 2  ζij −E X i,j =E  X X ζij i,j  ζij ζi0 j 0 − i,j,i0 ,j 0 = 2 X E[ζij ] E[ζi0 j 0 ] iji0 j 0 E[ζij ] E[ζi0 j 0 ] + i,j,i0 ,j 0 X i,j,i0 ,j 0 disjoint otherwise X X < E[ζij ζi0 j 0 ] < 4 i,j,i0 ,j 0 X E[ζij ] = 4n i,j,j 0 X E[ζij ] E[ζi0 j 0 ] iji0 j 0 E[ζij ζij 0 ] i,j,j 0 disjoint ≤4 E[ζij ζi0 j 0 ] − X E[ζij ] i,j   n = 4n ρe < 2n3 ρe 2 Combining these bounds, and the fact that ρ e ≥ ρ, we get P V[ i,j ζij ] 18 18 |Γ(T )| 2δN 36 2n3 ρe P ≤ < 18 = < < 2 2 2 (n ρe/3) ne ρ nρ δN c |Γ(T )| c E[ i,j ζij ] which can be made arbitrarily small. We now combine the previous three lemmas to show that if SubTest(v; δ) accepts with reasonable probability, then we can construct a component containing v which is close to being an isolated 33 blow-up. Corollary 38. If SubTest(v; δ) accepts with probability at least 13 , then there exists C 3 v such that E(C) < 2δN · |C|. Proof. If |Γ(v)| < δN , then let C = {v}. SubTest terminates with high probability. Note that such a T must exist, since otherwise SubTest would have rejected after |H|+1 iterations. Otherwise, let T be a skeleton containing v such that Set C = CT . By lemmas 37 and 36, E(CT ) = EI (CT ) + EE (CT ) < 2δ |CT | N , as desired. 4.2 Sketch of the Reconstruction Procedure Given a skeleton T , we say that T is δ -good if steps 4-6 fail to nd an inconsistent edge and T is consistent with H . Similarly, we say that T is not δ -good if T is not consistent with H . Otherwise, we recursively say that T is δ -good if and only if, with high probability over the choice of inconsistent edge (v, w) in step 7, skeleton(T ∪ {v, w}) is δ -good. Call a vertex u δ -good if {u} is δ -good and |Γ(u)| > δN . Lemma 39. If algorithm 33 accepts with probability at least 1/3, then there are at most 2−i N vertices which are not 2i -good and have degree at least 2i N , for each i < lg −1 . The lemma follows immediately from the denition of i-goodness. Informally, we now show how to construct a blow-up collection close to G. The procedure progresses in rounds. In the initial round, while there remains an uncovered vertex v which is -good, let C be the component guaranteed by lemma 38 and x that component. Once all -good vertices have been covered, disconnect all uncovered low-degree vertices and then go on to the next round. i In general, during the i-th round, we x any remaining 2 -correct vertices and then disconnect any leftover low-degree vertices. Suppose that the components constructed in this procedure were actually disjoint. Then the total 34 cost of the procedure would be bounded by XX i 2i  |C| N < X 2i  · 2−i N · N = N 2 i C i since at most 2 vertices are incorrect at the start of the i-th round. All that remains, therefore, is to show that we can select the components to be essentially disjoint (ie, S such that | C| ≈ P |C|), while still covering most of the i-good vertices in each round. Specically, we will require that each additional component constructed by the reconstruction procedure contain a constant fraction of new vertices. The challenge will then be to ensure that enough vertices are covered during each round. Since the reconstruction will not yield a strict partitioning, the following observation will be needed. Lemma 40. Let C = S i Ci , with the Ci s not necessarily disjoint. Then E(C) < P E(Ci ). Proof. Consider the partitioning of C obtained by assigning each v ∈ C arbitrarily to some Ci which fi ⊆ Ci , use the structure inherited from Ci . contains it. Within each partition C Note that P fi ) ≤ EI (C P EI (Ci ). Similarly, P fi ) ≤ EE (C P EE (Ci ). Since any partitioning provides an upper bound on E(C), it follows that E(C) ≤ P P EI (Ci ) + EE (Ci ) = E(Ci ), as desired. 4.3 The Reconstruction Procedure As stated in the previous discussion, the reconstruction proceeds in rounds i = 1 . . . , lg 1 . Throughout this section, we informally let C be the set of vertices which have been covered by the reconstruction, Fi be the set of skeletons used in round i, Ri be the set of vertices which are not yet covered at the start of round i, Li be the set of vertices discarded as low-degree at the end of round i, and L = S j<i Lj be the vertices which have been discarded as low-degree so far. These will be formally dened later. 35 4.3.1 Cliques We begin with a discussion of the simplest case, in which H is a single loop. This proof was given in [GR09], but we give it here for completeness, and for comparison to the general case. 1. Pick an arbitrary vertex v ∈ Ri−1 \C such that (a) v is δ -good (b) |Γ(v)| > δN (c) 1 |Γ(v) ∩ (C ∪ L)| ≤ 10 |Γ(v)| 2. For a vertex v selected in step 1, update Fi ← Fi ∪ {T } and C ← C ∪ Cv . 3. If no such vertices remain, set Li = {v ∈ Ri−1 \C : |Γ(v)| < δN } and Ri = Ri−1 \(C ∪ Li ). Update L ← L ∪ Li . We now show that this yields a good partitioning of most remaining vertices. Lemma 41. Suppose |Ri−1 | < 2−i−1 N . Then P v∈Fi E(Cv ) < N 2. 1 |Γ(v)| (by condition (1c)), Proof. Consider v ∈ Fi . Since |Γ(v)| > δN and |Cv ∩ (C ∪ L)| < 10 1 |Γ(v)|. By lemma 35, it follows that Cv is at least half new vertices. |Cv ∩ (C ∪ L)| < 10 Therefore, P v∈Fi |Cv | < 2 |Ri |, and the result follows from corollary 38. We now show that, despite condition (1c), most high-degree vertices are still covered. Lemma 42. For all i, Ri < 2−i N . Proof. We proceed by induction on i. For i = 0, the claim is trivial. Any vertex in Ri is either not δ -good, or has |Γ(v)| > δN and |Γ(v) ∩ (C ∪ L)| > By lemma 39, there are at most 1 δ 10 |Γ(v)| > 10 N . 1 −i 2 2 N vertices which are not δ -good. fi ⊂ Ri be the set of δ -good vertices which remain at the end of round i, and consider some Let R fi . Since v is δ -good, at most 1 of it's neighbors have degree less than δN , which means that it v∈R 2 has at least δ 20 N neighbors in C . The total number of edges between Ri and C is therefore at least fi δ N . But by lemma 41, the total number of such edges is at most N 2 . So R fi < 1 2−i N . R 10 2 36 The key simplication that occurs in this case, as opposed to general H , is that Cv has large overlap with C ∪ L if and only if Cv has large overlap with C . 4.3.2 General H We now consider the general case. As with the case for cliques, we again use a more stringent selection criteria, and then attempt to argue that Ri remains small. 1. Pick an arbitrary vertex v ∈ Ri−1 \C and u1 , . . . , uk such that uj ∈ Γ(v ∪ (a) T = {v, u1 , . . . , uk } is δ -good (b) |Γ(v)| > δN (c) 1 |Γ(v) ∩ (C ∪ L)| ≤ 10·2 H |Γ(v)| (d) |Γ(T ) ∩ (C ∪ L)| < 10·21H−j |Γ(T )| S `<j u` ) such that 2. For a skeleton T selected in step 1, update Fi ← Fi ∪ {T } and C ← C ∪ CT . 3. If no such skeletons remain, set Li = {v ∈ Ri−1 : |Γ(v)| < δN } and Ri = Ri−1 \(C ∪ Li ). Update L ← L ∪ Li . As in the case of cliques, it suces to bound the size |Ri |, as shown by the following lemma. Lemma 43. Suppose |Ri−1 | < 2−i−1 N . Then P T ∈Fi E(CT ) < N 2. Proof. Let δ = 2i  and consider T ∈ Fi . Since |Γ(T )| > δN and |CT ∩ (C ∪ L)| < 51 |Γ(T )| (by condition (1d)), |CT ∩ (C ∪ L)| < 1 5 |Γ(T )|. By lemma 35, it follows that CT is at least half new vertices. Therefore, P T ∈Fi |CT | < 2 |Ri |, and the result follows from corollary 38. Unfortunately, we do not know how to show that most high-degree vertices are still covered, despite conditions (1c) and (1d). Conjecture 44. For all i, Ri < 2−i N . The key diculty in proving Conjecture 44 is that a good vertex can have many neighbors which are low-degree. Specically, we have that each δ -good vertex which has not been covered after round i 37 has at least δN edges into C ∪ L. To obtain the bound on |Ri |, we therefore want to show that the −i N = N 2 . total number of edges leaving C ∪ L is at most δN · 2 For the special case where H is a clique, we argued that most of the edges between v and C ∪ L were actually between v and C . Since the number of edges leaving C is bounded by the number of edits allowed, and that tolerance is essentially a free parameter of the algorithm/reconstruction, we could force the upper bound to be as small as necessary. In this case, however, the edges could be from v to L. As a result, both the upper- and lower-bound depend on the degree bound used to dene L. 38 Chapter 5 Conclusions and Open Problems We have shown that there exist proximity-dependent graph properties for which a non-adaptive tester must suer an almost-quadratic increase in its query complexity over an adaptive tester. This gives evidence that the canonical transformation is essentially optimal, in the worst case. The primary open problem is to remove the proximity-dependence from the graph properties used in Theorem 3. In particular, for any δ > 0, does there exist a testing Π requires Q = Ω(q single graph property Π such that 2−δ ) queries for all  > 0? It also remains to determine whether there exists a nearly-quadratic separation when the adaptive algorithm is only allowed one-sided error. −1 ) upper-bound for the adaptive query e One approach to both of these questions is to prove an O( complexity of BU C(H) for general graphs, as sketched in chapter 4. We also reiterate the intriguing question raised in [GR09] as to what relationships are possible between the adaptive and non-adaptive query complexities. Specically, do there exists properties e such that Q = Θ(q 2−δ ), with δ 6= 2 ? In particular, is it true that Q must either be Θ(q) e e 4/3 )? or Ω(q t Finally, it remains to determine whether a gap exists between adaptive and non-adaptive property −2 ). In particular, does there exist a gap testers for properties with adaptive query complexity Ω( when q = Ω(1) as a function of N ? A plausible conjecture is that the non-adaptive query complexity is e −1 · q), or potentially even that the canonical query complexity is Q e = O( e −1 · q). Q = O( Unfortunately, we do not currently have any idea how to prove (or disprove) such a conjecture. 39 Bibliography [AG11] Lidor Avigad and Oded Goldreich. Testing graph blow-up. In Leslie Goldberg, Klaus Jansen, R. Ravi, and José Rolim, editors, Approximation, Randomization, and Com- binatorial Optimization. Algorithms and Techniques, volume 6845 of Lecture Notes in Computer Science, pages 389399. Springer Berlin / Heidelberg, 2011. [Alo01] N. Alon. Testing subgraphs in large graphs. In Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, FOCS '01, pages 434, Washington, DC, USA, 2001. IEEE Computer Society. [AS06] Noga Alon and Asaf Shapira. A characterization of easily testable induced subgraphs. Comb. Probab. Comput., 15:791805, November 2006. [Avi09] Lidor Avigad. On the lowest level of query complexity in testing graph properties. Master's project, Weizmann Institute of Science, Department of Computer Science and Applied Mathematics, December 2009. [BLR90] M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical problems. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, STOC '90, pages 7383, New York, NY, USA, 1990. ACM. [CRT05] Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. Approximating the minimum spanning tree weight in sublinear time. [GGR98] SIAM J. Comput., 34:13701379, June 2005. Oded Goldreich, Sha Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45:653750, July 1998. [GKNR09] Oded Goldreich, Michael Krivelevich, Ilan Newman, and Eyal Rozenberg. theorems for property testing. In Hierarchy Proceedings of the 12th International Workshop and 40 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX '09 / RANDOM '09, pages 504519, Berlin, Heidelberg, 2009. Springer-Verlag. [GR97] Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. In Proceed- ings of the twenty-ninth annual ACM symposium on Theory of computing, STOC '97, pages 406415, New York, NY, USA, 1997. ACM. [GR00] Oded Goldreich and Dana Ron. On testing expansion in bounded-degree graphs. Elec- tronic Colloquium on Computational Complexity, 7, 2000. [GR07] Mira Gonen and Dana Ron. On the benets of adaptivity in property testing of dense graphs. In Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX '07/RANDOM '07, pages 525539, Berlin, Heidelberg, 2007. Springer-Verlag. [GR09] Oded Goldreich and Dana Ron. Algorithmic aspects of property testing in the dense graphs model. In Proceedings of the 12th International Workshop and 13th Interna- tional Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX '09 / RANDOM '09, pages 520533, Berlin, Heidelberg, 2009. Springer-Verlag. [GT03] Oded Goldreich and Luca Trevisan. Three theorems regarding testing graph properties. Random Struct. Algorithms, 23:2357, August 2003. [KKR04] Tali Kaufman, Michael Krivelevich, and Dana Ron. Tight bounds for testing bipartiteness in general graphs. [PR02] SIAM J. Comput., 33:14411483, June 2004. Michal Parnas and Dana Ron. Testing the diameter of graphs. Random Struct. Algo- rithms, 20:165183, March 2002. [RS96] Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials withapplications to program testing. [RS06] SIAM J. Comput., 25:252271, February 1996. Sofya Raskhodnikova and Adam Smith. A note on adaptivity in testing properties of bounded degree graphs. Electronic Colloquium on Computational Complexity, 13, 2006.