Given a directed acyclic graph (DAG) Gn = (Vn;E), a function
on Gn is given by f : Vn ! R. Such a function is monotone if
f(x) f(y) for all (x; y) 2 E. A local monotonicity reconstructor for
Gn, introduced by Saks and Seshadhri (SICOMP 2010), is a randomized
algorithm that, given access to an oracle for an almost monotone function
f : Vn ! R on Gn, can quickly evaluate a related function g : Vn ! R
which is guaranteed to be monotone. Furthermore, the reconstructor can
be implemented in a distributed manner.
Given a directed graph G = (V;E) and an integer k 1, a k-transitive-
closure-spanner (k-TC-spanner) of G is a directed graph H = (V;EH)
that has (1) the same transitive-closure as G and (2) diameter at most k.
Transitive-closure spanners are a common abstraction for applications in
access control, property testing and data structures.
In this paper, we show a connection between 2-TC-spanners of Gn and
local monotonicity reconstructors for Gn. We show that an ecient local
monotonicity reconstructor for Gn implies a sparse 2-TC-spanner of Gn,
providing a new technique for proving lower bounds for local monotonicity
reconstructors. We present tight upper and lower bounds on the size
of the sparsest 2-TC-spanners of the directed hypercube and hypergrid,
DAGs which are very-well studied in this area. These bounds imply lower
bounds for local monotonicity reconstructors for the hypergrid (hypercube)
that nearly match the known upper bounds.