Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners
From MaRDI portal
Publication:5891744
DOI10.1137/100808186zbMath1248.05075OpenAlexW1983067233MaRDI QIDQ5891744
Arnab Bhattacharyya, Sofya Raskhodnikova, David P. Woodruff, Kyomin Jung, Elena Grigorescu, Madhav Jha
Publication date: 12 September 2012
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/b4fc802fae2242caa65d1875cac1ea6d22f95b0a
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)
Related Items
Sampling Correctors ⋮ Can we locally compute sparse connected subgraphs? ⋮ Steiner transitive-closure spanners of low-dimensional posets ⋮ Limitations of Local Filters of Lipschitz and Monotone Functions
