Autor:	Tsung-Han Chiang, 江宗翰
Druh dokumentu:	學位論文 ; thesis
Popis:	102 We consider the problem of how to nonadaptively recover the Cayley table of a group (G,．) with the minimum number of queries. Given a group (G,．), assume that we can access an oracle to ask for a．b for any a,b ∈G. The na#westeur048#ve way to recover the Cayley table of G is to ask the oracle for 〖\|G\|〗^2 times. Chang’s algorithm (Ching-Lueh Chang. Hardness of learning loops, monoids, and semirings. Discrete Applied Mathematics, 162: 149–158. 2014, Theorem 7) makes Ο(\|G\|log\|G\|) multiplication queries to recover the Cayley table of G. We adapt it into a nonadaptive Monte-Carlo algorithm, which makes Ο(\|G\|log\|G\|) multiplication queries to recover the Cayley table of G.
Databáze:	Networked Digital Library of Theses & Dissertations
Externí odkaz:	http://ndltd.ncl.edu.tw/handle/85778043172063187199 Zobrazit plný text záznamu