Open Collections

UBC Theses and Dissertations

UBC Theses Logo
Featured Collection

UBC Theses and Dissertations

Probabilistic testing of Boolean functions, or, How to test locally for a global property Majewski, Krzysztof Michał

Abstract

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 Metadata

Title
Probabilistic testing of Boolean functions, or, How to test locally for a global property
Creator
Majewski, Krzysztof Michał
Publisher
University of British Columbia
Date Issued
2003
Description
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).
Extent
929856 bytes
Genre
Thesis/Dissertation
Type
Text
File Format
application/pdf
Language
eng
Date Available
2009-10-29
Provider
Vancouver : University of British Columbia Library
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.
DOI
10.14288/1.0051650
URI
http://hdl.handle.net/2429/14328
Degree
Master of Science - MSc
Program
Computer Science
Affiliation
Science, Faculty of; Computer Science, Department of
Degree Grantor
University of British Columbia
Graduation Date
2003-11
Campus
UBCV
Scholarly Level
Graduate
Aggregated Source Repository
DSpace

Item Media

Item Citations and Data

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.