Communication Complexity and Lower Bounds on Multilective Computations

DOI10.1051/ITA:1999113MaRDI QIDQ4265538zbMATH OpenOpenAlexFDO

Authors 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/, https://eudml.org/doc/221992

zbMATH Keywords

multilective computationsprotocolsVLSI circuits

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1011685
• Lower bounds on communication complexity
• Lower bounds on threshold and related circuits via communication complexity
• Lower bounds on the multiparty communication complexity

Cites work

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

Cited in

(17)

• On the P versus NP intersected with co-NP question in communication complexity
• Lower bounds on the multiparty communication complexity
• The communication complexity of computing differentiable functions in a multicomputer network
• Non-deterministic communication complexity with few witnesses
• On the communication complexity of Lipschitzian optimization for the coordinated model of computation
• Size-treewidth tradeoffs for circuits computing the element distinctness function
• On the power of multiple reads in a chip
• Lower bounds for number-in-hand multiparty communication complexity, made easy
• The communication complexity of interleaved group products
• scientific article; zbMATH DE number 6691438 (Why is no real title available?)
• Languages with Bounded Multiparty Communication Complexity
• scientific article; zbMATH DE number 88975 (Why is no real title available?)
• scientific article; zbMATH DE number 1795910 (Why is no real title available?)
• Automata, Languages and Programming
• Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching
• The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems
• Some order dimension bounds for communication complexity problems

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

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