On the communication complexity of distributed algebraic computation

DOI10.1145/174147.174149MaRDI QIDQ4285628zbMATH OpenOpenAlexFDO

Authors Zhi-Quan Luo, John N. Tsitsiklis

Publication date 24 March 1994

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/1721.1/3117

zbMATH Keywords

algebraic computationclassical algebraic geometrycommunication complexityfield extensionlower bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Distributed algorithms (68W15) Symbolic computation and algebraic computation (68W30)

Recommendations

• One-way communication complexity of computing a collection of rational functions
• Trade-offs between communication and space
• scientific article; zbMATH DE number 88975
• Probabilistic communication complexity
• On the Communication Complexity of Solving a Polynomial Equation

Cited in

(11)

• The communication complexity of computing differentiable functions in a multicomputer network
• One-way communication complexity of computing a collection of rational functions
• Communication complexity and orthogonal polynomials
• Randomized communication complexity for linear algebra problems over finite fields
• scientific article; zbMATH DE number 5972643 (Why is no real title available?)
• On the Communication Complexity of Solving a Polynomial Equation
• scientific article; zbMATH DE number 1223708 (Why is no real title available?)
• On the average communication complexity of asynchronous distributed algorithms
• The Communication Complexity of Distributed epsilon-Approximations
• Distributed Algorithmic Mechanism Design and Algebraic Communication Complexity
• Optimal One-Pass Nonparametric Estimation Under Memory Constraint

This page was built for publication: On the communication complexity of distributed algebraic computation

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