Alistair Sinclair
Encyclopedia
Alistair Sinclair is a British
computer scientist and computational theorist.
Sinclair received his B.A. in Mathematics from St. John’s College, Cambridge in 1979, and his Ph.D. in Computer Science from the University of Edinburgh
in 1988 under the supervision of Mark Jerrum
. He is professor at the Computer Science division at UC Berkeley and has held faculty positions at University of Edinburgh and visiting positions at DIMACS
and the International Computer Science Institute
in Berkeley.
Sinclair’s research interests include the design and analysis of randomized algorithms, computational applications of stochastic processes and nonlinear dynamical systems, Monte Carlo method
s in Statistical Physics
,
and combinatorial optimization
. With his advisor Mark Jerrum
, Sinclair investigated the mixing behaviour of Markov chain
s to construct approximation algorithms for counting problems such as the computing the permanent
, with applications in diverse fields such as matching algorithms, geometric algorithms, mathematical programming, statistics, physics-inspired applications, and dynamical systems. This work has been highly influential in theoretical computer science and was recognised with the Gödel Prize
in 1996. A refinement of these methods led to a fully polynomial time randomised approximation algorithm for computing the permanent, for which Sinclair and his co-authors received the Fulkerson Prize
in 2006.
Great Britain
Great Britain or Britain is an island situated to the northwest of Continental Europe. It is the ninth largest island in the world, and the largest European island, as well as the largest of the British Isles...
computer scientist and computational theorist.
Sinclair received his B.A. in Mathematics from St. John’s College, Cambridge in 1979, and his Ph.D. in Computer Science from the University of Edinburgh
University of Edinburgh
The University of Edinburgh, founded in 1583, is a public research university located in Edinburgh, the capital of Scotland, and a UNESCO World Heritage Site. The university is deeply embedded in the fabric of the city, with many of the buildings in the historic Old Town belonging to the university...
in 1988 under the supervision of Mark Jerrum
Mark Jerrum
Mark Richard Jerrum is a British computer scientist and computational theorist.Jerrum received his Ph.D. in computer science in 1981 from University of Edinburgh under the supervision of Leslie Valiant...
. He is professor at the Computer Science division at UC Berkeley and has held faculty positions at University of Edinburgh and visiting positions at DIMACS
DIMACS
The Center for Discrete Mathematics and Theoretical Computer Science is a collaboration between Rutgers University, Princeton University, and the research firms AT&T, Bell Labs, Telcordia, and NEC. It was founded in 1989 with money from the National Science Foundation...
and the International Computer Science Institute
International Computer Science Institute
The International Computer Science Institute is an independent, non-profit research organization located in Berkeley, California, USA. Since its founding in 1988, ICSI has maintained an affiliation with the University of California, Berkeley, where several of its members hold faculty appointments...
in Berkeley.
Sinclair’s research interests include the design and analysis of randomized algorithms, computational applications of stochastic processes and nonlinear dynamical systems, Monte Carlo method
Monte Carlo method
Monte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in computer simulations of physical and mathematical systems...
s in Statistical Physics
Statistical physics
Statistical physics is the branch of physics that uses methods of probability theory and statistics, and particularly the mathematical tools for dealing with large populations and approximations, in solving physical problems. It can describe a wide variety of fields with an inherently stochastic...
,
and combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
. With his advisor Mark Jerrum
Mark Jerrum
Mark Richard Jerrum is a British computer scientist and computational theorist.Jerrum received his Ph.D. in computer science in 1981 from University of Edinburgh under the supervision of Leslie Valiant...
, Sinclair investigated the mixing behaviour of Markov chain
Markov chain
A Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...
s to construct approximation algorithms for counting problems such as the computing the permanent
Computing the permanent
In mathematics, the computation of the permanent of a matrix is a problem that is believed to be more complex than the computation of the determinant of a matrix despite the apparent similarity of the definitions....
, with applications in diverse fields such as matching algorithms, geometric algorithms, mathematical programming, statistics, physics-inspired applications, and dynamical systems. This work has been highly influential in theoretical computer science and was recognised with the Gödel Prize
Gödel Prize
The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory .The...
in 1996. A refinement of these methods led to a fully polynomial time randomised approximation algorithm for computing the permanent, for which Sinclair and his co-authors received the Fulkerson Prize
Fulkerson Prize
The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Programming Society and the American Mathematical Society . Up to three awards of $1500 each are presented at each International Symposium of the MPS...
in 2006.