Starting with one-way functions in which redundancy in the preimage is absolutely minimal, i.e. one-way functions that are one-to-one, we provide the first characterization of the existence of one-way permutations by a complexity class separation hypothesis, namely $\P \neq \up \inter \coup$.
Next, we study a type of one-way function that provably can never be one-to-one. Strong, total, associative, one-way functions are two-argument, one-way functions that are hard to invert, even if one of their arguments is known. Such special, one-way functions were used to study certain secret-key agreement and digital signature protocols that crucially depend on the properties of such special, one-way functions. We study techniques for creating such functions whose amount of preimage redundancy (as a function of the length of the corresponding image element) is minimized. We show that, if $\p \neq \up$, then such special one-way functions exist and that we can go from total, associative polynomial-time computable functions to strong, total, associative, one-way functions at no cost in increased preimage redundancy.
We examine the complexity of counting the sizes of intervals over orders having certain, natural, computational and redundancy properties. We show that having redundancy in the adjacency relations of the order adds almost nothing to the computational complexity of computing such intervals.
Finally, we look at a problem in routing on ad-hoc networks whose solution exploits redundancy. We provide a theoretical framework for analyzing the behavior of a variety of table-less routing schemes. We show that such schemes work well when there is edundancy between the network distance and the objective functions used to make routing decisions.