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.
In research supported by the grant we studied problems related to chance and its manifestations in voting, high performance computing, and evolution. Which voting methods are robust? With our collaborators we showed that simple majority vote is the optimal voting method between two alternatives. We showed that it is the least prone to errors by voters or voting machines and it is the easiest to predict from a population sample. A different picture arises in voting among three or more alternatives. Here we showed that all voting methods are prone to what is called manipulation. This means that in all voting methods involving 3 or more candidates, voters should often take into account polls in order to decide who to vote for so their vote is not wasted. Using similar mathematical techniques to those used for voting, we analyzed questions coming from high performance computing. In particular, we showed that various computational tasks are impossible to achieve even if one is satisfied with very relaxed benchmarks. In a separate line of research we investigated how much we can infer about evolutionary history from current genetic diversity. We showed that for slowly mutating families of species, a lot of the history could be recovered. On the other hand, for quickly evolving families of species we showed that it is impossible to recover ancient history. For both regimes we developed optimal inference procedures. Our educational efforts included mentoring a number of graduate students, the development of two advanced graduate courses and the development of online materials for an undergraduate level course in probability.
