On multi-partition communication complexity

DOI10.1016/j.ic.2004.05.002zbMath1073.68030OpenAlexW2025380793MaRDI QIDQ1886038

Pavol Ďuriš, Georg Schnitger, Martin Sauerhoff, Stasys P. Jukna, Juraj Hromkovič

Publication date: 12 November 2004

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2004.05.002

zbMATH Keywords

Computational complexityLower bounds\(k\)-partition protocolsComplexity hierarchyMulti-partition communication complexityNon-obliviousnessRead-once branching programs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Network protocols (68M12)

Related Items (7)

Probabilism versus Alternation for Automata ⋮ Size-treewidth tradeoffs for circuits computing the element distinctness function ⋮ ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES ⋮ Parameterized Compilation Lower Bounds for Restricted CNF-Formulas ⋮ Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs. ⋮ On the P versus NP intersected with co-NP question in communication complexity ⋮ Resolution over linear equations modulo two

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounds on tradeoffs between randomness and communication complexity
• Communication complexity
• Meanders and their applications in lower bounds arguments
• Neither reading few bits twice nor reading illegally helps much
• Lower bounds on the size of sweeping automata
• Two-way deterministic finite automata are exponentially more succinct than sweeping automata
• Private vs. common random bits in communication complexity
• The power of nondeterminism and randomness for oblivious branching programs
• Time-space tradeoffs for branching programs
• A communication-randomness tradeoff for two-processor systems
• On lower bounds for read-\(k\)-times branching programs
• Time-space trade-off lower bounds for randomized computation of decision problems
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• Branching Programs and Binary Decision Diagrams
• Communication Complexity
• Nondeterminism and the size of two way finite automata

This page was built for publication: On multi-partition communication complexity