雙亞線性交互式接近性證明
本文研究雙亞線性交互式接近性證明（dsIPPs），這是一種超快速生成和驗證的證明系統，可用於證明關於海量輸入的近似斷言。證明者只需讀取輸入的一小部分（亞線性），而驗證者讀取的部分更少。作者為任意可由常寬度一次性無記憶分支程序（ROOBP）決定的屬性構造了此類系統，還構建了針對輸入漢明重量近似驗證以及有界度圖模型中二分性鬆弛的證明系統。
雙亞線性交互式接近性證明（dsIPPs）是一種新穎的證明系統，旨在解決海量數據場景下的高效驗證問題。傳統交互式證明要求證明者讀取整個輸入才能生成證明，而dsIPP將這一要求降低到只需讀取輸入的一小部分（亞線性），驗證者甚至可以讀取更少的數據。這種近似驗證的思想源於屬性測試（property testing）領域，即驗證者不需要精確判斷輸入是否滿足屬性，只需判斷輸入是否“接近”滿足該屬性。在dsIPP中，誠實的證明者可以在亞線性時間內使驗證者接受所有屬於該屬性的輸入，而任何惡意的證明者都無法使驗證者接受遠離該屬性的輸入。
該研究由魏茨曼科學研究所的Noga Amir、Oded Goldreich和Guy N. Rothblum共同完成。他們首先為任意可由常寬度一次性無記憶分支程序（ROOBP）決定的屬性構造了通用的dsIPP。ROOBP是一類重要的計算模型，它允許一次讀取輸入比特且不保留狀態，常寬度意味着使用的內存很小。這類模型覆蓋了許多自然屬性，如某些圖性質或布爾函數。此外，他們還針對輸入漢明重量（即1的個數）的近似驗證設計了一個dsIPP，允許證明者在不讀取整個輸入的情況下證明輸入中1的個數大約為某個值。針對有界度圖模型，他們還構造了二分性（bipartiteness）的鬆弛版本的dsIPP，即證明圖是否接近二分圖。
這些成果的理論意義在於，它展示了即使在證明者無法完全讀取輸入的情況下，仍能提供可驗證的證明。實際應用中，這對於大規模數據集（如基因組數據、網絡流量、社交網絡圖等）的驗證非常有用，因為讀取整個數據集的成本可能過高。與傳統的交互式證明相比，dsIPP顯著降低了證明者的計算開銷，使得原本不可行的驗證任務變得可能。例如，在處理一個包含數十億條記錄的數據庫時，證明者只需讀取其中的一小部分即可證明整個數據庫滿足某個全局性質。該論文發表於2026年7月，並被頂級會議FOCS接收。未來，該工作可能推動更高效驗證協議的發展，並進一步縮小理論計算機科學與實際大數據分析之間的差距。