Testing Boolean Functions

Explore an overview of testing Boolean functions in this bootcamp talk from the Sublinear Algorithms Boot Camp. Delve into the concept of Boolean functions, which map inputs from a domain to {0, 1}, effectively encoding subsets of the domain. Learn about property testing algorithms designed to efficiently determine whether a function possesses specific properties, often with constant or poly-logarithmic queries. Examine definitions of standard property testing and its variants, and study well-known algorithms and analyses in this field. Gain insights from Erik Waingarten of the University of Pennsylvania as he presents this comprehensive introduction to an important topic in sublinear algorithms.

Testing Boolean Functions