Abstract:

We are going to talk about the following nice little problem: Given n Boolean functions, let us "color" every sample, compatible with one of these functions, with some Boolean function, not necessarily one of the original n, that is compatible with this sample. What is the smallest number of colors that every chain of samples should have?
We are going to solve this one, and, additionally, we are going to talk about the machine-learning roots of this problem, and about some other nice little questions in the area where the solution would lead us.
The talk is based on the joint work with Zachary Chase, Shay Moran, and Amir Yehudayoff.