Alistair Sinclair, Professor
Contents:
Research interests /
Publications /
Current and former graduate students /
Contact information
About me
I am Kikuo Ogawa and Kaoru Ogawa Professor of Computer Science in the
Department
of EECS at UC Berkeley, and also Associate Director of the
Simons Institute for the Theory of Computing.
Research interests
 Design and analysis of algorithms, especially randomized ones
 Computational applications of stochastic processes and nonlinear
dynamical systems
 Monte Carlo methods and phase transitions in statistical physics
 Combinatorial optimization
Some recent (and not so recent) papers

Spatial mixing and approximation algorithms for graphs with bounded connective constant
 Alistair Sinclair, Piyush Srivastava and Yitong Yin.
Proceedings of IEEE FOCS 2013.

LeeYang theorems and the complexity of computing averages
 Alistair Sinclair and Piyush Srivastava.
To appear in Communications in Mathematical Physics.
Preliminary version appeared in Proceedings of ACM STOC 2013, pp. 625634.

Random lattice triangulations: Structure and algorithms
 Pietro Caputo, Fabio Martinelli, Alistair Sinclair and Alexandre Stauffer.
To appear in Annals of Applied Probability.
Preliminary version appeared in Proceedings of ACM STOC 2013, pp. 615624.

Approximation algorithms for twostate antiferromagnetic spin systems on bounded degree
graphs
 Alistair Sinclair, Piyush Srivastava and Marc Thurley.
Journal of Statistical Physics, published online, March 2014.
Preliminary version appeared in Proceedings of ACMSIAM SODA 2012, pp. 941953.

Almost settling the hardness of noncommutative determinant
 Steve Chien, Prahladh Harsha, Alistair Sinclair and Srikanth Srinivasan.
Proceedings of ACM STOC 2011, pp. 499508.

Mobile geometric graphs: Detection, coverage and percolation
 Yuval Peres, Alistair Sinclair, Perla Sousi and Alexandre Stauffer.
Probability Theory and Related Fields 156 (2013), pp. 273305.
Preliminary version appeared in Proceedings of ACMSIAM SODA 2011, pp. 412428.

Liftings of treestructured Markov chains
 Tom Hayes and Alistair Sinclair.
Proceedings of APPROX/RANDOM 2010, pp. 602616.

Delaying satisfiability for random 2SAT
 Alistair Sinclair and Dan Vilenchik.
Random Structures & Algorithms 43 (2013), pp. 251263.
Preliminary version appeared in Proceedings of APPROX/RANDOM 2010, pp. 710723.

Mixing time for the SolidonSolid model
 Fabio Martinelli and Alistair Sinclair.
Annals of Applied Probability 22 (2012), pp. 11361166.
Preliminary version appeared in Proceedings of ACM STOC 2009, pp. 571580.

SheraliAdams relaxations of the matching polytope
 Claire Mathieu and Alistair Sinclair.
Proceedings of ACM STOC 2009, pp. 293302.

Strong and Pareto price of anarchy in congestion games
 Steve Chien and Alistair Sinclair.
Proceedings of ICALP 2009, pp. 279291.

The extended ktree algorithm
 Lorenz Minder and Alistair Sinclair.
Journal of Cryptology 25 (2012), pp. 349382.
Preliminary version appeared in Proceedings of ACMSIAM SODA 2009, pp. 586595.

Convergence to approximate Nash equilibria in congestion games
 Steve Chien and Alistair Sinclair.
Games & Economic Behavior 71 (2011), pp. 315327.
Preliminary version appeared in Proceedings of ACMSIAM SODA 2007, pp. 169178.

Low distortion maps between point sets
 Claire Kenyon, Yuval Rabani and Alistair Sinclair.
SIAM Journal on Computing 39 (2009), pp.16171636.
Preliminary version in Proceedings of ACM STOC 2004, pp. 272280.

On the satisfiability threshold and clustering of solutions of random 3SAT formulas
 Elitza Maneva and Alistair Sinclair.
Theoretical Computer Science 407 (2008), pp. 259369.

Algebras with polynomial identities and computing the determinant
 Steve Chien and Alistair Sinclair.
Full version appeared in
SIAM Journal on Computing 37 (2007), pp. 252266.
Preliminary version appeared in Proceedings of IEEE FOCS 2004, pp. 352361.

A general lower bound for mixing of single site dynamics on graphs
 Tom Hayes and Alistair Sinclair.
Annals of Applied Probability 17 (2007), pp. 931952.
Preliminary version appeared in Proceedings of IEEE FOCS 2005, pp. 511520.

Fast mixing for independent sets, colorings and other models on trees
 Fabio Martinelli, Alistair Sinclair and Dror Weitz.
Slightly revised version appeared in
Random Structures & Algorithms 31 (2007), pp. 134172.
Extended abstract appeared in
Proceedings of ACMSIAM SODA 2004, pp. 449458.

Negative examples for sequential importance sampling of binary contingency tables
 Ivona Bezáková, Alistair Sinclair, Daniel Štefankovič and Eric Vigoda.
Algorithmica 64 (2012), pp. 606620.
Preliminary version in Proceedings of European Symposium on Algorithms (ESA), 2006,
pp. 136147.

Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs
 Assaf Naor, Yuval Rabani and Alistair Sinclair.
Journal of Functional Analysis 227 (2005), pp. 273303.

Shuffling by semirandom transpositions
 Elchanan Mossel, Yuval Peres and Alistair Sinclair.
Mathematics arXiv math.PR/0404438 (April 2004).
Conference version appeared in IEEE FOCS 2004, pp. 572581.

The Ising model on trees: Boundary conditions and mixing time
 Fabio Martinelli, Alistair Sinclair and Dror Weitz.
