In the file maintenance problem, n integer items from the set {1,....,r} are to be stored in an array of size m>=n.

The general problem of proving limitations on what efficient algorithms can accomplish has been the subject of much research over the past four decades. In this talk, we consider the specific question of bounding the power of Boolean circuits.

Randomized rounding is a classic method to produce an integral 0/1 solution from a fractional one by interpreting the fractions as probabilities.

Markov chains are omnipresent. They are used as semantical backbone of Markovian queueing networks, stochastic Petri nets, stochastic process algebras, and calculi for systems biology.

We show that it is possible to encode any communication protocol between two parties so that the protocol succeeds even if a (1/4 − epsilon) fraction of all symbols transmitted by the parties are corrupted adversarially, at a cost of increasing th