標題: 亂數粹取之計算複雜度研究
On the Complexity of Extracting Randomness from Sources with Computational Min-Entropy
作者: 蔡錫鈞
TSAI SHI-CHUN
國立交通大學資訊工程學系(所)
關鍵字: 計算複雜度;隨機計算;決定性萃取器;Cayley 圖;循環矩陣;computationalmin-entropy;獨立符號來源;computational complexity;randomized computing;deterministicextractor;seedless extractor;Cayley graph;circulant matrix;computationalmin-entropy;independent-symbol sources;XOR-Lemma
公開日期: 2009
摘要: 本計劃為期三年,主要目的為研究Cayley 圖,循環矩陣(circulant matrix),以及只 擁有computational min-entropy 的隨機源。我們觀察到Cayley 圖與獨立符號隨機源 萃取器所對應的圖在結構上非常相似,因此我們希望可以藉此找出一個新的證明 Cayley 圖收斂性的方法。跟著我們也將檢驗循環矩陣的特性。此外,我們將考慮只擁 有computational min-entropy 的隨機源。對一個分布X 與一個函數f,如果我們說 一個來源(f(X)|X)擁有computational min-entropy k,則代表對任何大小為2k 的電 路,最多只有2k 的機率可以猜對f。值得注意的是,當函數值f(x)完全由x 所決定時, 給定x 之後,f(x)並不具有任何隨機性。然而,依照定義只要f 是一個很難的函數, 則(f(X)|X)還是可以擁有很大的computational min-entropy。本計劃將從只擁有 computational min-entropy 的隨機源中萃取出隨機性。首先,我們將證明不能從單一 個隨機源中萃取。接著我們希望證明當有另一個獨立的且擁有某些隨機性的隨機源, 甚或是只擁有computational min-entropy 的隨機源時,我們即可成功地萃取出隨機 元。事實上,此種萃取器的造法可以看成是學習理論中的一個問題,亦即,在任意分 布以及對手雜訊的模型中,學習一個線性函數。最後,我們將造出只擁有computational min-entropy 的獨立符號來源的決定性萃取器,而這可視為是”XOR-Lemma”的一個延伸。
This project aims to study the Cayley graphs, circulant matrices, and sources containing computational min-entropy. We observe that the Cayley graphs have similar structure to the corresponding graphs of extractors for independent-symbol sources in [LLT06]. We want to use the method for extractors to give a new proof for the convergence of Cayley graphs. We will study the properties of circulant matrices. In addition, we want to consider the sources with computational min-entropy. For a distribution X and a function f, we say that a conditional source (f(X)|X) has computational min-entropy k, if any circuit with size 2k predicts f correctly with probability at most 2k . Note that if f is deterministic, that is, f(x) is determined by x, f(x) has no randomness when given x. However, as long as f is hard, it still can have high computational min-entropy. In this project, we want to extract randomness from sources containing computational min-entropy. First, we want to prove that it is impossible to have a seedless extractor to extract from one single source with computational min-entropy. Then we want to show that if we are allowed an additional independent source which contains some statistical min-entropy or even only contains computational min-entropy, we can extract some randomness which looks random to circuits of certain size. In fact, this task of constructing extractors can be reduced to a problem in learning theory. The problem is to learn a linear function under arbitrary distribution with adversarial noise, and we want to give a learning algorithm for it. Finally, we want to give a deterministic extractor for independent-symbol sources with computational min-entropy, and this job can be seen as a generalization of “XOR-Lemma”
官方說明文件#: NSC97-2221-E009-064-MY3
URI: http://hdl.handle.net/11536/101147
https://www.grb.gov.tw/search/planDetail?id=1754303&docId=299179
Appears in Collections:Research Plans


Files in This Item:

  1. 972221E009064MY3(第1年).PDF
  2. 972221E009064MY3(第2年).PDF
  3. 972221E009064MY3(第3年).PDF

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.