Alon 和Krivelevich (SIAM J. Discrete Math. 15(2): 211-227 (2002)) 證明了如果一個圖是ε -非二部圖，那麼階數為Ỡ(1/ε) 的隨機導出于圖以很大概率是非二部圖。我們進一步猜想，這個導出子圖以很大概率是Ω(ε)-非二部圖。Gonen 和Ron (RANDOM 2007) 證明了當圖的最大度不超過O (εn )時猜想成立。我們將對更一般的情形給出證明，對於任意d，所有d 正則(或幾乎d 正則)的圖猜想成立。 / 假設猜想成立的情況下，我們證明二分屬性是可以被單側誤差在O(1/ε^c ) 時間內檢驗的，其中c 是一個嚴格小於2 的常數，而這個結果也改進了Alon 和Krivelevich 的檢驗算法。由於己知對二分屬性的非適應性的檢驗算法需要Ω(1 /ε²) 的複雜性(Bogdanov 和Trevisan ， CCC 2004) ，我們的結果也得出，假設猜想成立，適應性對檢驗二分屬性是有幫助的。 / 另外一個有很多屬性檢驗問題被廣泛研究的領域是布爾函數。對布爾函數單調性的檢驗也是屬性檢驗的經典問題。給定對布爾函數f: {0,1}{U+207F} → {0,1} 的訪問，在[18]中，證明了檢驗算法複雜性的下界是Ω(√n) 。另一方面，在[21]中，作者們構造了一個複雜性為O(n) 的算法。在本文中，我們刻畫一些單調布爾函數的本質，設計算法并分析其對於一些困難例子的效果。最近，在[14] 中， 一個類似的算法被證明是非適應性，單側誤差，複雜性為Ỡ (n⁵/⁶ ε⁻⁵/³) 的算法。 / Alon and Krivelevich (SIAM J. Discrete Math. 15(2): 211-227 (2002)) show that if a graph is ε-far from bipartite, then the subgraph induced by a random subset of Ỡ (1/ε) vertices is not bipartite with high probability. We conjecture that the induced subgraph is Ω(ε)-far from bipartite with high probability. Gonen and Ron (RANDOM 2007) proved this conjecture in the case when the degrees of all vertices are at most O(εn). We give a more general proof that works for any d-regular (or almost d-regular) graph for arbitrary degree d. / Assuming this conjecture, we prove that bipartiteness is testable with one-sided error in time O(1=ε{U+1D9C}), where c is a constant strictly smaller than two, improving upon the tester of Alon and Krivelevich. As it is known that non-adaptive testers for bipartiteness require Ω(1/ε²) queries (Bogdanov and Trevisan, CCC2004), our result shows, assuming the conjecture, that adaptivity helps in testing bipartiteness. / The other area in which various properties have been well studied is boolean function. Testing monotonicity of Boolean functions is a classical question in property testing. Given oracle access to a Boolean function f : {0, 1}{U+207F} →{0, 1}, in [18], it is shown a lower bound of testing is Ω(√n). On the other hand, in [21], the authors introduced an algorithm to test monotonicity using O(n) queries. In this paper, we characterize some nature of monotone functions, design a tester and analyze the performance on some generalizations of the hard case. Recently, in [14], a similar tester is shown to be a non-adaptive, one-sided error tester making Ỡ (n⁵/⁶ ε⁻⁵/³) queries. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Li, Fan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 76-79). / Abstracts also in Chinese. / Abstract --- p.i / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Property Testing --- p.1 / Chapter 1.2 --- Testing Bipartiteness --- p.4 / Chapter 1.3 --- Testing Monotonicity --- p.7 / Chapter 2 --- Testing Bipartiteness --- p.11 / Chapter 2.1 --- Background --- p.11 / Chapter 2.1.1 --- Our result --- p.11 / Chapter 2.1.2 --- The algorithms of Gonen and Ron --- p.13 / Chapter 2.1.3 --- Our proof --- p.16 / Chapter 2.1.4 --- Notation --- p.19 / Chapter 2.2 --- Splitting the vertices by degree --- p.19 / Chapter 2.3 --- The algorithm for high degree vertices --- p.20 / Chapter 2.4 --- Eliminating the high degree vertices --- p.22 / Chapter 2.5 --- From an XOR game to a bipartite graph --- p.33 / Chapter 2.6 --- Proof of the main theorem --- p.35 / Chapter 2.7 --- Proof of the conjecture for regular graphs --- p.37 / Chapter 3 --- Testing Monotonicity --- p.40 / Chapter 3.1 --- Towards an improved tester --- p.40 / Chapter 3.1.1 --- Properties of Distribution D --- p.42 / Chapter 3.1.2 --- An Alternative Representation of D --- p.46 / Chapter 3.1.3 --- Performance of D on Decreasing Functions --- p.51 / Chapter 3.1.4 --- Functions Containing Ω(2{U+207F}) Disjoint Violating Edges --- p.54 / Chapter 3.2 --- A o(n) Monotonicity Tester [14] and Some Improvements --- p.62 / Chapter 3.2.1 --- A o(n) Monotonicity Tester [14] --- p.62 / Chapter 3.2.2 --- An Alternative Proof of Theorem 3.2.2 --- p.65 / Chapter 4 --- Other Related Results --- p.67 / Chapter 4.1 --- Short Odd Cycles in Graphs that are Far From Bipartiteness --- p.67 / Chapter 4.2 --- Fourier Analysis on Boolean Functions --- p.69 / Bibliography --- p.76
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_328436 |
| Date | January 2013 |
| Contributors | Li, Fan., Chinese University of Hong Kong Graduate School. Division of Computer Science and Engineering. |
| Source Sets | The Chinese University of Hong Kong |
| Language | English, Chinese |
| Detected Language | English |
| Type | Text, bibliography |
| Format | electronic resource, electronic resource, remote, 1 online resource (vi, 79 leaves) |
| Rights | Use of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/) |
Page generated in 0.0022 seconds