Seminar by Lisa Hellerstein
TRIPODS Seminar
February 25, 2020
3:00 PM - 4:00 PM
Minimizing the expected number of tests to evaluate a symmetric Boolean function
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.
Date posted
Feb 18, 2020
Date updated
Feb 24, 2020
Speakers
Lisa Hellerstein | Professor of Computer Science and Engineering | New York University
Lisa Hellerstein is the TRIPODS institute's first long-term visitor.