Local property reconstruction and monotonicity

DOI10.1007/978-3-642-16367-8_29MaRDI QIDQ4933387zbMATH OpenOpenAlexFDO

Authors C. Seshadhri, Michael Saks

Publication date 12 October 2010

Published in Property Testing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-16367-8_29

Mathematics Subject Classification ID

General topics in the theory of data (68P01) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Randomized algorithms (68W20)

Recommendations

• Local monotonicity reconstruction
• Property-preserving data reconstruction
• Algorithms and Computation
• Limitations of local filters of Lipschitz and monotone functions
• Limitations of local filters of Lipschitz and monotone functions

Cites work

• BPP has subexponential time simulations unless EXPTIME has publishable proofs
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Approximating the distance to monotonicity in high dimensions
• Estimating the distance to a monotone function
• Fast approximate PCPs for multidimensional bin-packing problems
• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• scientific article; zbMATH DE number 5764799 (Why is no real title available?)
• scientific article; zbMATH DE number 1857651 (Why is no real title available?)
• scientific article; zbMATH DE number 1418269 (Why is no real title available?)
• Improved low-degree testing and its applications
• Information theory in property testing and monotonicity testing in higher dimension
• Local monotonicity reconstruction
• Monotonicity testing over general poset domains
• On the efficiency of local decoding procedures for error-correcting codes
• On the strength of comparisons in property testing
• Private information retrieval
• Property testing and its connection to learning and approximation
• Property-preserving data reconstruction
• Pseudorandom generators without the XOR lemma
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Spot-checkers
• Testability and repair of hereditary hypergraph properties
• Testing monotonicity
• Testing monotonicity over graph products
• Tolerant property testing and distance approximation
• Transitive-closure spanners

Cited in

(6)

• Local regularity of the monotone rearrangement.
• Local monotonicity reconstruction
• Algorithms and Computation
• Limitations of local filters of Lipschitz and monotone functions
• Limitations of local filters of Lipschitz and monotone functions
• Property-preserving data reconstruction

This page was built for publication: Local property reconstruction and monotonicity

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