Space-bounded communication complexity

DOI10.1145/2422436.2422456MaRDI QIDQ2986867zbMATH OpenOpenAlexFDO

Authors Joshua Brody, Shiteng Chen, Periklis A. Papakonstantinou, Hao Song, Xiaoming Sun

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.2422456

zbMATH Keywords

communication complexitymemory-boundedspace-bounded

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Lower bounds on communication complexity
• scientific article; zbMATH DE number 4068270
• Lower bounds in communication complexity
• Communication complexity
• scientific article; zbMATH DE number 1361464
• scientific article; zbMATH DE number 3881884
• Communication complexity
• scientific article; zbMATH DE number 4147508
• Communication Complexity
• Communication Complexity

Cites work

• 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?)
• 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
• 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 Randomized Learners
• Teaching a smarter learner.

Cited in

(3)

• Communication memento: memoryless communication complexity
• Communication-Space Tradeoffs for Unrestricted Protocols
• Linear space bootstrap communication schemes

This page was built for publication: Space-bounded communication complexity

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