182 citations · 328 across the 20 of their papers we have counts for
3 papers · 1 filter
Network installation and recovery: approximation lower bounds and faster exact formulations
Alexander Gutfraind, Jeremy Kun, Ádám D. Lelkes +1
We study the Neighbor Aided Network Installation Problem (NANIP) introduced previously which asks for a minimal cost ordering of the vertices of a graph, where the cost of visiting…
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…
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…