{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:56:45Z","timestamp":1787320605442,"version":"build-2736575974"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>Given a directed graph $G = (V,E)$ and an integer $k \\geq 1$, a k-transitive-closure-spanner (k-TC-spanner) 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 used 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 J. Comput., pp. 2897\u20132926], is a randomized algorithm that, given access to an oracle for an almost monotone function $f : \\{1,2,\\dots,m\\}^d \\to \\mathbb{R}$, can quickly evaluate a related function $g : \\{1,2,\\dots,m\\}^d \\to \\mathbb{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.<\/jats:p>","DOI":"10.1137\/100808186","type":"journal-article","created":{"date-parts":[[2012,5,15]],"date-time":"2012-05-15T19:00:16Z","timestamp":1337108416000},"page":"618-646","source":"Crossref","is-referenced-by-count":17,"title":["Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners"],"prefix":"10.1137","volume":"26","author":[{"given":"Arnab","family":"Bhattacharyya","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elena","family":"Grigorescu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Madhav","family":"Jha","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kyomin","family":"Jung","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sofya","family":"Raskhodnikova","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,5,15]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9075-9"},{"key":"R2","unstructured":"N. Alon and B. Schieber,\n                      Optimal Preprocessing for Answering On-line Product Queries\n                      , Technical Report 71\/87, School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv, Israel, 1987."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"M. J. Atallah, M. Blanton, N. Fazio, and K. B. Frikken,\n                      Dynamic and efficient key management for access hierarchies\n                      , ACM Trans. Inf. Syst. Secur., 12 (2009), 18.","DOI":"10.1145\/1455526.1455531"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"B. Awerbuch,\n                      Communication-time trade-offs in network synchronization\n                      , in Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing (PODC'85), M. Malcolm and R. Strong, eds., ACM, New York, 1985, pp. 272\u2013276.","DOI":"10.1145\/323596.323621"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198518"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"A. Bhattacharyya, E. Grigorescu, M. Jha, K. Jung, S. Raskhodnikova, and D. P. Woodruff,\n                      Lower bounds for local monotonicity reconstruction from transitive-closure spanners\n                      , in Proceedings of RANDOM 2010, M. J. Serna, R. Shaltiel, K. Jansen, and J. D. P. Rolim, eds., Lecture Notes in Comput. Sci. 6302, Springer, New York, 2010, pp. 448\u2013461.","DOI":"10.1007\/978-3-642-15369-3_34"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"A. Bhattacharyya, E. Grigorescu, K. Jung, S. Raskhodnikova, and D. P. Woodruff,\n                      Transitive-closure spanners\n                      , in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, C. Mathieu, ed., SIAM, Philadelphia, 2009, pp. 932\u2013941.","DOI":"10.1137\/1.9781611973068.101"},{"key":"R8","first-page":"111","volume":"1","author":"Bodlaender H. L.","year":"1994","journal-title":"Nordic J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1236-6064","issn-type":"print"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"A. K. Chandra, S. Fortune, and R. J. Lipton,\n                      Lower bounds for constant depth circuits for prefix problems\n                      , in Proceedings of ICALP, Josep D\u00edaz, ed., Lecture Notes in Comput. Sci. 154, Springer, New York, 1983, pp. 109\u2013117.","DOI":"10.1007\/BFb0036901"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90015-7"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840366"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261295"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331610"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1134"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.08.001"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"Y. Dodis, O. Goldreich, E. Lehman, S. Raskhodnikova, D. Ron, and A. Samorodnitsky,\n                      Improved testing algorithms for monotonicity\n                      , in Proceedings of RANDOM 1999, D. S. Hochbaum, K. Jansen, J. D. P. Rolim, and A. Sinclair, eds., Lecture Notes in Comput. Sci. 1671, Springer, New York, 1999, pp. 97\u2013108.","DOI":"10.1007\/978-3-540-48413-4_10"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103968"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070011"},{"key":"R19","unstructured":"W. Hesse,\n                      Directed graphs requiring large numbers of shortcuts\n                      , in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, SIAM, Philadelphia, 2003, pp. 665\u2013669."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"G. Narasimhan and M. H. M. Smid,\n                      Geometric Spanner Networks\n                      , Cambridge University Press, Cambridge, UK, 2007.","DOI":"10.1017\/CBO9780511546884"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/0218050"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65953"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"S. Raskhodnikova,\n                      Transitive-closure spanners: A survey\n                      , in Property Testing, O. Goldreich, ed., Lecture Notes in Comput. Sci. 6390, Springer, Heidelberg, 2010, pp. 167\u2013196.","DOI":"10.1007\/978-3-642-16367-8_10"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"L. Roditty, M. Thorup, and U. Zwick,\n                      Roundtrip spanners and roundtrip routing in directed graphs\n                      , ACM Trans. Algorithms, 4 (2008), 29.","DOI":"10.1145\/1367064.1367069"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/080728561"},{"key":"R27","unstructured":"R. Seidel,\n                      Understanding the Inverse Ackermann Function\n                      , slide series, available online at http:\/\/cgi.di. uoa.gr\/$\\!_{^{\\sim}}\\!$ewcg06\/invited\/Seidel.pdf, 2006."},{"key":"R28","doi-asserted-by":"crossref","unstructured":"S. Solomon,\n                      An optimal-time construction of sparse Euclidean spanners with tiny diameter\n                      , in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, D. Randall, ed., SIAM, Philadelphia, 2011, pp. 820\u2013839.","DOI":"10.1137\/1.9781611973082.65"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"M. Thorup,\n                      On shortcutting digraphs\n                      , in Graph-Theoretic Concepts in Computer Science, Proceedings of the 18th International Workshop (WG), Wiesbaden-Naurod, Germany, 1992, Lecture Notes in Comput. Sci. 657, Springer, New York, 1993, pp. 205\u2013211.","DOI":"10.1007\/3-540-56402-0_48"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001668"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0829"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"M. Thorup and U. Zwick,\n                      Compact routing schemes\n                      , in Proceedings of SPAA '01, A. Rosenberg, ed., ACM, New York, 2001, pp. 1\u201310.","DOI":"10.1145\/378580.378581"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"A. C. Yao,\n                      Space-time tradeoff for answering range queries (extended abstract)\n                      , in Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, H. R. Lewis, B. B. Simons, W. A. Burkhard, and L. H. Landweber, eds., ACM, New York, 1982, pp. 128\u2013136.","DOI":"10.1145\/800070.802185"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100808186","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:58:28Z","timestamp":1787317108000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100808186"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/100808186"],"URL":"https:\/\/doi.org\/10.1137\/100808186","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}