  The MapReduce framework has firmly established itself as one of the most
widely used parallel computing platforms for processing big data on tera- and
peta-byte scale. Approaching it from a theoretical standpoint has proved to be
notoriously difficult, however. In continuation of Goodrich et al.'s early
efforts, explicitly espousing the goal of putting the MapReduce framework on
footing equal to that of long-established models such as the PRAM, we
investigate the obvious complexity question of how the computational power of
MapReduce algorithms compares to that of combinational Boolean circuits
commonly used for parallel computations. Relying on the standard MapReduce
model introduced by Karloff et al. a decade ago, we develop an intricate
simulation technique to show that any problem in NC (i.e., a problem solved by
a logspace-uniform family of Boolean circuits of polynomial size and a depth
polylogarithmic in the input size) can be solved by a MapReduce computation in
O(T(n)/ log n) rounds, where n is the input size and T(n) is the depth of the
witnessing circuit family. Thus, we are able to closely relate the standard,
uniform NC hierarchy modeling parallel computations to the deterministic
MapReduce hierarchy DMRC by proving that NC^(i+1) is contained in DMRC^i for
all natural i, including 0. Besides the theoretical significance, this result
that has important applied aspects as well. In particular, we show for all
problems in NC^1---many practically relevant ones such as integer
multiplication and division, the parity function, and recognizing balanced
strings of parentheses being among these---how to solve them in a constant
number of deterministic MapReduce rounds.
