Page 38 - profile-ok

研究群 ｜ Research Laboratories

計算理論與演算法實驗室 Computation Theory and Algorithms Laboratory

研究人員 研究群介紹

高明達 Ming-Tat Ko 1. 圖論與圖論演算法 最佳化 (Multi-criteria optimization) 問題。此一研究議題中所考慮 6. 密碼學
Research Fellow 的大部分問題，在計算複雜度理論上都已被證明是難題 (Compu-
Computer Science , National Tsing-Hua University 圖論可以解決許多實際應用問題，而且也是很多理論研究的工具。我們通常先由基礎圖 tationally intractable)，因此我們將探討這些問題的深層架構，嘗 在代數攻擊上，XL 演算法為一種解方程式的技巧，幫助終結了
王大為 Da-Wei Wang 論性質的研究著手，然後藉由新性質的發現，設計高效率演算法，再進一步探討理論之 試發掘各種特性，進而設計近似最佳的演算法或啟發式演算法。 線性回饋平移暫存器 (Linear Feedback Shift Register) 作為加密技
Research Fellow 突破，以及可能的應用價值。我們探討於實際應用產生的圖論演算法問題。在生物演化 術的時代，我們對它首度作了完整的分析，並推廣到一些其他的
Computer Science , Yale University 分析應用上，我們探討兩個基本問題，史坦納樹根問題與超級樹的建構問題。將物種視 應用。另外我們也研究後量子密碼學，特別是多變量的公鑰密碼
為節點，足夠相似的兩物種以邊相連構成物種間的相似圖，史坦納樹根問題是要尋找一 系統 (MPKC) : 這是一種以處理多個小有限體中的變數，來取代大
呂及人 Chi-Jen Lu 4. 巨量資料計算
Research Fellow 含這些物種節點的樹狀圖，其k次方恰為其相似圖。此樹狀圖為符合這些物種相似圖的演 代數結構中的元素的想法，被認為是在量子電腦發明之後可能存
Computer Science , University of Massachusetts at 化樹。透過各種不同的方式，生物學家得到許多不同物種集合的演化樹。綜合這些演化 巨量資料之邏輯與知識表達：巨量資料之中隱藏許多有用的資訊 續的公鑰密碼系統 (Post-Quantum Public-Key Cryptosystem) 的一
Amherst 樹顯示的演化關係，建構大物種集合的演化樹即是超級樹的建構。雖然已有許多超級樹 與知識，因此，近年來具有學習與推理能力的智慧型代理人系統 個重要分類，該類系統一般也有高效能的名聲，適合用在小或嵌
李德財 Der-Tsai Lee 的建構方法，但是有效率且提供物種間完整演化關係的演算法仍然是生物學家的期待。 受到很大的重視。我們將以邏輯方法來探討智慧型代理人系統相 入式系統上。我們在這一方面的研究在世界上目前居於領先群
Distinguished Research Fellow 另外我們也探討自巨量資料之應用所產生的基本的演算法問題。例如有分割限制的圖形 關的知識表達與推理問題。一方面我們探討歸納產生有用的推理 中。另一方面，某些密碼演算法特別需要最高的效率。破密攻擊
Computer Science , University of Illinois at Urbana- 性質增強演算法，此問題源自隱私保護問題，可以應用於多種容錯設計上。另一是樹狀 規則與知識的方法，尤其是粹取出的知識的表達問題。另一方面 固然如此，加密的演算法有時也如此：或許是因為資源有限，例
Champaign
圖間編輯距離的計算演算法，可應用於生物資訊中需要巨大樹狀圖的比較的問題。 將嘗試建立適當的知識表達架構，使衍生的知識作為進一步推理 如 RSA 就太耗資源，不適合全在計算例如射頻電路身份辨識元件
徐讚昇 Tsan-sheng Hsu 與決策的基礎，代理人系統之間也可以交換知識，透過匯集不同 (Radio Frequency Identification Device, RFID) 的要求，並因此可能
Research Fellow 來源的知識產生更複雜的知識。這樣分散但是有組織的知識粹取 在最近被北約組織整個用 ECC (橢圓曲線) 系統取代。又或許效率
Computer Sciences , University of Texas at Austin
2. 幾何計算 與處理機制可以自巨量資料中衍生有用的知識作為決策之用以有 較低的演算法仍可以使用，但是高效能意味著同樣的硬體與速度
楊柏因 Bo-Yin Yang 效的減輕決策者面對資訊爆量的問題。 下更高的安全性，又或是可以使用更便宜的元件。我們特別注重
Associate Research Fellow Voronoi圖形有非常廣泛的用途，是幾何計算領域學者長期研究的重要幾何結構。此結構 在特殊硬體包括微控制器晶片 (microcontroller, 即智慧卡的主要組
Mathematics (Applied) , Massachusetts Institute of 所具有的性質及複雜度，還有如何計算而得等等都是幾何計算演算法的基本問題。當引 巨量資料的隱私加強技術之演算法與協定：近年來許多機構因不 件)，可即時重新程式化的電路陣列 (Field Programmable Gate Ar-
Technology 進不同的「距離」概念時，例如「時間距離」，Voronoi 圖形也會跟著變化。而其特性 同的目的收集大量且完備之個人資訊。分享這些資訊將可有益於 ray, FPGA) 上面的密碼學演算法。本實驗室最近為人稱道的研究是
廖純中 Churn-Jung Liau 與所選定的「距離」如何互動改變，如何利用「距離」的某些性質，設計更有效率的演 社會，但同時也對個人隱私產生極大的威脅。如何既能達到資料 利用計算機的顯示晶片來做橢圓曲線的計算，在破密上獲得破紀
Research Fellow 算法是我們所欲探討的問題。另外如何標示地圖中的地標，使得標示不會相互重疊的問 分享之目的又同時兼顧個人隱私，為我們研究之目標。我們提出 錄的速度。我們也做出低電流低耗能可以在 RFID 上執行的數位簽
CSIE , National Taiwan University 題；如何選定設施的地點，讓未來的競爭者所能贏取的顧客數目降到最低的問題等，也 一個邏輯的架構來探討公開 micro-data 的隱私風險，且同時提出 章演算法。最近也進行使用智慧型手機或其他類似的裝置來協助
劉進興 Jing-Sin Liu 是我們研究的方向。在生物計算領域裡有關基因序列的子序列問題上，例如找出最佳密 了一個量化的風險量測值。我們目前在研究資料庫連結這個更具 進行認證的資訊交換，或其他實用上的資訊安全研究。
Associate Research Fellow 度子序列，最佳總和子序列等，我們則試圖利用幾何計算領域的一些重要技巧，例如隨 挑戰性的問題，亦即如何得到資料庫連結後可計算出的結果又同
EE , National Taiwan University 機抽樣、參數搜尋、幾何切割、拓展圖和矩陣搜尋等來減少計算的複雜度。希望藉助幾 時保障個人隱私。我們打算利用多方私密計算技術，利用私密的
何計算的技術能幫忙解決更多生物計算領域的難題，並更進一步地應用於模型辨識、影 內積協定作為基礎，建構基礎函式，再以這些基礎函式來建構各
像處理、資料探勘等議題。 類型的應用系統。最終的目標為發展一套完展的系統，使用者可
用高階語言來寫程式，而自動的編譯器可將程式碼翻譯成可執行
的多方私密協定碼。
3. 網路設計與分析
網路設計問題探討的是如何將許多不同位置的站點，經由適當的網路架構連結以滿足特 5. 複雜度理論
定的需求。這類問題涵括了許多不同領域內的核心議題，例如超大型積體電路 (VLSI) 設
計、無線傳感器網路 (Wireless sensor network)、生物資訊學 (Bioinformatics) 及通訊網路 亂數在計算上，已成為一個有用的資源。對於許多計算問題，隨
(Communication network) 等。在不同的應用領域，這些問題透過各式各樣的效能評估 機演算法提供了最自然、最簡單、或最有效率的解決方法。然而
方式及限制條件，以不同的形式出現，而其間又存在著微妙的共通性。在這個研究議題 一般隨機演算法的設計，均假設有完美的亂數供其使用。但是電
上，我們將從演算法設計的角度，研究在單一或多重評量標的下的網路建構問題。我們 腦如何能產生完美的亂數？就連自然界是否存在完美的亂數源，
從許多網路品質的評量標的中，挑出最主要的幾項標的加以討論，包括網路的權重(所 也是一個值得爭議的問題。解決此困境的第一種方法，乃是研究
有邊的總和長度)、直徑(任兩點間的最長網路傳輸距離)、膨脹係數(任兩點間網路距離 如何將隨機式演算法轉化成確定式演算法，而不至於大為降低其
對最短直線距離之最大比值)、傳輸成本(任兩點間網路距離的總和)、瓶頸頻寬或流量等 效率。我們研究如何在合理的假設下達成這個目的，我們也研究
等。我們也將考慮當網路中的節點或連結發生短暫損壞時，如何維持網路的容錯性以及 這種去除隨機性工作的可能極限。我們將針對使用對數空間或常
網路動態更新的能力。除了網路設計的問題以外，我們也研究在既有網路上的多重目標 數平行時間的隨機式演算法，研究如何在不需任何假設下，有系
統的去除他們使用的亂數，來得到確定式的演算法。解決困境的
第二種方法，乃是設計所謂的亂度淬取程序，來由稍具亂度的弱
亂數源中，淬取近乎完美的亂數，以供隨機演算法使用。我們建
構出目前已知最有效率的亂度淬取程序，我們也將亂度淬取程序
應用於密碼學，而建構出具有永久安全性的加密系統。我們將推
廣這方面的成果，研究如何由不具統計亂度而只稍具計算亂度的
分佈中，淬取出可供隨機演算法使用的亂數。

38 39