布里斯托大學的學者將在計算機科學的兩個基本問題上提出新的突破。這些結果將在本周于世界領先的計算機科學國際會議上發(fā)表。

第56屆IEEE計算機科學基礎年度研討會將于10月18日至20日在加利福尼亞舉行。

計算機科學中最具挑戰(zhàn)性的問題之一是是否存在難以證明的問題。這在未解決的計算機科學問題(P = NP是否能解決問題的任何人將獲得100萬美元的獎勵)中最著名。

在第一篇文章，新動態(tài)和在線問題無條件的硬度結果，拉斐爾克利福德博士，讀者在算法設計在大學的計算機科學系，并從同事奧胡斯大學，已經(jīng)證明了硬度結果矩陣向量乘法，一個基本工具的版本在許多應用數(shù)學中 研究人員繼續(xù)顯示出有關數(shù)據(jù)動態(tài)變化的問題的進一步硬度結果。

研究小組研究了兩個基本問題的細胞探針復雜性：矩陣向量乘法和動態(tài)集不相交的一種形式，稱為Patrascu多相問題。研究人員針對這些問題提出了改進的無條件下界，并介紹了具有獨立利益的新證明技術。其中包括一項能夠證明以下形式的強閾值下限的技術：如果我們堅持要有非?？斓牟樵儠r間，則更新時間必須足夠慢才能計算出具有每個可能查詢答案的查找表。這是首次證明這種類型的下限。

研究人員的下限被證明等于有史以來的最高值，并給出了這樣一個數(shù)學證明的第二個例子，即使允許潛在的解決方案使用隨機數(shù)，該證明也成立。

在第二篇論文《在近乎線性的時間內(nèi)構建線性大小的頻譜稀疏度》中，大學計算機科學系計算機科學講師He He博士和麻省理工學院的博士生Yin Tat Lee提出了第一種構建算法在幾乎線性的時間內(nèi)運行的線性大小的頻譜稀疏器。

當今大數(shù)據(jù)場景中越來越多的應用程序需要處理數(shù)百萬個頂點的圖。盡管傳統(tǒng)算法可以直接應用在這些龐大的圖形中，但是當圖形包含數(shù)百萬個頂點時，這些算法通常太慢而無法實用。而且，存儲這些實用的大量圖形非常昂貴。

何孫博士說：“過去十年來，進行了深入研究以克服這兩個瓶頸。一種值得注意的方法是通過稱為頻譜稀疏化的中間步驟，這是通過繼承輸入圖的許多屬性的非常稀疏的圖來近似任何輸入圖。由于大多數(shù)算法在稀疏圖中的運行速度更快，因此頻譜稀疏化是加快許多實際圖形算法運行速度的關鍵中間步驟，包括在無向圖中找到近似最大流量，以及近似求解線性系統(tǒng)等。”

使用頻譜稀疏化，研究人員在稀疏圖中運行了許多算法，并且也獲得了大約正確的結果。這個通用框架使他們可以在一定程度上加快各種算法的運行速度。但是，要使整個方法切實可行，關鍵問題是找到更快的頻譜稀疏構造，并在所得稀疏器中減少邊緣。在過去的十年中，有很多研究針對這一領域。

研究人員證明，對于任何圖形，他們都可以在幾乎線性的時間內(nèi)構造其頻譜稀疏器，并且在輸出稀疏器中，每個頂點只有恒定數(shù)量的頂點。就算法的時間復雜度以及頻譜稀疏器中的邊緣數(shù)量而言，此結果幾乎是最佳的。

論文： Raphael Clifford，AllanGrønlund，Kasper Green Larsen在計算機科學基礎研討會(FOCS 2015)上提出的有關動態(tài)和在線問題的新無條件硬度結果。

論文： Yin Tat Lee和He Sun在計算機科學基礎研討會(FOCS 2015)上提出了在幾乎線性的時間內(nèi)構建線性大小的光譜稀疏性。他們的論文已被邀請參加SIAM Journal on Computing的特刊，該刊物專門介紹會議的最佳論文。