All reports by Author Guy Moshkovitz:

__
TR15-019
| 3rd February 2015
__

Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira#### Constructing Near Spanning Trees with Few Local Inspections

__
TR11-138
| 24th October 2011
__

Guy Moshkovitz#### Complexity Lower Bounds through Balanced Graph Properties

Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let $G$ be a connected bounded-degree graph. Given an edge $e$ in $G$ we would like ... more >>>

Guy Moshkovitz

In this paper we present a combinatorial approach for proving complexity lower bounds. We mainly focus on the following instantiation of it. Consider a pair of properties of $m$-edge regular hypergraphs. Suppose they are ``indistinguishable'' with respect to hypergraphs with $m-t$ edges, in the sense that every such hypergraph has ... more >>>