182 citations · 328 across the 20 of their papers we have counts for
4 papers · 1 filter
Reconstructing Arbitrary Trees from Traces in the Tree Edit Distance Model
Thomas Maranzatto
In this paper, we consider the problem of reconstructing trees from traces in the tree edit distance model. Previous work by Davies et al. (2019) analyzed special cases of reconstr…
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…
Statistical Algorithms and a Lower Bound for Detecting Planted Clique
Vitaly Feldman, Elena Grigorescu, Lev Reyzin +2
We introduce a framework for proving lower bounds on computational problems over distributions against algorithms that can be implemented using access to a statistical query oracle…