※ 本文為 MindOcean 轉寄自 ptt.cc 更新時間: 2021-03-02 17:43:38
看板 Gossiping
作者 標題 [爆卦] 25年未解的KLS猜想被統計博士解決了
時間 Tue Mar 2 17:01:37 2021
https://arxiv.org/pdf/2011.13661.pdf
1984年菲爾茲獎得主Jean Bourgain提出了一個猜想:任意維度的凸體用低一維的平面去
平分，那麼存在一個常數c，使凸體至少存在一個切面的面積大於c。
這個猜想在三維時很好想像(例如切西瓜)，但到了高維時複雜度就大大提高。Bourgain
到了去世前還在問他朋友-數學分析大師Vitali Milman:猜想是否有進展，想在死前知道
答案。
到了去世前還在問他朋友-數學分析大師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)。
維度d的三次方根:d^(1/3)。三年後華盛頓大學的李賢達和Vempala改進了Eldan的方法並
用統計學的自助抽樣法將上界降到空間維度的零次方:d^0。但是論文PO上網的幾天後就
被發現漏洞，於是他們修改了論文，將上界改成空間維度的四次方根:d^(1/4)。
李賢達和Vempala的d^0證明只有一處有問題，這引起了時為CAL統計學研究生陳遠思的興
趣，他當時在研究隨機抽樣方法的混合速率。數年的思考讓他意識到:重點不是補充李賢
達和Vempala證明中缺少的陳述，而是解決這種陳述的必要性。他採用遞歸法來降低KLS
邊界，這種自助抽樣法為KLS猜想和Bourgain問題實現了近似恆定常數的邊界。
趣，他當時在研究隨機抽樣方法的混合速率。數年的思考讓他意識到:重點不是補充李賢
達和Vempala證明中缺少的陳述，而是解決這種陳述的必要性。他採用遞歸法來降低KLS
邊界，這種自助抽樣法為KLS猜想和Bourgain問題實現了近似恆定常數的邊界。
陳遠思的結果顯示高維凸形物體不會有啞鈴那樣的結構，在任何維度凸體中隨機行走並完成遍歷的速度比預期還快。這將有助於計算機科學家對不同的隨機採樣算法進行優先排序。
陳遠思的論文發表後立刻引起關注並通過檢驗，哈佛資工教授、微軟研究院前新英格蘭
首席研究員Boaz Barak發推評價:"這是一個非常重要的突破，加快了對近似凸體體積的
研究。"
首席研究員Boaz Barak發推評價:"這是一個非常重要的突破，加快了對近似凸體體積的
研究。"
陳遠思目前在蘇黎世聯邦理工學院做博士後研究，同時在杜克大學統計科系擔任助理教
授。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.103.202 (臺灣)
※ 文章代碼(AID): #1WFVxqkG (Gossiping)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1614675700.A.B90.html
→ : 嗯嗯和我想的一樣1F 03/02 17:02
→ : 已知用火2F 03/02 17:02
推 : 這問題有夠trivial的 連我大學的工友都會解3F 03/02 17:03
推 : 看不懂Q4F 03/02 17:03
推 : 跟我想的差不多5F 03/02 17:03
推 : 阿不是說華人都只會填鴨 都很笨嗎6F 03/02 17:03
→ : 跟我的大學專題一樣7F 03/02 17:03
推 : 我都在提升機機的維度8F 03/02 17:04
→ : 恩恩，和樓下數學專家想得一樣。9F 03/02 17:04
推 : 工三小10F 03/02 17:04
推 : 我承認完全看不懂 pass11F 03/02 17:05
推 : 嗯嗯 我也是這麼想的12F 03/02 17:06
推 : 恩恩 跟我想的差不多 不過這部分建議再寫的淺白一點13F 03/02 17:06
→ : 不然很多人看不懂
→ : 不然很多人看不懂
推 : 看不懂= =15F 03/02 17:08
噓 : 這個愛莉莎莎早就解出來了16F 03/02 17:09
→ : 連題目都看不懂17F 03/02 17:09
推 : 我也是這麼想18F 03/02 17:09
推 : 我只會看天竺鼠車車了QQ19F 03/02 17:10
→ : 干 連題目都看不懂 數學家真閒20F 03/02 17:10
推 : 陳遠思是哪裡人?21F 03/02 17:10
→ th11yh23 …
推 : 我昨天也這樣和我朋友說 很高興也有人的想法和我一樣23F 03/02 17:12
推 : 這個可以用數學歸納法證明嗎?24F 03/02 17:13
推 : 嗯，證出來後上ptt會比較快嗎25F 03/02 17:13
→ : 排版啊..26F 03/02 17:13
→ : 第四段要修正一下吧= =我會再跟他討論一下27F 03/02 17:14
推 : 這麼厲害，怎麼不當youtuber28F 03/02 17:14
推 : 切西瓜我懂啊我夏天也會切 有什麼難的29F 03/02 17:16
→ : 我昨天也是這樣覺得的30F 03/02 17:19
推 : 原來如此!31F 03/02 17:23
→ : 嗯嗯跟我想到的一樣32F 03/02 17:23
※ 編輯: jackliao1990 (42.72.103.202 臺灣), 03/02/2021 17:23:59噓 : 為什麼你都po這種只做出一點突破標題就寫得好像把事情33F 03/02 17:25
→ : 都解決的東西啊？
※ 編輯: jackliao1990 (42.72.103.202 臺灣), 03/02/2021 17:27:17→ : 都解決的東西啊？
推 : 工三小，我好弱，嗚嗚嗚35F 03/02 17:28
推 : 原來如此！36F 03/02 17:32
推 : 嗯嗯跟我想的差不多37F 03/02 17:35
--
※ 看板: Gossiping 文章推薦值: 0 目前人氣: 0 累積人氣: 295
回列表(←)
分享