DC Field | Value | Language |
---|---|---|
dc.contributor.author | Bhattacharyya, Arnab | - |
dc.contributor.author | Grigorescu, Elena | - |
dc.contributor.author | Jha, Madhav | - |
dc.contributor.author | Jung, Kyomin | - |
dc.contributor.author | Raskhodnikova, Sofya | - |
dc.contributor.author | Woodruff, David P. | - |
dc.date.accessioned | 2011-08-12T05:44:26Z | - |
dc.date.available | 2011-08-12T05:44:26Z | - |
dc.date.issued | 2011-08-12 | - |
dc.identifier.uri | http://hdl.handle.net/10203/24883 | - |
dc.description.abstract | 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. | en |
dc.description.sponsorship | A.B. is supported by a DOE Computational Science Graduate Fellowship and NSF Awards 0514771, 0728645, 0732334. E.G. is supported by NSF award CCR-0829672. Supported by NSF/CCF award 0729171. S.R. is also supported by NSF/CCF CAREER award 0845701. | en |
dc.language.iso | en_US | en |
dc.subject | Property Testing | en |
dc.subject | Property Reconstruction | en |
dc.subject | Monotone Functions | en |
dc.subject | Spanners | en |
dc.subject | Hypercube | en |
dc.subject | Hypergrid | en |
dc.title | Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners | en |
dc.type | Article | en |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.