Some applications of randomness in computational complexity

In this dissertation we consider two different notions of randomness and their applications to problems in complexity theory. In part one of the dissertation we consider Kolmogorov complexity, a way to formalize a measure of the randomness of a single finite string, something that cannot be done using the usual distributional definitions. We let R be the set of random strings under this measure and study what resource-bounded machines can compute using R as an oracle. We show the surprising result that under proper definitions we can in fact define well-formed complexity classes using this approach, and that perhaps it is possible to exactly characterize standard classes such as BPP and NEXP in this way. In part two of the dissertation we switch gears and consider the use of randomness as a tool in propositional proof complexity, a sub-area of complexity theory that addresses the NP vs. coNP problem. Here we consider the ability of various proof systems to efficiently refute randomly generated unsatisfiable 3-CNF and 3-XOR formulas. In particular, we show that certain restricted proof systems based on Ordered Binary Decision Diagrams requires exponential-size refutations of these formulas. We also outline a new general approach for proving proof complexity lower bounds using random 3-CNF formulas and demonstrate its use on treelike resolution, a weak proof system.Ph. D.Includes bibliographical referencesby Luke Friedma