2013/07/06 by Michele Scquizzato, Scquizzato, Michele, Francesco Silvestri +1
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #Quantum Computing Algorithms and Architecture #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1307.1805
openalex publication_date 2013/07/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give lower bounds on the communication complexity required to solve several computational problems in a distributed-memory parallel machine, namely standard matrix multiplication, stencil computations, comparison sorting, and the Fast Fourier Transform. We revisit the assumptions under which preceding results were derived and provide new lower bounds which use much weaker and appropriate hypotheses. Our bounds rely on a mild assumption on work distribution, and strengthen previous results which require either the computation to be balanced among the processors, or specific initial distributions of the input data, or an upper bound on the size of processors' local memories.