Fetching the paper…
Reading the bibliography…
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.
An inequality related to the isoperimetric inequality
L. Loomis and H. Whitney · 1949
Earlier work this paper cites.
Gaussian elimination is not optimal
V. Strassen · 1969
Earlier work this paper cites.
The Effect of Algebraic Structure on the Computational Complexity of Matrix Multiplication
L. R. Kerr · 1970
Earlier work this paper cites.
I/O complexity: The red-blue pebble game
J.-W. Hong and H. T. Kung · 1981
Earlier work this paper cites.
The universality of the shuffle-exchange network
C.-L. Wu and T.-Y. Feng · 1981
Earlier work this paper cites.
A communication-time tradeoff
C. H. Papadimitriou and J. D. Ullman · 1987
Earlier work this paper cites.
The input/output complexity of sorting and related problems
A. Aggarwal and J. S. Vitter · 1988
Earlier work this paper cites.
Communication complexity of PRAMs
A. Aggarwal, A. K. Chandra, and M. Snir · 1990
Earlier work this paper cites.
A bridging model for parallel computation
L. G. Valiant · 1990
Earlier work this paper cites.
Communication complexity for parallel divide-and-conquer
I.-C. Wu and H. T. Kung · 1991
Earlier work this paper cites.
Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes
F. T. Leighton · 1992
Earlier work this paper cites.
Bulk synchronous parallel computing – a paradigm for transportable software
T. Cheatham, A. F. Fahmy, D. C. Stefanescu, and L. G. Valiant · 1995
Earlier work this paper cites.
Extending the Hong-Kung model to memory hierarchies
J. E. Savage · 1995
Cited alongside, same era.
LogP: A practical model of parallel computation
D. E. Culler, R. M. Karp, D. A. Patterson, A. Sahay, E. E. Santos, K. E. Schauser, R. Subramonian, and T. von Eicken · 1996
Cited alongside, same era.
Models of Computation: Exploring the Power of Computing
J. E. Savage · 1998
Cited alongside, same era.
Bulk-synchronous parallel multiplication of Boolean matrices
A. Tiskin · 1998
Cited alongside, same era.
The Design and Analysis of Bulk-Synchronous Parallel Algorithms
A. Tiskin · 1998
Cited alongside, same era.
Processor-time tradeoffs under bounded-speed message propagation: Part II, lower bounds
G. Bilardi and F. Preparata · 1999
Cited alongside, same era.
A model of computation for MapReduce
H. J. Karloff, S. Suri, and S. Vassilvitskii · 2010
Later among the works it cites.
Minimizing communication in numerical linear algebra
G. Ballard, J. Demmel, O. Holtz, and O. Schwartz · 2011
Later among the works it cites.
Strong I/O lower bounds for binomial and FFT computation graphs
D. Ranjan, J. Savage, and M. Zubair · 2011
Later among the works it cites.
Communication-optimal parallel 2.5D matrix multiplication and LU factorization algorithms
E. Solomonik and J. Demmel · 2011
Later among the works it cites.
BSP (bulk synchronous parallelism)
A. Tiskin · 2011
Later among the works it cites.
A bridging model for multi-core computing
L. G. Valiant · 2011
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Communication-efficient parallel sorting
M. T. Goodrich · 1999
Cited alongside, same era.
On the space and access complexity of computation DAGs
G. Bilardi, A. Pietracaprina, and P. D’Alberto · 2000
Cited alongside, same era.
Communication lower bounds for distributed-memory matrix multiplication
D. Irony, S. Toledo, and A. Tiskin · 2004
Cited alongside, same era.
Cache oblivious stencil computations
M. Frigo and V. Strumpen · 2005
Cited alongside, same era.
Network-oblivious algorithms
G. Bilardi, A. Pietracaprina, G. Pucci, and F. Silvestri · 2007
Cited alongside, same era.
Provably good multicore cache performance for divide-and-conquer algorithms
G. E. Blelloch, R. A. Chowdhury, P. B. Gibbons, V. Ramachandran, S. Chen, and M. Kozuch · 2008
Cited alongside, same era.
Brief announcement: strong scaling of matrix multiplication algorithms and memory-independent communication lower bounds
G. Ballard, J. Demmel, O. Holtz, B. Lipshitz, and O. Schwartz · 2012
Later among the works it cites.
Graph expansion and communication costs of fast matrix multiplication
G. Ballard, J. Demmel, O. Holtz, and O. Schwartz · 2012
Later among the works it cites.
A lower bound technique for communication on BSP with application to the FFT
G. Bilardi, M. Scquizzato, and F. Silvestri · 2012
Later among the works it cites.
Space-round tradeoffs for MapReduce computations
A. Pietracaprina, G. Pucci, M. Riondato, F. Silvestri, and E. Upfal · 2012
Later among the works it cites.
Oblivious algorithms for multicores and networks of processors
R. A. Chowdhury, V. Ramachandran, F. Silvestri, and B. Blakeley · 2013
Closest in time.