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

nondeterminismcommunication complexity

Mathematics Subject Classification ID

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

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

(13)

• Ambiguity and communication
• Self-verifying pushdown and queue automata
• On the power of laconic advice in communication complexity
• Probabilism versus Alternation for Automata
• Converting Self-verifying Automata into Deterministic Automata
• Self-verifying Cellular Automata
• Optimal simulation of self-verifying automata by deterministic automata
• On the non-deterministic communication complexity of regular languages
• On the Non-deterministic Communication Complexity of Regular Languages
• A little advice can be very helpful
• Iterative arrays with self-verifying communication cell
• A note on non-deterministic communication complexity with few witnesses
• Nondeterministic separations

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)