當(dāng) Daniel Spielman 在 2001 年與人合著了一篇關(guān)于算法平滑分析的論文時(shí)，它對(duì)數(shù)學(xué)和計(jì)算機(jī)科學(xué)領(lǐng)域產(chǎn)生了重大影響。一項(xiàng)新的獎(jiǎng)項(xiàng)表明，20 年后，它同樣令人印象深刻。

計(jì)算機(jī)科學(xué)、統(tǒng)計(jì)學(xué)和數(shù)據(jù)科學(xué)以及數(shù)學(xué)和應(yīng)用數(shù)學(xué)的 Sterling 教授 Spielman 和他的經(jīng)常合作者，Shang-Hua Teng 的論文獲得了 20 年 STOC 時(shí)間測(cè)試獎(jiǎng)。該獎(jiǎng)項(xiàng)表彰發(fā)表在年度 ACM 計(jì)算理論研討會(huì)論文集上的論文。該獎(jiǎng)項(xiàng)于 2021 年設(shè)立，此后每年頒發(fā)一次。共有三個(gè)獎(jiǎng)項(xiàng)，針對(duì)頒發(fā)獎(jiǎng)項(xiàng)的前 10 年、20 年和 30 年舉行的 STOC 會(huì)議。

他們的工作引入了“平滑分析”作為衡量算法復(fù)雜性的一種方法，人們認(rèn)為它可以更真實(shí)地理解算法的執(zhí)行方式。該概念涉及某些算法在實(shí)踐中比在理論中更好的現(xiàn)象。

Spielman 和 Teng 是南加州大學(xué)計(jì)算機(jī)科學(xué)與數(shù)學(xué)的 Seeley G. Mudd 教授，他們?cè)谄交治龇矫娴墓ぷ鳙@得了許多其他獎(jiǎng)項(xiàng)，包括 2008 年享有盛譽(yù)的哥德?tīng)柂?jiǎng)。

他們引入的平滑分析框架依賴(lài)于深入的數(shù)學(xué)分析和洞察力。它對(duì)理論計(jì)算機(jī)科學(xué)和其他學(xué)科至關(guān)重要——自 2001 年以來(lái)，已有大量基于它的研究。

該領(lǐng)域的人士認(rèn)為，這篇論文對(duì)于開(kāi)發(fā)預(yù)測(cè)算法和啟發(fā)式算法在真實(shí)數(shù)據(jù)和真實(shí)計(jì)算機(jī)上的性能的巨大挑戰(zhàn)至關(guān)重要。