Annotations in data streams

DOI10.1145/2636924MaRDI QIDQ4962165zbMATH OpenOpenAlexFDO

Authors Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler

Publication date 30 October 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2636924

zbMATH Keywords

annotationsdata streamsinteractive proof

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Annotations in Data Streams
• Annotations for Sparse Data Streams
• Semi-streaming algorithms for annotated graph streams

Cited in

(11)

• An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
• Zero-information protocols and unambiguity in Arthur-Merlin communication
• Annotations in Data Streams
• An exponential separation between MA and AM proofs of proximity
• Verifiable stream computation and Arthur-Merlin communication
• Annotations for Sparse Data Streams
• scientific article; zbMATH DE number 7650137 (Why is no real title available?)
• scientific article; zbMATH DE number 7758324 (Why is no real title available?)
• Streaming zero-knowledge proofs
• New lower bounds in Merlin-Arthur communication and graph streaming verification
• SNARK lower bounds via communication complexity

This page was built for publication: Annotations in data streams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4962165)