:' Alistair Sinclair (born 1960) is a

British British may refer to: Peoples, culture, and language * British people, nationals or natives of the United Kingdom, British Overseas Territories, and Crown Dependencies. ** Britishness, the British identity and common culture * British English ...

computer scientist and

computational theorist In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., ...

. 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 The University of Edinburgh ( sco, University o Edinburgh, gd, Oilthigh Dhùn Èideann; abbreviated as ''Edin.'' in post-nominals) is a public research university based in Edinburgh, Scotland. Granted a royal charter by King James VI in 15 ...

in 1988 under the supervision of

Mark Jerrum Mark Richard Jerrum (born 1955) is a British computer scientist and computational theorist. Jerrum received his Ph.D. in computer science 'On the complexity of evaluating multivariate polynomials' in 1981 from University of Edinburgh under the s ...

. He is professor at the Computer Science division at the

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant u ...

and has held faculty positions at University of Edinburgh and visiting positions at

DIMACS The Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) is a collaboration between Rutgers University, Princeton University, and the research firms AT&T, Bell Labs, Applied Communication Sciences, and NEC. It was founded in ...

and the

International Computer Science Institute The International Computer Science Institute (ICSI) is an independent, non-profit research organization located in Berkeley, California, United States. Since its founding in 1988, ICSI has maintained an affiliation agreement with the University ...

in Berkeley. Sinclair’s research interests include the design and analysis of

randomized algorithms A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...

, computational applications of stochastic processes and nonlinear dynamical systems,

Monte Carlo method Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be deter ...

s in

statistical physics Statistical physics is a branch of physics that evolved from a foundation of statistical mechanics, which uses methods of probability theory and statistics, and particularly the mathematical tools for dealing with large populations and approxi ...

and

combinatorial optimization Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...

. With his advisor

, Sinclair investigated the mixing behaviour of

Markov chain A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happen ...

s to construct

approximation algorithms In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solut ...

for counting problems such as the

computing the permanent In linear algebra, the computation of the permanent of a matrix is a problem that is thought to be more difficult than the computation of the determinant of a matrix despite the apparent similarity of the definitions. The permanent is defined sim ...

, 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 The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Intere ...

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 The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at e ...

in 2006.2006 Fulkerson Prize citation
Notices of the AMS, December 2006, volume 53, number 11

''Computational Complexity''. Retrieved 11 April 2017. Sinclair's initial forms part of the name of the

GNRS conjecture In theoretical computer science and metric geometry, the GNRS conjecture connects the theory of graph minors, the stretch factor of embeddings, and the approximation ratio of multi-commodity flow problems. It is named after Anupam Gupta, Ilan ...

on metric embeddings of minor-closed graph families.

References

British computer scientists Theoretical computer scientists Gödel Prize laureates Alumni of the University of Edinburgh Living people UC Berkeley College of Engineering faculty 1960 births Alumni of St John's College, Cambridge {{UK-compu-bio-stub