The Voting algorithm is robust to various noise models
N.A. Aishwaryaprajna, Jonathan E. Rowe · Theoretical Computer Science · 2023
A simple Voting algorithm has been shown to be effective at solving the OneMax problem in the presence of high levels of posterior noise in our previous research. In this paper, we extend this analysis to several different noise models, and show that the Voting algorithm remains robust in all of them. We consider the prior noise model and the partial evaluation of randomly selected bits. The Voting algorithm has superior runtime bounds on these problems compared to other published algorithms. We also introduce a new variant of partial evaluation, and further consider the simple model when a comparison-based oracle produces incorrect results with a fixed probability.