顯示廣告
隱藏 ✕
※ 本文為 MindOcean 轉寄自 ptt.cc 更新時間: 2021-03-02 17:43:38
看板 Gossiping
作者 jackliao1990 (j)
標題 [爆卦] 25年未解的KLS猜想被統計博士解決了
時間 Tue Mar  2 17:01:37 2021


https://arxiv.org/pdf/2011.13661.pdf
1984年菲爾茲獎得主Jean Bourgain提出了一個猜想:任意維度的凸體用低一維的平面去
平分,那麼存在一個常數c,使凸體至少存在一個切面的面積大於c。
這個猜想在三維時很好想像(例如切西瓜),但到了高維時複雜度就大大提高。Bourgain
到了去世前還在問他朋友-數學分析大師Vitali Milman:猜想是否有進展,想在死前知道
答案。

後來Kannan、Lová  sz和Simonovits從Jean Bourgain的猜想延伸,於1995年提出了KLS猜
想:用來平分任意維度凸體的最小曲面面積是多少?高維度空間中,平分最佳平面和最佳
曲面的差距會變大嗎?切面的面積是否和維度d有關?
這個猜想是計算機科學和統計學中許多問題的核心-例如:熱通過凸形擴散需要多長時間
?隨機步行者走幾步才能到達真正隨機的位置?其結果直接關係到隨機行走算法的運行時
間,如機器學習模型的採樣問題。


2012年Eldan透過引入隨機定位技術來降低這個問題與空間維度上界,他將上界降到空間
維度d的三次方根:d^(1/3)。三年後華盛頓大學的李賢達和Vempala改進了Eldan的方法並
用統計學的自助抽樣法將上界降到空間維度的零次方:d^0。但是論文PO上網的幾天後就
被發現漏洞,於是他們修改了論文,將上界改成空間維度的四次方根:d^(1/4)。


李賢達和Vempala的d^0證明只有一處有問題,這引起了時為CAL統計學研究生陳遠思的興
趣,他當時在研究隨機抽樣方法的混合速率。數年的思考讓他意識到:重點不是補充李賢
達和Vempala證明中缺少的陳述,而是解決這種陳述的必要性。他採用遞歸法來降低KLS
邊界,這種自助抽樣法為KLS猜想和Bourgain問題實現了近似恆定常數的邊界。

陳遠思的結果顯示高維凸形物體不會有啞鈴那樣的結構,在任何維度凸體中隨機行走並完成遍歷的速度比預期還快。這將有助於計算機科學家對不同的隨機採樣算法進行優先排序。

陳遠思的論文發表後立刻引起關注並通過檢驗,哈佛資工教授、微軟研究院前新英格蘭
首席研究員Boaz Barak發推評價:"這是一個非常重要的突破,加快了對近似凸體體積的
研究。"

陳遠思目前在蘇黎世聯邦理工學院做博士後研究,同時在杜克大學統計科系擔任助理教
授。


--
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.103.202 (臺灣)
※ 文章代碼(AID): #1WFVxqkG (Gossiping)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1614675700.A.B90.html
benomy: 嗯嗯和我想的一樣1F 03/02 17:02
sk050607: 已知用火2F 03/02 17:02
WeasoN: 這問題有夠trivial的 連我大學的工友都會解3F 03/02 17:03
wbt77hsy: 看不懂Q4F 03/02 17:03
ben840619: 跟我想的差不多5F 03/02 17:03
StylishTrade: 阿不是說華人都只會填鴨 都很笨嗎6F 03/02 17:03
MEVIUS: 跟我的大學專題一樣7F 03/02 17:03
ProfessUX: 我都在提升機機的維度8F 03/02 17:04
cuteSquirrel: 恩恩,和樓下數學專家想得一樣。9F 03/02 17:04
pshuang: 工三小10F 03/02 17:04
ePaper: 我承認完全看不懂 pass11F 03/02 17:05
funkD: 嗯嗯 我也是這麼想的12F 03/02 17:06
Ericz7000: 恩恩 跟我想的差不多 不過這部分建議再寫的淺白一點13F 03/02 17:06
Ericz7000: 不然很多人看不懂
Iruvata: 看不懂= =15F 03/02 17:08
VdustR: 這個愛莉莎莎早就解出來了16F 03/02 17:09
bill403777: 連題目都看不懂17F 03/02 17:09
rioforreal: 我也是這麼想18F 03/02 17:09
ppptttqaz: 我只會看天竺鼠車車了QQ19F 03/02 17:10
EvilPrada: 干  連題目都看不懂  數學家真閒20F 03/02 17:10
dhccc: 陳遠思是哪裡人?21F 03/02 17:10
th11yh23 
th11yh23: 我認為應該不是這樣吧 下次再跟作者討論看看22F 03/02 17:11
j55888819: 我昨天也這樣和我朋友說 很高興也有人的想法和我一樣23F 03/02 17:12
EvilPrada: 這個可以用數學歸納法證明嗎?24F 03/02 17:13
industrialld: 嗯,證出來後上ptt會比較快嗎25F 03/02 17:13
BaRanKa: 排版啊..26F 03/02 17:13
rainingkid: 第四段要修正一下吧= =我會再跟他討論一下27F 03/02 17:14
icosahedron: 這麼厲害,怎麼不當youtuber28F 03/02 17:14
lolic: 切西瓜我懂啊我夏天也會切 有什麼難的29F 03/02 17:16
louiswei1986: 我昨天也是這樣覺得的30F 03/02 17:19
s81048112: 原來如此!31F 03/02 17:23
joker7788996: 嗯嗯跟我想到的一樣32F 03/02 17:23
※ 編輯: jackliao1990 (42.72.103.202 臺灣), 03/02/2021 17:23:59
doro0202: 為什麼你都po這種只做出一點突破標題就寫得好像把事情33F 03/02 17:25
doro0202: 都解決的東西啊?
※ 編輯: jackliao1990 (42.72.103.202 臺灣), 03/02/2021 17:27:17
asidy: 工三小,我好弱,嗚嗚嗚35F 03/02 17:28
polarbear: 原來如此!36F 03/02 17:32
LukeSkywaker: 嗯嗯跟我想的差不多37F 03/02 17:35

--
※ 看板: Gossiping 文章推薦值: 0 目前人氣: 0 累積人氣: 291 
作者 jackliao1990 的最新發文:
點此顯示更多發文記錄
分享網址: 複製 已複製
1樓 時間: 2021-03-02 19:47:08 (台灣)
  03-02 19:47 TW
兩個底圓半徑相同的圓錐體接在一起 也是凸體
兩個截面半徑相同的球蓋體接在一起 也是凸體
2樓 時間: 2021-03-02 20:12:12 (台灣)
  03-02 20:12 TW
五十多年前,我的同學撞球時就想過,沒有結論。
r)回覆 e)編輯 d)刪除 M)收藏 ^x)轉錄 同主題: =)首篇 [)上篇 ])下篇