Streaming computations with a loquacious prover

DOI10.1145/2422436.2422471MaRDI QIDQ2986880zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Hartmut Klauck, Ved Prakash

Publication date 16 May 2017

Published in Proceedings of the 4th conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

data streamingdelegating computationinteractive proofsproof verification

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Streaming authenticated data structures
• scientific article; zbMATH DE number 6829278
• Verifiable stream computation and Arthur-Merlin communication
• Annotations in Data Streams
• Streaming Verification in Data Analysis

Cites work

• A model of interactive teaching
• A theory of goal-oriented communication
• A theory of the learnable
• Algorithmic Learning Theory
• Derandomizing polynomial identity tests means proving circuit lower bounds
• scientific article; zbMATH DE number 3154781 (Why is no real title available?)
• scientific article; zbMATH DE number 67625 (Why is no real title available?)
• scientific article; zbMATH DE number 67631 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Learning from different teachers
• Measuring teachability using variants of the teaching dimension
• Models of cooperative teaching and learning
• Occam's razor
• On specifying Boolean functions by labelled examples
• On the complexity of teaching
• On the limits of efficient teachability
• On the power of inductive inference from good examples
• Pseudorandom generators for space-bounded computation
• Recent Developments in Algorithmic Teaching
• Teachability in computational learning
• Teaching a smarter learner.
• Teaching Randomized Learners

Cited in

(9)

• The landscape of communication complexity classes
• Zero-information protocols and unambiguity in Arthur-Merlin communication
• Best-Order Streaming Model
• Streaming authenticated data structures
• Verifiable stream computation and Arthur-Merlin communication
• Best-order streaming model
• scientific article; zbMATH DE number 7650137 (Why is no real title available?)
• scientific article; zbMATH DE number 7758324 (Why is no real title available?)
• New lower bounds in Merlin-Arthur communication and graph streaming verification

This page was built for publication: Streaming computations with a loquacious prover

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