請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41325完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 呂育道 | |
| dc.contributor.author | Yen-Wu Ti | en |
| dc.contributor.author | 狄彥吾 | zh_TW |
| dc.date.accessioned | 2021-06-15T00:15:51Z | - |
| dc.date.available | 2014-06-24 | |
| dc.date.copyright | 2009-06-24 | |
| dc.date.issued | 2009 | |
| dc.date.submitted | 2009-06-10 | |
| dc.identifier.citation | [1] A. Abdollahi, A. Faghihi and A. M. Hassanabadi, 3-generator groups whose
elements commute with their endomorphic images are abelian, Communications in Algebra, 36(10) (2008), pp. 3783--3791. [2] A. Abdollahi, A. Faghihi and A. M. Hassanabadi, Minimal Number of Gener- ators and Minimum Order of a Non-Abelian Group whose Elements Commute with Their Endomorphic Images, Communications in Algebra, 36(5) (2008), pp. 1976--1987. [3] S. B. Akers and B. Krishnamurthy, A group-theoretic model for symmetric inter- connection networks parallel processing, International Conference Parallel Pro- cessing, (1986), pp. 216--233. [4] N. Alon, E. Fischer, M. Krivelevich and M. Szegedy, E±cient Testing of Large Graphs, FOCS (1999), pp. 656--666. [5] N. Alon, E. Fischer, I. Newman and A. Shapira, A Combinatorial Characteriza- tion of the Testable Graph Properties: It's All About Regularity, STOC (2006), pp. 251--260. [6] N. Alon and A. Shapira, A Characterization of Easily Testable Induced Sub- graphs, SODA (2004), pp. 942--951. [7] N. Alon and A. Shapira, Testing Subgraphs in Directed Graphs, STOC (2003), pp. 700--709. [8] F. S. Annexstein, M. Baumslag and A. L. Rosenberg, Group Action Graphs and Parallel Architectures, SIAM J. Comput., 19(3) (1990), pp. 544-569. [9] G. B. Arfken, Generators, Mathematical Methods for Physicists, 3rd ed. Orlando, Academic Press, 1985. [10] S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, Proof Verification and Hardness of Approximation Problems, FOCS (1992), pp 14--23. [11] L. Babai and P. Erd}os, Representation of Group Elements as Short Products, Annals of Discrete Mathematics, 12 (1982), pp. 27--30. [12] L. Babai, L. Fortnow, L. A. Levin and M. Szegedy, Checking Computations in Polylogarithmic Time, STOC (1991), pp. 21--31. [13] M. Bellare, D. Coppersmith, J. Hºastad, M. A. Kiwi, and M. Sudan, Linearity Testing in Characteristic Two, IEEE Transactions on Information Theory, 42(6) (1996), pp. 1781--1795. [14] M. Bellare, O. Goldreich and M. Sudan, Free Bits, PCPs and Non- Approximability - Towards Tight Results, FOCS (1995), pp. 422--431. [15] M. Bellare, S. Goldwasser, C. Lund, and A. Russell, E±cient Probabilistically Checkable Proofs and Applications to Approximations, STOC (1993), pp. 294-- 304. [16] M. Bellare and M. Sudan, Improved Non-approximability Results, STOC (1994), pp. 184--193. [17] M. A. Bender and D. Ron, Testing Properties of Directed Graphs: Acyclicity and Connectivity, Random Structures and Algorithms, 20 (2002), pp. 184--205. [18] M. Ben-Or, D. Coppersmith, M. Luby, and R. Rubinfeld, Non-abelian Ho- momorphism Testing, and Distributions Close to Their Self-convolutions, RANDOM-APPROX (2004), pp. 273--285. [19] E. Ben-Sasson, M. Sudan, S. P. Vadhan and A. Wigderson, Randomness-efficient Low Degree Tests and Short PCPs via Epsilon-Biased Sets, STOC (2003), pp. 612--621. [20] J. Bermond, T. Kodate and S. Perennes, Gossiping in Cayley Graphs by Pack- ets, Combinatorics and Computer Science, (1995), pp. 301--315 [21] S. N. Bhatt, F. R. K. Chung, J. W. Hong, F. T. Leighton and A. L. Rosen- berg, Optimal Simulations by Butter°y Networks (Preliminary Version), STOC (1988), pp. 192--204. [22] M. Blum, M. Luby, and R. Rubinfeld, Self-testing/correcting with Applications to Numerical Problems, J. Computer and System Sciences, 47(3) (1993), pp. 549--595. [23] B. Bollob¶as, Complete Subgraphs Are Elusive, J. Comb. Theory (Series B), 21 (1976), pp. 1--7. [24] M. R. Bridson and M. Tweedale, De‾ciency and abelianized de‾ciency of some virtually free groups, Math. Proc. Camb. Phil. Soc., Vol 143 (2007), pp. 257--264. [25] R. M. Bryant, L. Kovc¶as and G. R. Robinson, Transitive permutation groups and irreducible linear groups, Quart. J. Math. Oxford, 46(2) (1995), pp. 385--407. [26] P. J. Cameron, R. Solomon and A.Turull, Chains of subgroups in symmetric groups, J. Algebra, 127 (1989), pp. 340--352. [27] G. E. Carlsson, J. E. Cruthirds, H. B. Sexton and C. G.Wright, Interconnection Networks Based on a Generalization of Cube-Connected Cycles, IEEE Trans. Computers, 34(8) (1985), pp. 769--772. [28] K. Cheung and M. Mosca, Decomposing finite abelian groups, Quantum Infor- mation and Computation, 1(3) (2008), pp. 26--32. [29] C. E. Chronaki, A Survey of Evasiveness: Lower Bounds on the Decision-Tree Complexity of Boolean Functions, Available on http://www.ics.forth.gr/ chron- aki/papers/ur/eve.ps, (2002). [30] Y. Dodis, O. Goldreich, E. Lehman, S. Raskhodnikova, D. Ron and A. Samorod- nitsky, Improved Testing Algorithms for Monotonicity, RANDOM-APPROX (1999), pp. 97--108. [31] D. S. Dummit and R. M. Foote. Abstract Algebra, New Jersey, Prentice-Hall, Inc, 1991. [32] D. B. A. Epstein, Finite Presentations of Groups and 3-Manifolds, The Quar- terly Journal of Mathematics, 12(1) (1961), pp. 205--212. [33] F. Ergun, S. Kannan, R. Kumar, R. Rubinfeld and M. Viswanathan, Spot- Checkers, STOC (1998), pp. 259--268. [34] U. Feige and S. Kogan, The Hardness of Approximating Hereditary Properties, Available on http://research.microsoft.com/research/theory/feige/homepagefiles/ hereditary.pdf, (2005). [35] E. Fischer and L. Fortnow, Tolerant Versus Intolerant Testing for Boolean Prop- erties, Electronic Colloquium on Computational Complexity (ECCC), 11(105) (2004). [36] E. Fischer and I. Newman, Testing versus Estimation of Graph Properties, STOC (2005), pp. 138--146. [37] K. Friedl, G. Ivanyos and M. Santha, E±cient Testing of Groups, STOC (2005), pp. 157--166. [38] Z. Furedi, A. Naor and J. Verstraete, On the Turan Number for the Hexagon, Available on http://research.microsoft.com/research/ theory/naor/homepage%20files/final-hexagons.pdf, (2004). [39] R. Gold and J. Kim, Bases for Cyclotomic Units, Compositio Mathematica, 71(1) (1989), pp. 13--27. [40] O. Goldreich, S. Goldwasser, E. Lehman, D. Ron and A. Samorodnitsky, Testing Monotonicity, Combinatorica, 20(3) (2000), pp. 301--337. [41] O. Goldreich, S. Goldwasser and D. Ron, Property Testing and Its Connection to Learning and Approximation, J. ACM, 45(4) (1998), pp. 653--750. [42] O. Goldreich and D. Ron, A Sublinear Bipartiteness Tester for Bounded Degree Graphs, Combinatorica, 19(3) (1999), pp. 335--373. [43] J. Hºastad, Some Optimal Inapproximability Results, STOC (1997), pp. 1--10. [44] J. Hºastad, Testing of the Long Code and Hardness for Clique, STOC (1996), pp. 11--19. [45] J. Hºastad and A. Wigderson, Simple Analysis of Graph Tests for Linearity and PCP, Random Structures and Algorithms, 22(2) (2003), pp. 139--160. [46] D. A. Holton, and J. Sheehan. The Petersen Graph, Cambridge, England, Cam- bridge University Press, 1993. [47] R. C. Holt, E. M. Reingold, On the Time Required to Detect Cycles and Con- nectivity in Graphs, Mathematical Systems Theory, 6(2) (1972), pp. 103--106. [48] M. Jerrum, A compact presentation for permutation groups, J. Algorithms, 7 (1986), pp. 60--78. [49] G. Karpilovsky, The Schur multiplier. London Mathematical Society Mono- graphs, New Series 2. Oxford: Clarendon Press. XIV, 1987. [50] L. H. Kau®man, Virtual Knot Theory, Europ. J. Combinatorics, 20 (1999), pp. 663--691. [51] M. J. Kearns and D. Ron, Testing Problems with Sublearning Sample Complex- ity, J. Comput. Syst. Sci., 61(3) (2000), pp. 428--456. [52] S. G. Kim, Virtual Knot Groups, Mathematics Subject Classi‾cation, Primary 57M25, 1991. [53] D. G. Kirkpatrick, Determining Graph Properties from Matrix Representations, STOC (1974), pp. 84--90. [54] M. A. Kiwi, Probabilistically Checkable Proofs and the Testing of Hadamard-like Codes, Ph.D. dissertation. Massachusetts Institute of Technology, Cambridge, Mass, 1996. [55] L. Kov¶acs and M. F. Newman, Generating transitive permutation groups, Quart. J. Math. Oxford, 39(2) (1988), pp. 361--372. [56] T. KÄovari, V. T. Sos and P. Turan, On a Problem of K. Zarankiewicz, Collo- quium Math., 3 (1954), pp. 50--57. [57] R. Lipton, New Directions in Testing. Series in Discrete Mathematics and The- oretical Computer Science ACM/AMS, (2), 1991. [58] A. Lucchini, F. Menegazzo and M. Morigi, Asymptotic results for transitive permutation groups, Bull. London Math. Soc., 32 (2000), pp. 191--195. [59] F. Menegazzo, The Number of Generators of a Finite Group, Irish Math. Soc. Bulletin, 50 (2003), pp. 117--128. [60] D. R. Morrison, On K3 Surfaces with Large Picard Number, Inventiones Math- ematicae, 75(1) (1984), pp. 105--121. [61] B. H. Neumann, A two-generator group isomorphic to a proper factor group, J. London Math. Soc., s1-25(4) (1950), pp. 247--248. [62] M. Parnas, D. Ron and R. Rubinfeld, Tolerant Property Testing and Distance Approximation, Electronic Colloquium on Computational Complexity (ECCC), 11(10) (2004). [63] R. L. Rivest, J. Vuillemin, A Generalization and Proof of the Aanderaa- Rosenberg Conjecture, STOC (1975), pp. 6--11. [64] R. Rubinfeld and M. Sudan, Robust Characterizations of Polynomials with Ap- plications to Program Testing, SIAM J. Comput., 25(2) (1996), pp. 252--271. 43 [65] Y. Saad and M. H. Schultz, Topological Properties of Hypercubes, IEEE Trans- actions on computers, (1988), pp. 867--872. [66] A. Samorodnitsky and L. Trevisan, A PCP Characterisation of NP with Optimal Amortized Query Complexity, STOC (2000), pp. 191--199. [67] P. Shor, Polynomial-time algorithms for prime factorization and discrete loga- rithms on a quantum computer, SIAM J. Computing, 26(5) (1997), pp. 1484-- 1509. [68] L. Trevisan, Recycling Queries in PCPs and in Linearity Tests (Extended Ab- stract), STOC (1998), pp. 299--308. [69] H. F. Trotter, Homology of Group Systems With Applications to Knot Theory, The Annals of Mathematics, 2nd Ser., 76(3) (1962), pp. 464--498. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41325 | - |
| dc.description.abstract | 性質測試 (property testing)是一個在資訊學科中被廣泛研究的課題，其應用
範圍涵蓋了網路拓樸與程式除錯等多個領域。Bender 與Ron 發展了一個性質測 試的演算法，用來測試某些有向圖是否滿足強連通的性質，本論文將這個演算法 稱之為BR 演算法。BR 演算法在應用上有諸多限制，只適用於滿足特定條件的某 些有向圖。本論文發展了一個不受限制的演算法，可以測試任何一個有向圖是否 具有強連通的性質。 對於一個事先設定的有向圖H，Alon 與Shapira 證明了對於任一個有向圖G，如 果我們需要大量移除G 的有向邊，才可以完全消除G 裡面與H 共構(isomorphic) 的子圖(subgraph)，則在有向圖G 中的H 共構子圖的數目有一個下界。對於一個 有向子圖，如果其圖形的任一部分都不與H 形成共構，我們便稱之為無H 子圖。 本論文利用Alon 與Shapira 的研究結果，發展了一個演算法，用以測試任一個 有向圖是否存在一個由k 個點所組成的無H 子圖。 相對於在應用上受到限制的BR 演算法，本論文所發展用來測試強連通性質的演 算法，在應用上沒有限制但是效率會比較慢。因此對於滿足BR 演算法應用限制 的少數有向圖，我們還是傾向用BR 演算法來測試其是否有強連通的性質；至於 其他不滿足限制的有向圖，我們便使用本論文發展的演算法。當我們需要在兩者 之間做選擇的時候，前述測試無H 子圖的演算法可以幫助我們選擇合適的強連通 測試演算法。 一個群的生成元可以用來生成整個群，而對於一個阿貝爾群而言，其生成元的數 目是一個受到學界關注的研究題目。本論文利用前述的強連通測試演算法，發展 了一個很有效率的演算法，可以測試任一個集合與一個二元運算的組合是否為一 個生成元數目小於k 的阿貝爾群。 | zh_TW |
| dc.description.abstract | Bender and Ron construct a restricted tester on the strong connectivity of digraphs (we call it the BR tester). We generalize the BR tester to test the strong connectivity of digraphs.
For any digraph H and a digraph G being far from any H-free digraph, Alon and Shapira prove a lower bound of the number of H in G. After solving the problem of testing the strong connectivity of digraphs, we use Alon and Shapira's result to construct a randomized algorithm for testing digraphs with an H-free k-induced subgraph. Our strong connectivity tester has no restriction but must query about the input more times than the restricted BR tester. Suppose an input digraph satisfies the restrictions of the BR tester, using the BR tester to test the strong connectivity of this input digraph is more e±cient than using our strong connectivity tester. If we want to test the strong connectivity of a digraph, our randomized algorithm for testing digraphs with an H-free k-induced subgraph can help us determine which tester should be used to test the strong connectivity of the digraph: the BR tester or our strong connectivity tester. A generator set for a finite group is a subset of the group elements such that repeated multiplications of the generators alone can produce all the group elements. The number of generators of an abelian group is an important issue in many studies. In most cases, it is not easy to identify whether a group-like structure is an abelian group with k generators for a constant k. We construct an efficient randomized algorithm that, given a finite set with a binary operation, tests if it is an abelian group with a k-generator set. If k is not too large, the query complexity of our algorithm is polylogarithmic in the size of the groundset. Otherwise the query complexity is at most the square root of the size of the groundset. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T00:15:51Z (GMT). No. of bitstreams: 1 ntu-98-D91922010-1.pdf: 518122 bytes, checksum: ffb2777c799ea433eaa0cf7b38d1eb35 (MD5) Previous issue date: 2009 | en |
| dc.description.tableofcontents | 1 Introduction 1
2 Background 5 2.1 Question of property testing . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Property testing on combinatorial objects . . . . . . . . . . . . . . . . 6 2.3 Property testing and learning theory . . . . . . . . . . . . . . . . . . 6 3 Testing of Digraph Properties 8 3.1 Property testing on digraphs . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Research work related to graph property testing . . . . . . . . . . . . 9 3.3 Reduction between group properties and digraph properties . . . . . 10 4 Testing Strong Connectivity on Digraphs 12 4.1 Strongly connected component . . . . . . . . . . . . . . . . . . . . . . 12 4.2 Tester construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5 Testing Whether a Digraph Contains H-free k-induced Subgraphs 20 5.1 Existence of H-free k-induced subgraphs is ­(N2)-evasive . . . . . . . 20 5.2 Tester construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 6 Testing of Group Properties 35 6.1 Finite group-like structure . . . . . . . . . . . . . . . . . . . . . . . . 35 6.2 Research work related to group property testing . . . . . . . . . . . . 36 6.3 Tester construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 7 Conclusion 46 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 | |
| dc.language.iso | en | |
| dc.subject | 隨機演算法 | zh_TW |
| dc.subject | 有向圖 | zh_TW |
| dc.subject | 性質測試 | zh_TW |
| dc.subject | 強連通 | zh_TW |
| dc.subject | 阿貝爾群 | zh_TW |
| dc.subject | 生成元 | zh_TW |
| dc.subject | H-free subgraph | en |
| dc.subject | Generator | en |
| dc.subject | Abelian | en |
| dc.subject | Property testing | en |
| dc.subject | Strong connectivity | en |
| dc.title | 有向圖與阿貝爾群的性質測試 | zh_TW |
| dc.title | Property Testing on Directed Graphs and Abelian Groups | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 97-2 | |
| dc.description.degree | 博士 | |
| dc.contributor.oralexamcommittee | 趙坤茂,劉長遠,林軒田,吳明倫 | |
| dc.subject.keyword | 性質測試,隨機演算法,有向圖,強連通,阿貝爾群,生成元, | zh_TW |
| dc.subject.keyword | Property testing,Strong connectivity,H-free subgraph,Abelian,Generator, | en |
| dc.relation.page | 55 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2009-06-10 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-98-1.pdf 未授權公開取用 | 505.98 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。