布里斯托大學(xué)的學(xué)者將在計算機(jī)科學(xué)的兩個基本問題上提出新的突破。這些結(jié)果將在本周于世界領(lǐng)先的計算機(jī)科學(xué)國際會議上發(fā)表。
第56屆IEEE計算機(jī)科學(xué)基礎(chǔ)年度研討會將于10月18日至20日在加利福尼亞舉行。
計算機(jī)科學(xué)中最具挑戰(zhàn)性的問題之一是是否存在難以證明的問題。這在未解決的計算機(jī)科學(xué)問題(P = NP是否能解決問題的任何人將獲得100萬美元的獎勵)中最著名。
在第一篇文章,新動態(tài)和在線問題無條件的硬度結(jié)果,拉斐爾克利福德博士,讀者在算法設(shè)計在大學(xué)的計算機(jī)科學(xué)系,并從同事奧胡斯大學(xué),已經(jīng)證明了硬度結(jié)果矩陣向量乘法,一個基本工具的版本在許多應(yīng)用數(shù)學(xué)中 研究人員繼續(xù)顯示出有關(guān)數(shù)據(jù)動態(tài)變化的問題的進(jìn)一步硬度結(jié)果。
研究小組研究了兩個基本問題的細(xì)胞探針復(fù)雜性:矩陣向量乘法和動態(tài)集不相交的一種形式,稱為Patrascu多相問題。研究人員針對這些問題提出了改進(jìn)的無條件下界,并介紹了具有獨立利益的新證明技術(shù)。其中包括一項能夠證明以下形式的強(qiáng)閾值下限的技術(shù):如果我們堅持要有非??斓牟樵儠r間,則更新時間必須足夠慢才能計算出具有每個可能查詢答案的查找表。這是首次證明這種類型的下限。
研究人員的下限被證明等于有史以來的最高值,并給出了這樣一個數(shù)學(xué)證明的第二個例子,即使允許潛在的解決方案使用隨機(jī)數(shù),該證明也成立。
在第二篇論文《在近乎線性的時間內(nèi)構(gòu)建線性大小的頻譜稀疏度》中,大學(xué)計算機(jī)科學(xué)系計算機(jī)科學(xué)講師He He博士和麻省理工學(xué)院的博士生Yin Tat Lee提出了第一種構(gòu)建算法在幾乎線性的時間內(nèi)運(yùn)行的線性大小的頻譜稀疏器。
當(dāng)今大數(shù)據(jù)場景中越來越多的應(yīng)用程序需要處理數(shù)百萬個頂點的圖。盡管傳統(tǒng)算法可以直接應(yīng)用在這些龐大的圖形中,但是當(dāng)圖形包含數(shù)百萬個頂點時,這些算法通常太慢而無法實用。而且,存儲這些實用的大量圖形非常昂貴。
何孫博士說:“過去十年來,進(jìn)行了深入研究以克服這兩個瓶頸。一種值得注意的方法是通過稱為頻譜稀疏化的中間步驟,這是通過繼承輸入圖的許多屬性的非常稀疏的圖來近似任何輸入圖。由于大多數(shù)算法在稀疏圖中的運(yùn)行速度更快,因此頻譜稀疏化是加快許多實際圖形算法運(yùn)行速度的關(guān)鍵中間步驟,包括在無向圖中找到近似最大流量,以及近似求解線性系統(tǒng)等。”
使用頻譜稀疏化,研究人員在稀疏圖中運(yùn)行了許多算法,并且也獲得了大約正確的結(jié)果。這個通用框架使他們可以在一定程度上加快各種算法的運(yùn)行速度。但是,要使整個方法切實可行,關(guān)鍵問題是找到更快的頻譜稀疏構(gòu)造,并在所得稀疏器中減少邊緣。在過去的十年中,有很多研究針對這一領(lǐng)域。
研究人員證明,對于任何圖形,他們都可以在幾乎線性的時間內(nèi)構(gòu)造其頻譜稀疏器,并且在輸出稀疏器中,每個頂點只有恒定數(shù)量的頂點。就算法的時間復(fù)雜度以及頻譜稀疏器中的邊緣數(shù)量而言,此結(jié)果幾乎是最佳的。
論文: Raphael Clifford,AllanGrønlund,Kasper Green Larsen在計算機(jī)科學(xué)基礎(chǔ)研討會(FOCS 2015)上提出的有關(guān)動態(tài)和在線問題的新無條件硬度結(jié)果。
論文: Yin Tat Lee和He Sun在計算機(jī)科學(xué)基礎(chǔ)研討會(FOCS 2015)上提出了在幾乎線性的時間內(nèi)構(gòu)建線性大小的光譜稀疏性。他們的論文已被邀請參加SIAM Journal on Computing的特刊,該刊物專門介紹會議的最佳論文。