Alistair Sinclair

Last updated

Alistair Sinclair (born 1960) 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. [1] He is professor at the Computer Science division at the University of California, 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 methods in statistical physics and combinatorial optimization. With his advisor Mark Jerrum, Sinclair investigated the mixing behaviour of Markov chains 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. [2] 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. [3]

Sinclair's initial forms part of the name of the GNRS conjecture on metric embeddings of minor-closed graph families.

Related Research Articles

Discrete mathematics Study of discrete mathematical structures

Discrete mathematics is the study of mathematical structures that can be considered "discrete" rather than "continuous". Objects studied in discrete mathematics include integers, graphs, and statements in logic. By contrast, discrete mathematics excludes topics in "continuous mathematics" such as real numbers, calculus or Euclidean geometry. Discrete objects can often be enumerated by integers; more formally, discrete mathematics has been characterized as the branch of mathematics dealing with countable sets. However, there is no exact definition of the term "discrete mathematics".

Richard M. Karp American mathematician

Richard Manning Karp is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008.

Theoretical computer science Subfield of computer science and mathematics

Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.

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 Interest Group on Algorithms and Computational Theory. The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.

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 each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.

Éva Tardos Hungarian mathematician

Éva Tardos is a Hungarian mathematician and the Jacob Gould Schurman Professor of Computer Science at Cornell University.

Vijay Vazirani

Vijay Virkumar Vazirani is an Indian American distinguished professor of computer science in the Donald Bren School of Information and Computer Sciences at the University of California, Irvine.

Christos Papadimitriou American computer scientist

Christos Harilaos Papadimitriou is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia University.

Umesh Virkumar Vazirani is an Indian-American academic who is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the University of California, Berkeley, and the director of the Berkeley Quantum Computation Center. His research interests lie primarily in quantum computing. He is also a co-author of a textbook on algorithms.

Rajeev Motwani Indian computer scientist (1962–2009)

Rajeev Motwani was an Indian American professor of Computer Science at Stanford University whose research focused on theoretical computer science. He was an early advisor and supporter of companies including Google and PayPal, and a special advisor to Sequoia Capital. He was a winner of the Gödel Prize in 2001.

Michael Stewart Paterson, is a British computer scientist, who was the director of the Centre for Discrete Mathematics and its Applications (DIMAP) at the University of Warwick until 2007, and chair of the department of computer science in 2005.

Mark Richard Jerrum is a British computer scientist and computational theorist.

In the analysis of algorithms, several authors have studied the computation of the volume of high-dimensional convex bodies, a problem that can also be used to model many other problems in combinatorial enumeration. Often these works use a black box model of computation in which the input is given by a subroutine for testing whether a point is inside or outside of the convex body, rather than by an explicit listing of the vertices or faces of a convex polytope. It is known that, in this model, no deterministic algorithm can achieve an accurate approximation, and even for an explicit listing of faces or vertices the problem is #P-hard. However, a joint work by Martin Dyer, Alan M. Frieze and Ravindran Kannan provided a randomized polynomial time approximation scheme for the problem, providing a sharp contrast between the capabilities of randomized and deterministic algorithms.

Joseph S. B. Mitchell American computer scientist and mathematician

Joseph S. B. Mitchell is an American computer scientist and mathematician. He is Distinguished Professor and Department Chair of Applied Mathematics and Statistics and Research Professor of Computer Science at Stony Brook University.

Martin Edward Dyer is a professor in the School of Computing at the University of Leeds, Leeds, England. He graduated from the University of Leeds in 1967, obtained his MSc from Imperial College London in 1968 and his PhD from the University of Leeds in 1979. His research interests lie in theoretical computer science, discrete optimization and combinatorics. Currently, he focuses on the complexity of counting and the efficiency of Markov chain algorithms for approximate counting.

Noam Nisan Israeli computer scientist

Noam Nisan is an Israeli computer scientist, a professor of computer science at the Hebrew University of Jerusalem. He is known for his research in computational complexity theory and algorithmic game theory.

Leslie Ann Goldberg is a professor of computer science at the University of Oxford and a Fellow of St Edmund Hall, Oxford. Her research concerns the design and analysis of algorithms for random sampling and approximate combinatorial enumeration.

Satish Rao is an American computer scientist who is a professor of computer science at the University of California, Berkeley.

Jin-Yi Cai is a Chinese American mathematician and computer scientist. He is a professor of computer science, and also the Steenbock Professor of Mathematical Sciences at the University of Wisconsin–Madison. His research is in theoretical computer science, especially computational complexity theory. In recent years he has concentrated on the classification of computational counting problems, especially counting graph homomorphisms, counting constraint satisfaction problems, and Holant problems as related to holographic algorithms.

References

  1. ↑ John, Sinclair, Alistair (1988). "Randomised algorithms for counting and generating combinatorial structures". hdl:1842/11392.{{cite journal}}: Cite journal requires |journal= (help)
  2. ↑ "1996 Gödel Prize citation". Archived from the original on 2 April 2015. Retrieved 14 December 2011.
  3. ↑ 2006 Fulkerson Prize citation, Notices of the AMS, December 2006, volume 53, number 11
    - "Fulkerson Prize" Computational Complexity. Retrieved 11 April 2017.


GodfreyKneller-IsaacNewton-1689.jpg

This article about a British scientist is a stub. You can help Wikipedia by expanding it.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.