3 papers
cs.DS2024
Quickly Determining Who Won an Election
Lisa Hellerstein, Naifeng Liu, Kevin Schewior
This paper considers elections in which voters choose one candidate each, independently according to known probability distributions. A candidate receiving a strict majority (absol…
cs.DS2022
Two 6-approximation Algorithms for the Stochastic Score Classification Problem
Naifeng Liu
We study the arbitrary cost case of the unweighted Stochastic Score Classification (SSClass) problem. We show two constant approximation algorithms and both algorithms are 6-approx…
cs.DS2022
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…