University of British Columbia
Probabilistic testing of Boolean functions, or, How to test locally for a global property
Abstract
dc:descriptionProbabilistic 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).
Degree
thesis:*- Name thesis:degree_name
- Master of Science - MSc
- Level thesis:degree_level
- master's
- Discipline thesis:degree_discipline
- Computer Science
- Grantor dc:publisher
- University of British Columbia
- Year dc:date
- 2003
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Majewski, Krzysztof Michał
Rights
dc:rights- Statement dc:rights
-
- For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
- Language dc:language
- eng
Identifiers
dc:identifier.*- Handle dc:identifier
- http://hdl.handle.net/2429/14328