看板 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
推 WeasoN: 這問題有夠trivial的 連我大學的工友都會解3F 03/02 17:03
→ MEVIUS: 跟我的大學專題一樣7F 03/02 17:03
推 ePaper: 我承認完全看不懂 pass11F 03/02 17:05
推 funkD: 嗯嗯 我也是這麼想的12F 03/02 17:06
推 Ericz7000: 恩恩 跟我想的差不多 不過這部分建議再寫的淺白一點
不然很多人看不懂13F 03/02 17:06
噓 VdustR: 這個愛莉莎莎早就解出來了16F 03/02 17:09
推 dhccc: 陳遠思是哪裡人?21F 03/02 17:10
推 th11yh23: 我認為應該不是這樣吧 下次再跟作者討論看看22F 03/02 17:11
推 j55888819: 我昨天也這樣和我朋友說 很高興也有人的想法和我一樣23F 03/02 17:12
→ rainingkid: 第四段要修正一下吧= =我會再跟他討論一下27F 03/02 17:14
推 lolic: 切西瓜我懂啊我夏天也會切 有什麼難的29F 03/02 17:16
※ 編輯: jackliao1990 (42.72.103.202 臺灣), 03/02/2021 17:23:59
噓 doro0202: 為什麼你都po這種只做出一點突破標題就寫得好像把事情都解決的東西啊？33F 03/02 17:25
※ 編輯: jackliao1990 (42.72.103.202 臺灣), 03/02/2021 17:27:17
推 asidy: 工三小，我好弱，嗚嗚嗚35F 03/02 17:28
--