Attribute estimation and testing quasi-symmetry
Document Type
Article
Department
Mathematics (HMC)
Publication Date
1-2009
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 δ>0, rejects every function that differs from every quasi-symmetric function on at least a fraction ε>0 of the inputs. For a function of n arguments, the test probes the function at O((n/ε)log(n/δ)) 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.
Rights Information
© 2008 Elsevier B.V.
Terms of Use & License Information
DOI
10.1016/j.ipl.2008.10.011
Recommended Citation
Krzysztof Majewski, Nicholas Pippenger, "Attribute estimation and testing quasi-symmetry", Information Processing Letters, 109:4 (January 2009) 233-237.
