Property-preserving data reconstruction

DOI10.1007/S00453-007-9075-9MaRDI QIDQ930593zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

Monotonicity testingSublinear algorithms

Mathematics Subject Classification ID

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

Recommendations

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

Cites work

• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• scientific article; zbMATH DE number 1241835 (Why is no real title available?)
• scientific article; zbMATH DE number 1857651 (Why is no real title available?)
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Distribution-free property testing
• Property testing and its connection to learning and approximation
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• The height of a random binary search tree
• Tolerant property testing and distance approximation

Cited in

(17)

• Constructing near spanning trees with few local inspections
• 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
• Transitive-closure spanners: a survey
• Limitations of local filters of Lipschitz and monotone functions
• 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
• 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)