![Sublinear Algorithms Wide Format Logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-11/Sublinear%20Algorithms.jpg?h=8538f4e5&itok=RTUg456n)
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.