Property-preserving data reconstruction

DOI10.1007/S00453-007-9075-9zbMATH Open1147.68017OpenAlexW2141078756MaRDI QIDQ930593FDOQ930593

Authors: Nir Ailon, Bernard Chazelle, Seshadhri Comandur, Ding Liu 

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

Recommendations

• Algorithms and Computation
• Local property reconstruction and monotonicity
• Local monotonicity reconstruction
• Online geometric reconstruction
• Limitations of local filters of Lipschitz and monotone functions

zbMATH Keywords

Monotonicity testingSublinear algorithms

Mathematics Subject Classification ID

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

Cites Work

• Property testing and its connection to learning and approximation
• Self-testing/correcting with applications to numerical problems
• Robust Characterizations of Polynomials with Applications to Program Testing
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Distribution-free property testing
• Tolerant property testing and distance approximation
• The height of a random binary search tree
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Cited In (17)

• Steiner transitive-closure spanners of low-dimensional posets
• Steiner transitive-closure spanners of low-dimensional posets
• Preserving data utility via BART
• Approximating convex functions via non-convex oracles under the relative noise model
• Space-efficient local computation algorithms
• Limitations of local filters of Lipschitz and monotone functions
• Transitive-closure spanners: a survey
• Local monotonicity reconstruction
• Preventing Silent Data Corruptions from Propagating During Data Reconstruction
• Local property reconstruction and monotonicity
• Limitations of local filters of Lipschitz and monotone functions
• Sampling correctors
• Algorithms and Computation
• Can we locally compute sparse connected subgraphs?
• Local algorithms for sparse spanning graphs
• Constructing near spanning trees with few local inspections
• Local computation algorithms for graphs of non-constant degrees

This page was built for publication: Property-preserving data reconstruction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q930593)