The principle of deferred decisions

Lefteris Kirousis
University of Patras, Greece

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.

(Joint work with Alexis C. Kaporis and Yannis C. Stamatiou)

Presentation (PDF File)

Back to Phase Transitions And Algorithmic Complexity