亂數粹取之計算複雜度研究

Abstract

本計劃為期三年，主要目的為研究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”