Verifying Computations with Streaming Interactive Proofs

Summary: Introduces streaming interactive proofs where verifiers use one-pass, logarithmic space, communication, and rounds, yet detect cheating with negligible error. Practical protocols for core database/streaming tasks yield exponential verifier savings and scalable performance. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 10521
Venue: VLDB
Year: 2012
Pagerank: -
Overall Rank: 13,666 | 6.24%
DOI: 10.14778/2047481.2047484

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Graham Cormode (AT&T)
2. Justin Thaler (Harvard University)
3. Ke Yi (Hong Kong University of Science and Technology)

BibTeX Citation

@article{cormode_vldb12,
        title = {{Verifying Computations with Streaming Interactive Proofs}},
        author = {Cormode, Graham and Thaler, Justin and Yi, Ke},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {1},
        pages = {25--36},
        doi = {10.14778/2047481.2047484},
        url = {https://doi.org/10.14778/2047481.2047484},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,608	Lightweight Authentication of Linear Algebraic Queries on Data Streams	2013	SIGMOD	5.2470962e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
4,381	Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams	2007	VLDB	6.7333392e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,258	Correctness in Stream Processing: Challenges and Opportunities	2022	CIDR
2	4,080	Specification and Verification of Data-driven Web Services	2004	PODS
3	10,289	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD
4	5,874	Verification of Relational Data-Centric Dynamic Systems with External Services	2013	PODS
5	5,426	Practical Authenticated Pattern Matching with Optimal Proof Size	2015	VLDB
6	2,350	Query Execution Assurance for Outsourced Databases	2005	VLDB
7	4,887	Scalable Verification for Outsourced Dynamic Databases	2009	VLDB
8	2,125	Verification of Communicating Data-Driven Web Services	2006	PODS
9	9,608	Lightweight Authentication of Linear Algebraic Queries on Data Streams	2013	SIGMOD
10	4,381	Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams	2007	VLDB