3 citations · 10 across the 8 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
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…