雙亞線性互動式接近性證明
本文研究雙亞線性互動式接近性證明（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接收。未來，該工作可能推動更高效驗證協議的發展，並進一步縮小理論電腦科學與實際大數據分析之間的差距。