Apple ML Research
· Cloud & Big Tech
Doubly Sub-linear Interactive Proofs of Proximity
We study doubly sub-linear interactive proofs of proximity (dsIPPs): proofs that are ultra-fast to generate, and can be used to prove approximate assertions about a huge input. Proof generation is ultra-fast in the sense that it only requires reading a small (sub-linear) portion of the input. Approximate verification o