5 citations · 17 across the 9 of their papers we have counts for
10 papers
Adaptivity Gaps for the Stochastic Boolean Function Evaluation Problem
Lisa Hellerstein, Devorah Kletenik, Naifeng Liu +1
We consider the Stochastic Boolean Function Evaluation (SBFE) problem where the task is to efficiently evaluate a known Boolean function on an unknown bit string of length…
The Stochastic Boolean Function Evaluation Problem for Symmetric Boolean Functions
Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein +1
We give two approximation algorithms solving the Stochastic Boolean Function Evaluation (SBFE) problem for symmetric Boolean functions. The first is an -approximation al…
A Tight Bound for Stochastic Submodular Cover
Lisa Hellerstein, Devorah Kletenik, Srinivasan Parthasarathy
We show that the Adaptive Greedy algorithm of Golovin and Krause (2011) achieves an approximation bound of for Stochastic Submodular Cover: here is the "goal va…
The Stochastic Score Classification Problem
Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein +1
Consider the following Stochastic Score Classification Problem. A doctor is assessing a patient's risk of developing a certain disease, and can perform tests on the patient. Ea…
Submodular Goal Value of Boolean Functions
Eric Bach, Jeremie Dusart, Lisa Hellerstein +1
Recently, Deshpande et al. introduced a new measure of the complexity of a Boolean function. We call this measure the "goal value" of the function. The goal value of is defined…
Scenario Submodular Cover
Nathaniel Grammel, Lisa Hellerstein, Devorah Kletenik +1
Many problems in Machine Learning can be modeled as submodular optimization problems. Recent work has focused on stochastic or adaptive versions of these problems. We consider the…