Deterministically Simulating Barely Random Algorithms in the Random-Order Arrival Model

Allan Borodin, Christodoulos Karavasilis, David Zhang

Interest in the random-order model (ROM) leads us to initiate a study of utilizing random-order arrivals to extract random bits with the goal of derandomizing algorithms. Besides p…