Theory Seminar: Minimizing the Expected Cost of Evaluating Boolean Functions

Friday, August 11, 2017 -
11:00am to 12:00pm
CS 5331

Speaker Name: 

Lisa Hellerstein

Speaker Institution: 

NYU Tandon School of Engineering



Cookies Location: 

CS 5331


Consider the following problem: A company produces units of a product that undergo tests before being shipped. Individual tests have different costs, and test outcomes are binary. Certain combinations of test outcomes disqualify a unit from being shipped, and testing of the unit can stop as soon as such a combination is detected. Determine the optimal order in which to perform the tests so as to minimize expected testing cost.

The above is a concrete version of an abstract problem: determining how to minimize the expected cost of evaluating a given Boolean function. In this talk, we will survey results about such problems for both independent and non-independent distributions on the inputs, for various classes of Boolean functions. We will discuss approximation algorithms based on reductions to submodular covering problems, and connections to submodular goal value, a related complexity measure for Boolean functions. We will also describe open problems.

This talk includes joint work with Nathaniel Grammel, Devorah Kletenik, Patrick Lin, Eric Bach, Sarah Allen, Tonguc Unluyurt, and Amol Deshpande