A number of problems in computational complexity and pseudorandomness are being investigated, using new extensions of Lebesgue measure theory and the Baire category method as tools. These techniques, recently developed by the principal investigator, assign probabilistic and topological "sizes" to subsets of complexity classes. This approach, which has already revealed new, quantitative information about the structure of these classes, is being used to investigate: (1) relationships between uniform and nonuniform complexity, with particular emphasis on circuit-size and program-size complexities; (2) quantitative relationships between the "span" of (i.e., the set of problems efficiently reducible to) a problem and its complexity properties, including approximation, complexity cores, and hard instances; (3) theoretical aspects of pseudorandomness; and (4) the adequacy of pseudorandom sources for efficient randomized algorithms. The complexity-theoretic measure and category methods themselves are being refined, strengthened, and extended to a wider variety of classes.
