scientific article; zbMATH DE number 1500514

MaRDI QIDQ4501529zbMATH OpenFDO

Authors Juraj Hromkovič, Martin Sauerhoff

Publication date 26 April 2001

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

(13)

• scientific article; zbMATH DE number 1688365 (Why is no real title available?)
• Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
• Nondeterministic Communication with a Limited Number of Advice Bits
• Width hierarchy for \(k\)-OBDD of small width
• On multi-partition communication complexity
• Approximation of boolean functions by combinatorial rectangles
• On the power of randomized multicounter machines
• On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• 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
• The power of nondeterminism and randomness for oblivious branching programs
• On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata

This page was built for publication:

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