亂數粹取之計算複雜度研究
檔案
- 972221E009064MY3(第1年).PDF (1.59 MB, Adobe PDF)
- 972221E009064MY3(第2年).PDF (581.7 KB, Adobe PDF)
- 972221E009064MY3(第3年).PDF (2.32 MB, Adobe PDF)
日期
2009
摘要
本計劃為期三年,主要目的為研究Cayley 圖,循環矩陣(circulant matrix),以及只
擁有computational min-entropy 的隨機源。我們觀察到Cayley 圖與獨立符號隨機源
萃取器所對應的圖在結構上非常相似,因此我們希望可以藉此找出一個新的證明
Cayley 圖收斂性的方法。跟著我們也將檢驗循環矩陣的特性。此外,我們將考慮只擁
有computational min-entropy 的隨機源。對一個分布X 與一個函數f,如果我們說
一個來源(f(X)|X)擁有computational min-entropy k,則代表對任何大小為2k 的電
路,最多只有2k 的機率可以猜對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”的一個延伸。
擁有computational min-entropy 的隨機源。我們觀察到Cayley 圖與獨立符號隨機源
萃取器所對應的圖在結構上非常相似,因此我們希望可以藉此找出一個新的證明
Cayley 圖收斂性的方法。跟著我們也將檢驗循環矩陣的特性。此外,我們將考慮只擁
有computational min-entropy 的隨機源。對一個分布X 與一個函數f,如果我們說
一個來源(f(X)|X)擁有computational min-entropy k,則代表對任何大小為2k 的電
路,最多只有2k 的機率可以猜對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”的一個延伸。