Communication Complexity and Lower Bounds on Multilective Computations

DOI10.1051/ITA:1999113zbMath0946.68052OpenAlexW2159271456MaRDI QIDQ4265538

Juraj Hromkovič

Publication date: 17 October 2000

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_1999__33_2_193_0/

zbMATH Keywords

VLSI circuitsprotocolsmultilective computations

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Size-treewidth tradeoffs for circuits computing the element distinctness function

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The performance of multilective VLSI algorithms
• Lower bounds on communication complexity
• Lower bounds for synchronous circuits and planar circuits
• Lower bounds for depth-restricted branching programs
• Nonlinear lower bounds on the number of processors of circuits with sublinear separators
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• A comparison of two lower-bound methods for communication complexity
• On the complexity of planar Boolean circuits
• On the power of multiple reads in a chip
• On lower bounds for read-\(k\)-times branching programs
• A very simple function that requires exponential size read-once branching programs.
• An exponential lower bound for real-time branching programs
• On the complexity of branching programs and decision trees for clique functions
• A Separator Theorem for Planar Graphs
• Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
• Communication Complexity

This page was built for publication: Communication Complexity and Lower Bounds on Multilective Computations