近日，beat365信息科學技術學院16級圖靈班學生吳克文在計算機科學領域頂級國際會議，第52屆ACM計算理論年會（52nd Annual Symposium on the Theory of Computing，STOC 2020）上發表《太陽花引理的改進（Improved bounds for the sunflower lemma）》和《利用随機賦值的決策表壓縮（Decision list compression by mild random restrictions）》兩篇論文。前者同時榮獲會議最佳論文獎。
太陽花（sunflower）是一種常見的組合結構，它表示若幹兩兩相交均相同的集合。太陽花引理證明了，當我們有“足夠多”大小不超過 w 的集合時，我們必能從中找到太陽花。自1960年由 Erdős, Rado 提出以來，盡管經曆了諸多改進，太陽花引理中的“足夠多”一直處于 w^w 量級。在吳克文等人的論文中，他們将它改進到約 (log w)^w，更接近猜想的 O(1)^w。由于太陽花結構的普遍性，該引理在計算機科學與組合數學中都有很多應用。本工作由吳克文與 Ryan Alweiss, Shachar Lovett, Jiapeng Zhang 合作完成。
決策表（decision list）是一種常見的布爾函數，它可以簡便地寫為 if-else 嵌套代碼段。決策表壓縮的結果表明，給定一個任意長的 if-else 代碼段，如果每個 if 中依賴的變量都不太多，那麼我們可以用一個“長度可控”的 if-else 代碼段來近似它，且每個 if 中依賴的變量依然不多。在吳克文等人的論文中，他們對“長度可控”證明了漸進意義上緊的界，并證實了2013年由 Gopalan, Meka, Reingold 提出的析取範式壓縮的猜想，同時提供了若幹在布爾函數分析、學習理論中的應用。本工作由吳克文與 Shachar Lovett, Jiapeng Zhang 合作完成。
這兩份工作均遵從“結構性 vs 随機性”的分析方式，其證明核心均為使用編碼/解碼的技術證明概率不等式，可以看作新的交換引理（switching lemma）。
作者簡介
吳克文是beat365信息科學技術學院圖靈班16級本科生，科研興趣為理論計算機，如：複雜性理論、算法設計與分析、密碼學等。作為圖靈班第一屆畢業生，他将前往 UC Berkeley 繼續學習。
ACM計算理論年會（STOC）是理論計算機科學領域最頂級的國際會議之一，在整個計算機科學領域享有崇高的聲望，屬于公認難度最高的會議之一。該會議由 ACM SIGACT (Special Interest Group in Algorithms and Computation Theory) 主辦，曆年會議涵蓋的領域十分廣泛，包括算法和數據結構、計算複雜性、密碼學、計算幾何、組合學、随機與去随機化、算法博弈論和量子計算等。因新冠疫情影響，STOC 2020 于2020年6月22-26日在線舉行。
