Computer Science Theory Seminar
Lisa Hellerstein
NYU
Minimizing the expected number of tests to evaluate a symmetric Boolean function
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.
Tuesday February 25, 2020 at 3:00 PM in 1325 SEO