182 citations · 328 across the 20 of their papers we have counts for
Showing 2014 · cs.CCShow all
2 papers · 2 filters
cs.CC2014★ 1 cited
On the Computational Complexity of MapReduce
Benjamin Fish, Jeremy Kun, Ádám Dániel Lelkes +2
In this paper we study MapReduce computations from a complexity-theoretic perspective. First, we formulate a uniform version of the MRC model of Karloff et al. (2010). We then show…
cs.CC2014
On Coloring Resilient Graphs
Jeremy Kun, Lev Reyzin
We introduce a new notion of resilience for constraint satisfaction problems, with the goal of more precisely determining the boundary between NP-hardness and the existence of effi…