Randomization and probabilistic techniques have played a vital role in theoretical computer science over the last decade. This research addresses four areas; (1) the analysis of mixing rates of Markov chains to design efficient randomized algorithms for approximate counting problems -- including the classical problem of estimating the permanent of a matrix, (2) further applications of recently discovered probabilistically checkable proof systems to prove that certain approximation problems are computationally hard, in particular, the problem of approximating the expansion of a graph, as well as approximate counting problems, (3) the formulation of a generalization of Occam's razor for the identification of probabilistic hypotheses, and (4) the study of the computational power of computing devices based on quantum physics.
