Attribute estimation and testing quasi-symmetry

DOI10.1016/J.IPL.2008.10.011zbMATH Open1191.68853arXiv0708.2105OpenAlexW2038422144MaRDI QIDQ976083FDOQ976083

Nicholas Pippenger, Krzysztof Majewski

Publication date: 16 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: A Boolean function is symmetric if it is invariant under all permutations of its arguments; it is quasi-symmetric if it is symmetric with respect to the arguments on which it actually depends. We present a test that accepts every quasi-symmetric function and, except with an error probability at most delta>0, rejects every function that differs from every quasi-symmetric function on at least a fraction epsilon>0 of the inputs. For a function of n arguments, the test probes the function at O((n/epsilon)log(n/delta)) inputs. Our quasi-symmetry test acquires information concerning the arguments on which the function actually depends. To do this, it employs a generalization of the property testing paradigm that we call attribute estimation. Like property testing, attribute estimation uses random sampling to obtain results that have only "one-sided errors and that are close to accurate with high probability.

Full work available at URL: https://arxiv.org/abs/0708.2105

Recommendations

• Partially symmetric functions are efficiently isomorphism testable
• A characterization of constant-sample testable properties
• Testing juntas
• Nearly tight bounds for testing function isomorphism
• Nearly tight bounds for testing function isomorphism

zbMATH Keywords

randomized algorithmsBoolean functionsproperty testing

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Cites Work

• Property testing and its connection to learning and approximation
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing monotonicity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: Attribute estimation and testing quasi-symmetry

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