일반적인 분포 특성을 위한 대화형 증명(Interactive Proofs)

데이터 분석가(Bob)가 미지의 분포에 대해 내린 주장이 사실인지, 데이터 수집자(Alice)가 직접 분석을 수행하는 것보다 적은 자원으로 검증할 수 있는 방법론을 제시한다.

본 연구에서는 bounded-depth circuit(제한된 깊이의 회로)로 결정 가능한 일반적인 분포 특성에 대해 **대화형 증명 시스템(Interactive Proof Systems)**을 구축했다. 분포의 서포트 크기를 $N$, 회로의 깊이를 $D$라고 할 때, 검증자의 샘플 복잡도, 실행 시간, 통신 복잡도는 모두 $\tilde{O}(D + N^{0.99})$로 제한된다.

이 시스템은 다음과 같은 특징을 가진다.

• 이중 효율성(Doubly-efficient): 정직한 증명자는 다항 시간 내에 동작하며, 준선형(quasi-linear) 수준의 샘플 복잡도를 가진다.
• 확장성: bounded-depth Turing machine으로 결정 가능한 특성에 대해서도 유사한 결과를 보여준다.
• 기존 연구와의 차별점: 이전 연구가 'label-invariant'라는 제한된 클래스에 국한되었던 것과 달리, 본 연구는 훨씬 더 일반적인 분포 특성까지 다룬다.

단순한 특성이라 할지라도 증명자 없이 직접 결정하려면 준선형 수준의 샘플 복잡도와 실행 시간이 필요하다는 점을 명시하며, 본 시스템의 효율성을 강조한다.