Lisa Hellerstein : Minimizing the expected number of tests to evaluate a symmetric Boolean function

Posted by Gyorgy Turan , part of the Computer Science Theory Seminar.

At

Feb. 25, 2020, 3 p.m.

In

1325 SEO

Abstract

A Boolean function f(x1, ..., xn) is symmetric if its value is determined by the number of its input variables that are set to 1. Given a symmetric Boolean function f(x1,...,xn), suppose we want to determine the value of f on an initially unknown assignment to its inputs xi. For each xi, we are given pi, the probability that xi=1. The xi's are independent. The only way to find the value of xi in the assignment is to "test" xi. The problem is to determine the order in which to perform the tests, so as to minimize the expected number of tests. We present approximation algorithms for versions of this problem and discuss open questions.