CAREER: Applications of Probability Theory in Computer Science, Social Choice, Biology and Statistics

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

The investigator studies the robustness of functions to stochastic perturbation of their inputs in terms of the influences of each variable on the function. The investigator is interested in particular in problems arising in the theory of social choice in economy and in hardness of approximation in theoretical computer science and their relation to classical and Gaussian isoperimetric problems. The investigator further studies properties of Gibbs measures on trees in relation to algorithmic inference problems on Markov random fields. In particular, provably efficient algorithms for phylogenetic inference are developed. In the first topic the investigator studies questions like: ``How do we design a reliable voting scheme? What is the effect of error in voting machines on the outcome of a vote?''. The same mathematical questions are also an important ingredient in understanding theoretical questions arising in high-performance computing, in particular the existence of efficient algorithms that approximately solve ``hard'' problems. In the second topic, the investigator is motivated by questions on ancestral relationship that are central in modern biological, medical and genealogical research, and in problems arising in high-dimensional statistical inference which play an important role in expert systems and data-mining.