Add to ORKGAbstract. In this paper we study the MapReduce Class (MRC) defined by Karloff et al., which is a formal complexity-theoretic model of MapRe-duce. We show that constant-round MRC computations can decide reg-ular languages and simulate sublogarithmic space-bounded Turing ma-chines. In addition, we prove hierarchy theorems for MRC under certain complexity-theoretic assumptions. These theorems show that sufficiently increasing the number of rounds or the amount of time per processor strictly increases the computational power of MRC. Our work lays the foundation for further analysis relating MapReduce to established com-plexity classes. Our results also hold for Valiant’s BSP model of parallel computation and the MPC model of Beame et al
AbstractThis paper outlines a theory of parallel algorithms that emphasizes two crucial aspects of p...
We show that proving lower bounds in algebraic models of computation may not be easier than in the s...
This thesis focuses on problems which themselves encode questions about circuits or algorithms, also...
In this paper we study MapReduce computations from a complexity-theoretic perspective. First, we for...
The MapReduce framework has firmly established itself as one of the most widely used parallel comput...
In this thesis we examine some of the central problems in the theory of computational complexity, l...
This work explores fundamental modeling and algorithmic issues arising in the well-established MapRe...
This paper considers the well-known Turing machine model, the nondeterministic real-time Turing mach...
AbstractWe argue that uniform circuit complexity introduced by Borodin is a reasonable model of para...
Algorithmic metatheorems state that if a problem can be described in a certain logic and the inputs ...
We show that proving lower bounds in algebraic models of computation may not be easier than in the s...
The relative power of several computational models is considered. These models are the Turing machin...
We regard the MapReduce mechanism as a unifying principle in the domain of computer science. Going b...
(eng) Model theory has lately become a domain of interest to computer scientists. The reason is that...
Dans cette thèse, nous étudions l’algorithmique parallèle à grande échelle de quelques problèmes en ...
AbstractThis paper outlines a theory of parallel algorithms that emphasizes two crucial aspects of p...
We show that proving lower bounds in algebraic models of computation may not be easier than in the s...
This thesis focuses on problems which themselves encode questions about circuits or algorithms, also...
In this paper we study MapReduce computations from a complexity-theoretic perspective. First, we for...
The MapReduce framework has firmly established itself as one of the most widely used parallel comput...
In this thesis we examine some of the central problems in the theory of computational complexity, l...
This work explores fundamental modeling and algorithmic issues arising in the well-established MapRe...
This paper considers the well-known Turing machine model, the nondeterministic real-time Turing mach...
AbstractWe argue that uniform circuit complexity introduced by Borodin is a reasonable model of para...
Algorithmic metatheorems state that if a problem can be described in a certain logic and the inputs ...
We show that proving lower bounds in algebraic models of computation may not be easier than in the s...
The relative power of several computational models is considered. These models are the Turing machin...
We regard the MapReduce mechanism as a unifying principle in the domain of computer science. Going b...
(eng) Model theory has lately become a domain of interest to computer scientists. The reason is that...
Dans cette thèse, nous étudions l’algorithmique parallèle à grande échelle de quelques problèmes en ...
AbstractThis paper outlines a theory of parallel algorithms that emphasizes two crucial aspects of p...
We show that proving lower bounds in algebraic models of computation may not be easier than in the s...
This thesis focuses on problems which themselves encode questions about circuits or algorithms, also...