Alistair Sinclair

Alistair Sinclair's AcademicInfluence.com Rankings

Alistair Sinclair

Computer Science

#471

World Rank

#489

Historical Rank

Database

#6843

World Rank

#7082

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Alistair Sinclair's Degrees

PhD Computer Science University of California, Berkeley

Similar Degrees You Can Earn

Best Online PhD of Computer Science (Doctorates) 2025

Why Is Alistair Sinclair Influential?

(Suggest an Edit or Addition)

According to Wikipedia, 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 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.

(See a Problem?)

Alistair Sinclair's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Approximating the Permanent (1989) (821)
Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains (1987) (794)
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries (2004) (694)
Optimal speedup of Las Vegas algorithms (1993) (556)
Polynomial-Time Approximation Algorithms for the Ising Model (1993) (553)
The Markov chain Monte Carlo method: an approach to approximate counting and integration (1996) (541)
Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow (1992) (490)
Algorithms for Random Generation and Counting: A Markov Chain Approach (1993) (477)
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries (2001) (269)
Convergence to approximate Nash equilibria in congestion games (2007) (246)
Conductance and the rapid mixing property for Markov chains: the approximation of permanent resolved (1988) (218)
Markov chain algorithms for planar lattice structures (1995) (210)
Cuts, Trees and ℓ1-Embeddings of Graphs* (1999) (171)
Local divergence of Markov chains and the analysis of iterative load-balancing schemes (1998) (151)
Fast mixing for independent sets, colorings, and other models on trees (2004) (126)
Approximation Algorithms for Two-State Anti-Ferromagnetic Spin Systems on Bounded Degree Graphs (2011) (122)
Fast Uniform Generation of Regular Graphs (1990) (119)
Mixing in time and space for lattice spin systems: A combinatorial view (2002) (105)
A computational view of population genetics (1995) (102)
Mobile geometric graphs: detection, coverage and percolation (2010) (102)
Improved Bounds for Mixing Rates of Marked Chains and Multicommodity Flow (1992) (102)
A general lower bound for mixing of single-site dynamics on graphs (2005) (93)
Random walks on truncated cubes and sampling 0-1 knapsack solutions (1999) (89)
Quadratic dynamical systems (1992) (79)
Glauber Dynamics on Trees: Boundary Conditions and Mixing Time (2003) (73)
The Extended k-tree Algorithm (2009) (65)
Embedding k-outerplanar graphs into ℓ1 (2003) (65)
Spatial mixing and the connective constant: optimal bounds (2014) (58)
Approximating the number of monomer-dimer coverings of a lattice (1996) (58)
Low distortion maps between point sets (2004) (57)
The Ising Partition Function: Zeros and Deterministic Approximation (2017) (54)
Sherali-adams relaxations of the matching polytope (2009) (49)
The Ising model on trees: boundary conditions and mixing time (2003) (45)
Clifford algebras and approximating the permanent (2002) (44)
Mixing in time and space for discrete spin systems (2004) (43)
Negative Examples for Sequential Importance Sampling of Binary Contingency Tables (2006) (42)
Randomised algorithms for counting and generating combinatorial structures (1988) (40)
Spatial codes and the hardness of string folding problems (1998) (36)
Spatial Mixing and Approximation Algorithms for Graphs with Bounded Connective Constant (2013) (35)
Shuffling by semi-random transpositions (2004) (35)
Dynamics for the Mean-field Random-cluster Model (2014) (34)
Strong and Pareto Price of Anarchy in Congestion Games (2009) (34)
Biased random walks, Lyapunov functions, and stochastic analysis of best fit bin packing (1996) (32)
Random lattice triangulations: structure and algorithms (2012) (30)
Random-cluster dynamics in Z 2 (2016) (30)
Conductance and the Rapid Mixing Property for Markov Chains: the Approximation of the Permanent Resolved (Preliminary Version) (1988) (30)
Polynomial-Time Approximation Algorithms for Ising Model (Extended Abstract) (1990) (29)
Fisher zeros and correlation decay in the Ising model (2018) (28)
Algebras with polynomial identities and computing the determinant (2004) (28)
Beyond the Lovász Local Lemma: Point to Set Correlations and Their Algorithmic Applications (2018) (27)
On the satisfiability threshold and clustering of solutions of random 3-SAT formulas (2007) (25)
Markov Chain Algorithms for Planar Lattice Structures (Extended Abstract). (1995) (25)
A Deterministic Algorithm for Counting Colorings with 2-Delta Colors (2019) (23)
Self-testing algorithms for self-avoiding walks (2000) (22)
A deterministic algorithm for counting colorings with 2Δ colors (2019) (21)
Topics in black-box combinatorial optimization (1996) (21)
Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs (2005) (20)
Mixing time for the solid-on-solid model (2009) (19)
Lee–Yang Theorems and the Complexity of Computing Averages (2012) (19)
Finding points on curves over finite fields (1995) (16)
Dynamics of Lattice Triangulations on Thin Rectangles (2015) (15)
Optimal Speedup of Las Vegas Algorithms y (2019) (15)
Almost settling the hardness of noncommutative determinant (2011) (15)
Testable algorithms for self-avoiding walks (1994) (15)
The Equilibrium Genetic Algorithm and the Role of Crossover (1993) (14)
Spatial mixing and nonlocal Markov chains (2017) (14)
Delaying satisfiability for random 2SAT (2010) (14)
Convergence Rates for Monte Carlo Experiments (1998) (13)
Quadratic Dynamical Systems (Preliminary Version) (1992) (12)
Matchings in lattice graphs (1993) (12)
Approximation Algorithms for Two-State Anti-Ferromagnetic Spin Systems on Bounded Degree Graphs (2014) (12)
Analysis of a Classical Matrix Preconditioning Algorithm (2015) (11)
Embeddings of finite metrics (2000) (11)
Mobile Geometric Graphs, and Detection and Communication Problems in Mobile Wireless Networks (2010) (11)
The extendedk-tree algorithm (2009) (11)
Random-cluster dynamics in $${{\mathrm{\mathbb {Z}}}}^2$$Z2 (2017) (11)
Liftings of Tree-Structured Markov Chains - (Extended Abstract) (2010) (10)
Entropy decay in the Swendsen-Wang dynamics (2020) (9)
Entropy decay in the Swendsen–Wang dynamics on ℤd (2021) (8)
Entropy decay in the Swendsen–Wang dynamics on Zd (2022) (8)
Sampling from gibbs distributions (1999) (7)
Spatial mixing and the connective constant: optimal bounds (2016) (7)
Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions (2019) (6)
Low-temperature Ising dynamics with random initializations (2021) (6)
Random walks in convex sets (2000) (6)
A Computational View of Population Genetics ( preliminary version ) (1995) (6)
Entropy production in nonlinear recombination models (2016) (5)
Symbolic Integration and the Complexity of Computing Averages (2015) (5)
Efficiently list‐edge coloring multigraphs asymptotically optimally (2018) (4)
A Markov Chain Monte Carlo Method for Derivative Pricing and Risk Assessment (2005) (4)
The Critical Mean-field Chayes-Machta Dynamics (2021) (4)
The Computational Worldview and the Sciences : a Report on Two Workshops (2007) (4)
Markov chains and rapid mixing (1993) (4)
A New Perspective on Stochastic Local Search and the Lovasz Local Lemma (2018) (4)
Belief propagation algorithms for constraint satisfaction problems (2006) (4)
On approximating the permanent and other #p-complete problems (1998) (2)
Lee–Yang Theorems and the Complexity of Computing Averages (2014) (2)
Spatial mixing and the random-cluster dynamics on lattices (2022) (2)
Analysis of a Classical Matrix Preconditioning Algorithm (2015) (2)
The failure of Thomas Reid's attack on David Hume (1995) (2)
Negative Examples for Sequential Importance Sampling of Binary Contingency Tables (2011) (1)
The Answers Lie Within Us: Towards a Science of the Human Spirit (1998) (1)
The Ising Partition Function: Zeros and Deterministic Approximation (2018) (1)
What is philosophy (2008) (1)
The Extended k-tree Algorithm (2011) (1)
On determinant-based algorithms for counting perfect matchings in graphs (2003) (1)
CS 271 Randomness & Computation Fall 2011 Lecture 14 : October 11 (2011) (0)
8.1 Continuation of Volume Estimation (2009) (0)
Modelling Ge- Netic Algorithms with Markov Chains. In (1994) (0)
Lecture 1: August 25th 1.1 Introduction 1.1.1 Model of Computation (2011) (0)
Lecture 4: September 15 4.1 Recapitulation (2009) (0)
Session details: Session 9B (2005) (0)
Lecture 8: October 1 (0)
0.1 Multicommodity Flow (2009) (0)
Lecture 1: August 27 1.1 the Markov Chain Monte Carlo Paradigm 1.2 Applications 1.2.1 Combinatorics (2009) (0)
Real-time adjustment of the animal ration using NIRS (2014) (0)
Quantum Information Processing (2004) (0)
The Algorithmic Lovász Local Lemma (2018) (0)
The Middle Way versus Extremism (2020) (0)
1 The Lovász Local Lemma (2011) (0)
CS 70 Discrete Mathematics and Probability Theory Fall 2018 (2018) (0)
Two Killer Applications: Hashing and Load Balancing (2016) (0)
1 The Algorithmic Lovász Local Lemma (2022) (0)
CS 271 Randomness & Computation Fall 2011 Lecture 20 : November 1 (2011) (0)
55 : 2 Fisher Zeros and Correlation Decay in the Ising Model 1 (2018) (0)
5.1 Unbalancing Lights (2011) (0)
THE NEED TO COMPLETE THE SECULARIZATION OF SOCIETY (2013) (0)
Lecturer: Alistair Sinclair (2011) (0)
9.1 Coloring Random Graphs (continued) (2011) (0)
5.1 the Power of Two Choices (2011) (0)
WORLD WAR ONE AND THE LOSS OF THE HUMANIST CONSENSUS (2013) (0)
WHAT TO DO ABOUT RELIGION: A PLAN OF ACTION (2013) (0)
7.1 Volume of a Convex Body 17.2 Mixing Time (2009) (0)
1 Pairwise independent random variables Definition (2020) (0)
Disclaimer: These notes have not been subjected to the usual scrutiny reserved for formal publications. They may be distributed outside this class only with the permission of the Instructor. (2011) (0)
Lecture 15: October 22 15.1 Matchings in a Graph (2007) (0)
Concentration Inequalities and the Laws of Large Numbers (2018) (0)
Spatial Mixing and Systematic Scan Markov chains (2016) (0)
1 A deterministic algorithm for primality testing (2020) (0)
Quadratic Dynamical Systems ( Preliminary Version ) y (2019) (0)
1 A randomized algorithm for primality testing (2018) (0)
CS294-2 Markov Chain Monte Carlo: Foundations Applications Fall 2002 (2007) (0)
Spanning Trees : The Matrix Tree Theorem (2020) (0)
Henry Ford: The Visionary Humanist (2013) (0)
Random Walks on Undirected Graphs (2011) (0)
Mobile geometric graphs: detection, coverage and percolation (2012) (0)
CS 294 Markov Chain Monte Carlo : Foundations & Applications Fall 2009 Lecture 6 : September 22 (2009) (0)
Lecture 2: September 8 2.1 Markov Chains (2009) (0)
Lecture 13: Oct 20 (2009) (0)
CS 271 Randomness & Computation Fall 2011 Lecture 9 : September 27 (2011) (0)
9.1 Independent Sets (continuation) (2009) (0)
System commands (1983) (0)
Submitted to the Annals of Applied Probability RANDOM LATTICE TRIANGULATIONS : STRUCTURE AND ALGORITHMS By (2014) (0)
Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques (1999) (0)
6.1 on the Components of a Random Graph (2011) (0)
Fingerprints , Polynomials , and Pattern Matching Notes by Alistair Sinclair 1 Example 1 : Checking Matrix Multiplication (2012) (0)
Entropy decay in the Swendsen-Wang dynamics on ${\mathbb Z}^d$ (2020) (0)
Glauber Dynamics for the 2-d Ising model Recall the fundamental result (2009) (0)
CS 294 Markov Chain Monte Carlo : Foundations & Applications Fall 2009 Lecture 14 : October 22 (2009) (0)
Part 1 : Required Problems 1 Random Variables Warm-Up (2019) (0)
CS 294 Partition Functions Fall 2020 (2020) (0)
DUALISM AND HUMANISM (2013) (0)
CS271 Randomness & Computation Fall 2011 (2011) (0)
6.1 Existence of Monotone Circuits for the Majority Function (2011) (0)
The emergence of philosophical inquiry in 18th century Scotland (1998) (0)
APPROXIMATING THE PERMANENT * MARK JERRUM ? AND (0)

This paper list is powered by the following services:

Other Resources About Alistair Sinclair

What Schools Are Affiliated With Alistair Sinclair?

Alistair Sinclair is affiliated with the following schools:

Alistair Sinclair's Academic­Influence.com Rankings