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

lower boundscommunication complexityfield extensionalgebraic computationclassical algebraic geometry

Mathematics Subject Classification ID

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

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

(9)

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

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)