Computer Science Seminar
Lisa Hellerstein
NYU Tandon School of Engineering
On the Submodular Goal Value of Boolean Functions
Abstract: Submodular Goal Value is a complexity measure for Boolean functions.
The measure was first defined in our earlier work (with Deshpande et al.),
motivated by applications to
algorithmic problems in Boolean function evaluation, and by
problems in Boolean decision tree complexity.
The measure turns out to be of intrinsic interest as well.
In this talk, after providing definitions and briefly reviewing motivating applications,
we will discuss our recent work exploring properties
of the Submodular Goal Value measure. We give bounds on the Submodular
Goal Value of both general and specific classes of Boolean functions,
establish some relations to existing complexity measures for Boolean functions,
and present open questions.
This is joint work with Eric Bach, Jeremie Dusart, and Devorah Kletenik
Friday February 17, 2017 at 12:00 PM in SEO 612