Local Property Reconstruction and Monotonicity

DOI10.1007/978-3-642-16367-8_29zbMath1310.68232OpenAlexW1570645758MaRDI QIDQ4933387

C. Seshadhri, Michael E. 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

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

Cites Work

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