2025年ゲーデル賞、明示的2元抽出器に関する画期的論文に授与

2025年ゲーデル賞は、Eshan ChattopadhyayとDavid Zuckermanの画期的な論文「明示的2元抽出器とレジリエント関数」に対して授与されました。この論文はSTOC 2016とAnnals of Math 2019に掲載され、ラムゼーグラフの構成を大幅に改善し、従来の方法をはるかに超える指数関数的な限界を達成しました。この成果は、脱ランダム化への影響と、ラムゼー理論への驚くべき応用から高く評価されており、擬似ランダム性と組み合わせ論における二重の意味に関する議論を引き起こしています。