Abstract

This bootcamp talk will be an overview on testing Boolean functions. A Boolean function is a function which maps inputs of a domain to {0, 1} (in other words, encoding a subset of the domain) and the task in property testing is to approximately determine whether the function has a particular property. We aim for algorithms which are really, really efficient (think constant or poly-logarithmic queries to the function). We will cover the definitions of (standard) property testing and some variants, as well as some of the well-known algorithms and analyzes.

Attachment

Video Recording