Streaming Interactive Proofs and Arthur-Merlin Communication
summary
Claims a verifier with only polylog space can answer point membership and nearest-neighbor queries by turning the stream into a multilinear polynomial, storing its evaluation at a random point, and asking a helper for the polynomial restricted to a line; this yields a streaming interactive proof (SIP) with soundness error about B/|F| (pick |F|≈1000B), verifier space and communication both ≈ log n log log n, and a three-round protocol for nearest neighbor via a virtual stream of balls; helper work may be heavy.
AI-written summary · about