ALCOMFT-TR-02-75

Alexis Kaporis, Lefteris Kirousis and Yannis Stamatiou
How to prove conditional randomness using the Principle of Deferred Decisions
Patras. Work package 4. May 2002.

Abstract: We propose a methodology to determine the conditional that should be put on a random object so that its randomness is retained when we run a given algorithm on it. The methodology is based on the Principle of Deferred Decisions. The basic idea is to store the information about the object in ``small pieces" in separate registers. The contents of the registers pertaining to the conditional are exposed, while the others are unexposed. Having separate registers for different types of information prevents exposing information that need not be exposed. We use this methodology to prove various randomness invariance results, one of which answers an open question.

Postscript file: ALCOMFT-TR-02-75.ps.gz (60 kb).