Information theory in property testing and monotonicity testing in higher dimension

DOI10.1016/j.ic.2006.06.001zbMath1171.68492OpenAlexW1986542077MaRDI QIDQ859828

Bernard Chazelle, Nir Ailon

Publication date: 22 January 2007

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2006.06.001

zbMATH Keywords

information theoryproperty testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Information theory (general) (94A15) Randomized algorithms (68W20)

Related Items

Parameterized property testing of functions, Approximating the distance to monotonicity of Boolean functions, Unnamed Item, Erasure-Resilient Property Testing, Monotonicity testing and shortest-path routing on the cube, Almost Optimal Distribution-Free Sample-Based Testing of k-Modality, TESTING FOR FORBIDDEN POSETS IN ORDERED ROOTED FORESTS, Transitive-Closure Spanners: A Survey, Local Property Reconstruction and Monotonicity, Estimating the distance to a monotone function, Unnamed Item, Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity, Unnamed Item, Exponentially improved algorithms and lower bounds for testing signed majorities

Cites Work

• On the strength of comparisons in property testing
• Property testing and its connection to learning and approximation
• Monotonicity testing over general poset domains
• Automata, Languages and Programming
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Testing monotonicity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item