| Redundancy is a basic property of many computational settings. This thesis presents techniques for eliminating redundancy in some cases and exploiting it in others.; We study one-way functions, i.e., functions that are easy to compute but hard to invert. Such functions have been studied as cryptographic primitives. Since it remains an open question whether one-way functions exist, we study the question of their existence in relation to a variety of complexity-theoretic hypotheses.; 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 ≠ UP ∩ coUP. This shows that (partial) one-way permutations exist if and only if (total) one-way permutations exist.; 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 have been 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 ≠ 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.; Continuing our study of eliminating redundancy in functions, 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 such orders adds almost nothing to the computational complexity of computing such intervals.; Finally, we look at a problem related to routing over 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 redundancy between the network distance and the objective functions used locally at each node to make routing decisions. |
