Browsing by Author "TSAI SHI-CHUN"

Now showing 1 - 20 of 28

NP 之外的計算複雜度研究
(2011)
蔡錫鈞
;
TSAI SHI-CHUN
;
國立交通大學資訊工程學系（所）
NP 之外的計算複雜度研究
(2009)
蔡錫鈞
;
TSAI SHI-CHUN
;
國立交通大學資訊工程學系(所)
NP 之外的計算複雜度研究
(2010)
蔡錫鈞
;
TSAI SHI-CHUN
;
國立交通大學資訊工程學系（所）
亂數粹取之計算複雜度研究
(2009)
蔡錫鈞
;
TSAI SHI-CHUN
;
國立交通大學資訊工程學系(所)
本計劃為期三年，主要目的為研究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”的一個延伸。
亂數粹取之計算複雜度研究
(2008)
蔡錫鈞
;
TSAI SHI-CHUN
;
國立交通大學資訊工程學系(所)
本計劃為期三年，主要目的為研究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”的一個延伸。
亂數粹取之計算複雜度研究
(2010)
蔡錫鈞
;
TSAI SHI-CHUN
;
國立交通大學資訊工程學系（所）
本計劃為期三年，主要目的為研究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”的一個延伸。
以多項式表示布林函數的最小次方下限問題
(2011)
蔡錫鈞
;
TSAI SHI-CHUN
;
國立交通大學資訊工程學系（所）
本計劃目標是針對布林函數(Boolean function)的多項式表示法，探討其次方 (degree)下界。用多項式來表示布林函數是少數已知可供證明電路複雜度(circuit complexity)的途徑之一，電路複雜度牽涉許多計算機科學基礎且未解的重要問題；新的多項式次方下界必可增加我們對於電路複雜度的了解。考慮一個n 個變數布林函數f:{0,1}n→{0,1}與對應的多項式P(x)，目前大多以下列三種模型來定義多項式表示法：(1)精確表示法P(x)=f(x)∀x.(2)單邊表示法P(x)=0 ⇔f(x)=0.(3)廣義表示法∀x,y s.t. f(x)≠f(y)⇒ P(x)≠P(y).目前對於後兩種模型的下界所知不多，且都是針對特定函數的結果；例如，And(x)和Modm(x)，但是對於OR(x) 在單邊和廣義兩種表示法的下界卻仍是公開的難題。近年有學者轉進考慮同時取兩種不同餘數時的多項式次方下界，亦即同時考慮Zp[x] 和Zq[x]中的多項式。考慮一個n 個變數布林函數f，令dp 和dq 分別代表在Zp[x] 和 Zq[x]中可以表示f 的最低次方，目前已知的最好結果是在精確表示法的模型中，任意的布林函數f 都須符合(log p)×dp×dq×p2dp≥n 的不等式。但是就具體的函數而言，這並非最佳的結果；此外也依然缺乏在單邊和廣義兩種模型下的結果。本計劃目標是改進此下界，並從精確表示法模型繼續推廣到單邊和廣義兩種模型。第一年目標：就「對稱型」布林函數，改進已知次方下界，並推廣到其他模型。第二年目標：就「非對稱型」布林函數，改進已知次方下界，並推廣到其他模型。
以多項式表示布林函數的最小次方下限問題
(2012)
蔡錫鈞
;
TSAI SHI-CHUN
;
國立交通大學資訊工程學系（所）
本計劃目標是針對布林函數(Boolean function)的多項式表示法，探討其次方 (degree)下界。用多項式來表示布林函數是少數已知可供證明電路複雜度(circuit complexity)的途徑之一，電路複雜度牽涉許多計算機科學基礎且未解的重要問題；新的多項式次方下界必可增加我們對於電路複雜度的了解。考慮一個n 個變數布林函數f:{0,1}n→{0,1}與對應的多項式P(x)，目前大多以下列三種模型來定義多項式表示法：(1)精確表示法P(x)=f(x)∀x.(2)單邊表示法P(x)=0 ⇔f(x)=0.(3)廣義表示法∀x,y s.t. f(x)≠f(y)⇒ P(x)≠P(y).目前對於後兩種模型的下界所知不多，且都是針對特定函數的結果；例如，And(x)和Modm(x)，但是對於OR(x) 在單邊和廣義兩種表示法的下界卻仍是公開的難題。近年有學者轉進考慮同時取兩種不同餘數時的多項式次方下界，亦即同時考慮Zp[x] 和Zq[x]中的多項式。考慮一個n 個變數布林函數f，令dp 和dq 分別代表在Zp[x] 和 Zq[x]中可以表示f 的最低次方，目前已知的最好結果是在精確表示法的模型中，任意的布林函數f 都須符合(log p)×dp×dq×p2dp≥n 的不等式。但是就具體的函數而言，這並非最佳的結果；此外也依然缺乏在單邊和廣義兩種模型下的結果。本計劃目標是改進此下界，並從精確表示法模型繼續推廣到單邊和廣義兩種模型。第一年目標：就「對稱型」布林函數，改進已知次方下界，並推廣到其他模型。第二年目標：就「非對稱型」布林函數，改進已知次方下界，並推廣到其他模型。
弱隨機源之亂度萃取及其應用(I)
(2005)
蔡錫鈞
;
TSAI SHI-CHUN
;
國立交通大學資訊工程學系(所)
本計劃為期三年，主要目的為建造. 雙弱隨機源的萃取器 (two-sources-extractors)，多弱隨機源的萃取器 (multi-sources-extractors)，以及實作可用於生物認證上的模糊萃取器 (fuzzy extractors for biometric authentication)。弱隨機源 (Weak random sources)所能保證的事只有不會有某一個特定字串出現的機率非常高。如果我們說一個弱隨機源的min-entropy 為b 則表示每個字串出現的機率都不會超過 2.b ，直觀地，我們認為這樣的弱隨機源」包含」 b 個隨機元。而萃取器(extractor)是一個函數，它可以從弱隨機源中，萃取出相當靠近均等分佈(uniform distribution)的隨機元。過去幾十年來，國內外的理論學家都致力於發展需要額外的真實隨機元才能萃取弱隨機源中隨機性 (randomness)的種子萃取器 (seeded extractors)。經過多年的努力後，種子萃取器的發展已幾進完美，且在資訊科學的許多領域有重要的應用。可是由於真實的隨機元在自然界中並不存在，因此，學者們慢慢的把目標放在如何從兩個或多個弱隨機源中萃取出隨機性以及考慮限制更強的固定某些位元的決定性萃取器 (deterministic extractors for bit-fixing sources)。本計劃將改進先前固定某些位元萃取器當來源隨機性太低時，所輸出的隨機元與均等分佈誤差過大的缺點，且經由固定某些位元萃取器的建造方式來改進多個弱隨機源萃取器只萃取出元來源隨機性極少部分的缺點。最後，我們將改進模糊萃取器利用編碼理論(coding theory)來增加其錯誤更正能力卻反而容易洩露資訊的危機，並實作一個應用於生物認證方面的模糊萃取器。
弱隨機源之亂度萃取及其應用(II)
(2006)
蔡錫鈞
;
TSAI SHI-CHUN
;
國立交通大學資訊工程學系(所)
弱隨機源之亂度萃取及其應用(III)
(2007)
蔡錫鈞
;
TSAI SHI-CHUN
;
國立交通大學資訊工程學系(所)
快速最大流量問題探討
(2015)
蔡錫鈞
;
TSAI SHI-CHUN
;
國立交通大學資訊工程學系（所）
校園資訊服務節能計畫( I )
(2015)
蔡錫鈞
;
TSAI SHI-CHUN
;
國立交通大學資訊工程學系（所）
校園資訊服務節能計畫(II)
(2016)
蔡錫鈞
;
TSAI SHI-CHUN
;
國立交通大學資訊工程學系（所）
解隨機化之研究(I)
(2003)
蔡錫鈞
;
TSAI SHI-CHUN
;
國立交通大學資訊工程學系
解隨機化之研究(II)
(2004)
蔡錫鈞
;
TSAI SHI-CHUN
;
國立交通大學資訊工程學系
解隨機化之研究(III)
(2005)
蔡錫鈞
;
TSAI SHI-CHUN
;
國立交通大學資訊工程學系(所)
逼近演算法之設計與分析
(2014)
蔡錫鈞
;
TSAI SHI-CHUN
;
國立交通大學資訊工程學系（所）
演算法自計算機科學發展以來一直是核心研究中的一部分，而其中最佳化問題算法的演進也都是重要的議題。本計晝的三個主題在：一、為特定的算法問題設計有效率的逼近算法或進行average case complexity的分析：在P关NP幾近成立的前提下，許多屬於NP-Hard但重要而常用來建模的算法問題要有效率的完美求解已是希望渺茫。進而解決此類問題的方向便是進行逼近算法的研究或者分析在average case下，問題是否會變得容易許多。面對有多項式時間算法但仍希望增進時間效率的情況，也可以嘗試放寬求解的質量進而設計高效算法。二、分析問題的不可逼近性：面對逼近算法也難以設計的情況下，必須從另一方面探討問題可逼近的極限，是否連逼近本身也是真正困難的。三、問題的計算複雜度歸類：許多問題雖然可能已知是NP-Hard，但詳細應被歸類在哪還未有結果，在對於算法問題的算法設計與結構上的仔細分析後會對問題的本質有更多的了解，有助於我們將尚未歸類的難題作分類。進一步了解問題的困難度。
逼近演算法之設計與分析
(2012)
蔡錫鈞
;
TSAI SHI-CHUN
;
國立交通大學資訊工程學系（所）
演算法自計算機科學發展以來一直是核心研究中的一部分，而其中最佳化問題算法的演進也都是重要的議題。本計晝的三個主題在：一、為特定的算法問題設計有效率的逼近算法或進行average case complexity的分析：在P关NP幾近成立的前提下，許多屬於NP-Hard但重要而常用來建模的算法問題要有效率的完美求解已是希望渺茫。進而解決此類問題的方向便是進行逼近算法的研究或者分析在average case下，問題是否會變得容易許多。面對有多項式時間算法但仍希望增進時間效率的情況，也可以嘗試放寬求解的質量進而設計高效算法。二、分析問題的不可逼近性：面對逼近算法也難以設計的情況下，必須從另一方面探討問題可逼近的極限，是否連逼近本身也是真正困難的。三、問題的計算複雜度歸類：許多問題雖然可能已知是NP-Hard，但詳細應被歸類在哪還未有結果，在對於算法問題的算法設計與結構上的仔細分析後會對問題的本質有更多的了解，有助於我們將尚未歸類的難題作分類。進一步了解問題的困難度。
逼近演算法之設計與分析
(2013)
蔡錫鈞
;
TSAI SHI-CHUN
;
國立交通大學資訊工程學系（所）
演算法自計算機科學發展以來一直是核心研究中的一部分，而其中最佳化問題算法的演進也都是重要的議題。本計晝的三個主題在：一、為特定的算法問題設計有效率的逼近算法或進行average case complexity的分析：在P关NP幾近成立的前提下，許多屬於NP-Hard但重要而常用來建模的算法問題要有效率的完美求解已是希望渺茫。進而解決此類問題的方向便是進行逼近算法的研究或者分析在average case下，問題是否會變得容易許多。面對有多項式時間算法但仍希望增進時間效率的情況，也可以嘗試放寬求解的質量進而設計高效算法。二、分析問題的不可逼近性：面對逼近算法也難以設計的情況下，必須從另一方面探討問題可逼近的極限，是否連逼近本身也是真正困難的。三、問題的計算複雜度歸類：許多問題雖然可能已知是NP-Hard，但詳細應被歸類在哪還未有結果，在對於算法問題的算法設計與結構上的仔細分析後會對問題的本質有更多的了解，有助於我們將尚未歸類的難題作分類。進一步了解問題的困難度。