# On the Computational Complexity of MapReduce

DevFeed: [On the Computational Complexity of MapReduce](<https://devfeed.tech/articles/on-the-computational-complexity-of-mapreduce-40368.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/10/05/on-the-computational-complexity-of-mapreduce/>)

Published: 2014-10-05T09:00:30Z

Content type: article

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>), [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [Graphs](<https://devfeed.tech/topics/graphs.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [circuit-complexity](<https://devfeed.tech/tags/circuit-complexity.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [distributed-computing](<https://devfeed.tech/tags/distributed-computing.md>), [exponential-time-hypothesis](<https://devfeed.tech/tags/exponential-time-hypothesis.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [hierarchy](<https://devfeed.tech/tags/hierarchy.md>), [karloff](<https://devfeed.tech/tags/karloff.md>), [l-vs-p](<https://devfeed.tech/tags/l-vs-p.md>), [map-reduce](<https://devfeed.tech/tags/map-reduce.md>), [padding](<https://devfeed.tech/tags/padding.md>), [research](<https://devfeed.tech/tags/research.md>)

## AI overview

The article presents an accessible discussion of research analyzing the computational complexity of a theoretical model of the MapReduce framework. It describes open questions about MapReduce's power, including whether constant-round algorithms can determine graph connectivity and how the model relates to complexity classes such as P and L.

## Source excerpt

I recently wrapped up a fun paper with my coauthors Ben Fish, Adam Lelkes, Lev Reyzin, and Gyorgy Turan in which we analyzed the computational complexity of a model of the popular MapReduce framework. Check out the preprint on the arXiv. Update: this paper is now published in the proceedings of DISC2015. As usual I'll give a less formal discussion of the research here, and because the paper is a bit more technically involved than my previous work I'll be omitting some of the more pedantic details.