Technical Report UCB//CSD031256, UC Berkeley, July 2003.
(Extended abstract appeared in Proceedings of FOCS 2003.
Slightly modified version appeared in Communications in Mathematical
Physics 250 (2004), pp. 301334.)
 Embedding kOuterplanar Graphs into l_1
 Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich and Alistair Sinclair.
Proceedings of ACMSIAM SODA 2003, pp. 527536.
Full version appeared in SIAM Journal on Discrete Mathematics 20 (2006),
pp. 119136.
 Mixing in time and space for lattice spin systems:
a combinatorial view
 Martin Dyer, Alistair Sinclair, Eric Vigoda and Dror Weitz, February 2003.
Slightly revised version appeared in Random Structures & Algorithms 24 (2004), pp. 461479.
Preliminary version in Proceedings of RANDOM 2002, pp. 149163.
 Random walks on truncated cubes and sampling
01 knapsack solutions
 Ben Morris and Alistair Sinclair, July 2002. Slightly revised version appeared in
SIAM Journal on Computing 34 (2005), pp. 195226.
Preliminary version in IEEE FOCS 1999, pp. 230240.
 Finding points on curves over finite fields
 Joachim von zur Gathen, Igor Shparlinski and Alistair Sinclair.
SIAM Journal on Computing 32 (2003), pp. 14361448.
 Clifford algebras and approximating the
permanent
 Steve Chien, Lars Rasmussen and Alistair Sinclair, November 2002.
Slightly revised version
appeared in Journal of Computer & Systems Sciences 67 (2003), pp. 263290.
Preliminary version in ACM STOC 2002, pp. 222231.
 A polynomialtime approximation algorithm for the
permanent of a matrix with nonnegative entries
 Mark Jerrum, Alistair Sinclair and Eric Vigoda, ACM STOC 2001, pp. 712721.
Extended version available on ECCC, here;
revised version appeared in Journal of the ACM 51 (2004), pp. 671697.
 Cuts, trees and l_1embeddings of graphs
 Anupam Gupta, Ilan Newman, Yuri Rabinovich and Alistair Sinclair,
Combinatorica 24 (2004), pp. 233269. Preliminary version in IEEE FOCS 1999, pp. 399408.
 Local Divergence of Markov chains and the
analysis of iterative loadbalancing schemes
 Yuval Rabani, Alistair Sinclair and Rolf Wanka, Proceedings of IEEE FOCS 1998,
pp. 694703
 Spatial codes and the hardness of string
folding problems
 Ashwin Nayak, Alistair Sinclair and Uri Zwick, Proceedings of ACMSIAM SODA 1998,
pp. 639648
 Convergence rates for Monte Carlo experiments
 Alistair Sinclair, in "Numerical Methods for Polymeric Systems,"
S.G.Whittington ed., IMA Volumes in Mathematics & its Applications, 1997,
pp. 118
 The Markov chain Monte Carlo method:
an approach to approximate counting and integration
 Mark Jerrum and Alistair Sinclair, in "Approximation Algorithms for NPhard Problems," D.S.Hochbaum ed., PWS Publishing, Boston, 1996
 Biased random walks, Lyapunov functions, and stochastic analysis of Best Fit bin packing
 Claire Kenyon, Yuval Rabani and Alistair Sinclair, ACM/SIAM SODA 1996, pp. 351358
 Approximating the number of dimer
coverings of a lattice
 Claire Kenyon, Dana Randall and Alistair Sinclair, Journal of Statistical Physics 83 (1996), pp. 637659.
Preliminary version in ACM STOC 1993.
 Markov Chain Algorithms for Planar Lattice Structures
 Michael Luby, Dana Randall and Alistair Sinclair, IEEE FOCS 1995, pp. 150159
 A computational view of population genetics
 Yuval Rabani, Yuri Rabinovich and Alistair Sinclair, ACM STOC 1995, pp. 8392
 Testable Algorithms for SelfAvoiding Walks
 Dana Randall and Alistair Sinclair, ACM/SIAM SODA 1994
 Polynomialtime Approximation Algorithms for the
Ising Model
 Mark Jerrum and Alistair Sinclair, SIAM Journal on Computing 22 (1993), pp. 10871116
 Optimal Speedup of Las Vegas Algorithms
 Michael Luby, Alistair Sinclair and David Zuckerman, Information Processing Letters 47 (1993), pp. 173180
 Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
 Alistair Sinclair, Combinatorics, Probability and Computing 1 (1992), pp. 351370
 Quadratic Dynamical Systems
 Yuri Rabinovich, Alistair Sinclair and Avi Wigderson, FOCS 1992, pp. 304313
 When is a Graphical Sequence Stable?
 Mark Jerrum, Brendan McKay and Alistair Sinclair, Random Graphs, Vol. 2 (A. Frieze and T. Luczak, eds., Wiley, 1992, pp. 101115.
 Fast Uniform Generation of Regular Graphs
 Mark Jerrum and Alistair Sinclair, Theoretical Computer Science 73 (1990), pp. 91100
 Approximating the Permanent
 Mark Jerrum and Alistair Sinclair, SIAM Journal on Computing 18 (1989), pp. 11491178.
Preliminary version in ACM STOC 1988.
 Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains
 Mark Jerrum and Alistair Sinclair, Information & Computation 82 (1989), pp. 93133.
Current and former graduate students
Contact information
Prof. Alistair Sinclair
Computer Science Division
Soda Hall
University of California
Berkeley, CA 947201776
Phone: (510) 6438144
Fax: (510) 6425775
Email: sinclair ATSIGN cs DOT berkeley DOT edu