On the communication complexity of distributed algebraic computation

DOI10.1145/174147.174149zbMATH Open0799.68121OpenAlexW2085716634MaRDI QIDQ4285628FDOQ4285628

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

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

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)

Cited In (9)

• Optimal One-Pass Nonparametric Estimation Under Memory Constraint
• Randomized communication complexity for linear algebra problems over finite fields
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)