Abstract. Given a directed graph G = (V, E) and an integer k ≥ 1, a k-transitive-closure-spanner (k-TCspanner) of G is a directed graph H = (V, E H ) 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. We show a connection between 2-TC-spanners and local monotonicity filters. A local monotonicity filter, introduced by Saks and Seshadhri (SIAM Journal on Computing, 2010), is a randomized algorithm that, given access to an oracle for an almost monotone function f : {1, 2, . . . , m} d → R, can quickly evaluate a related function g : {1, 2, . . . , m} d → R which is guaranteed to be monotone. Furthermore, the filter can be implemented in a distributed manner. We show that an efficient local monotonicity filter implies a sparse 2-TC-spanner of the directed hypergrid, providing a new technique for proving lower bounds for local monotonicity filters. Our connection is, in fact, more general: an efficient local monotonicity filter for functions on any partially ordered set (poset) implies a sparse 2-TC-spanner of the directed acyclic graph corresponding to the poset. We present nearly tight upper and lower bounds on the size of the sparsest 2-TC-spanners of the directed hypercube and hypergrid. These bounds imply stronger lower bounds for local monotonicity filters that nearly match the upper bounds of Saks and Seshadhri.
In addition to these works on upper bounds on monotonicity reconstruction, Bhattacharyya et al. in REF proved a lower bound for local monotonicity reconstruction of Saks and Seshadhri using transitive-closure spanners.
Lower bounds for local monotonicity reconstruction from transitive closure spanners
In RANDOM
Mathematics Computer Science