Nondeterministic Communication with a Limited Number of Advice Bits

DOI10.1137/S0097539702414622MaRDI QIDQ4441900zbMATH OpenOpenAlexFDO

Authors Juraj Hromkovič, Georg Schnitger

Publication date 8 January 2004

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539702414622

zbMATH Keywords

communication complexitynondeterminism

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1256774
• On the power of laconic advice in communication complexity
• scientific article; zbMATH DE number 1335889
• Non-deterministic communication complexity with few witnesses
• scientific article; zbMATH DE number 1500514

Cited in

(15)

• A note on non-deterministic communication complexity with few witnesses
• On the power of laconic advice in communication complexity
• Nondeterministic separations
• On the Non-deterministic Communication Complexity of Regular Languages
• On the non-deterministic communication complexity of regular languages
• Converting Self-verifying Automata into Deterministic Automata
• scientific article; zbMATH DE number 1256774 (Why is no real title available?)
• scientific article; zbMATH DE number 1335889 (Why is no real title available?)
• Self-verifying pushdown and queue automata
• Ambiguity and communication
• Optimal simulation of self-verifying automata by deterministic automata
• A little advice can be very helpful
• Self-verifying Cellular Automata
• Probabilism versus Alternation for Automata
• Iterative arrays with self-verifying communication cell

This page was built for publication: Nondeterministic Communication with a Limited Number of Advice Bits

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