Property-preserving data reconstruction

DOI10.1007/s00453-007-9075-9zbMath1147.68017OpenAlexW2141078756MaRDI QIDQ930593

Nir Ailon, Seshadhri Comandur, Ding Liu, Bernard Chazelle

Publication date: 1 July 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9075-9

zbMATH Keywords

Monotonicity testingSublinear algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Related Items

Sampling Correctors, Can we locally compute sparse connected subgraphs?, Steiner transitive-closure spanners of low-dimensional posets, Constructing near spanning trees with few local inspections, Steiner Transitive-Closure Spanners of Low-Dimensional Posets, Approximating convex functions via non-convex oracles under the relative noise model, Local computation algorithms for graphs of non-constant degrees, Transitive-Closure Spanners: A Survey, Local Property Reconstruction and Monotonicity, Limitations of Local Filters of Lipschitz and Monotone Functions, Local algorithms for sparse spanning graphs, Unnamed Item

Cites Work

• Self-testing/correcting with applications to numerical problems
• Tolerant property testing and distance approximation
• Property testing and its connection to learning and approximation
• The height of a random binary search tree
• Robust Characterizations of Polynomials with Applications to Program Testing
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Unnamed Item
• Unnamed Item
• Unnamed Item