Tradeoffs between nondeterminism and complexity for communication protocols and branching programs (extended abstract)

DOI10.1007/3-540-46541-3_12MaRDI QIDQ4501529zbMATH OpenFDO

Authors Juraj Hromkovič, Martin Sauerhoff

Publication date 26 April 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-46541-3_12

zbMATH Keywords

multipartition protocols

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 1688365
• The power of nondeterminism and randomness for oblivious branching programs
• On multi-partition communication complexity
• Communication-Space Tradeoffs for Unrestricted Protocols

Cited in

(14)

• Approximation of boolean functions by combinatorial rectangles
• Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
• The power of nondeterminism and randomness for oblivious branching programs
• On the power of randomized multicounter machines
• On multi-partition communication complexity
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-k-times branching programs
• scientific article; zbMATH DE number 1688365 (Why is no real title available?)
• Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
• The intractability of bounded protocols for on-line sequence transmission over non-FIFO channels
• Nondeterministic Communication with a Limited Number of Advice Bits
• Unexpected upper bounds on the complexity of some communication games
• On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
• Width hierarchy for \(k\)-OBDD of small width

This page was built for publication: Tradeoffs between nondeterminism and complexity for communication protocols and branching programs (extended abstract)

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