UBC Theses and Dissertations
Probabilistic testing of Boolean functions, or, How to test locally for a global property Majewski, Krzysztof Michał
Probabilistic testing is a general problem that has fundamental scientific value as well as direct applications to important concepts in theoretical computer science, such as probabilistically checkable proofs (PCP). We consider specifically the testing of Boolean functions, discussing some key existing results and providing new results for several classes of functions. In particular, we give efficient tests for a Boolean function to be symmetric (invariant under permutation of its variables) and quasi-symmetric (a symmetric function of the variables it actually depends on).
Item Citations and Data