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. From 2012 to 2017 I was Founding 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
- Low-temperature Ising dynamics with random initializations
- Reza Gheissari and Alistair Sinclair.
To appear in Annals of Applied Probability. Preliminary version appeared in
Proceedings of ACM STOC, 2022.
[arXiv]
-
The critical mean-field Chayes-Machta dynamics
- Antonio Blanca, Alistair Sinclair and Xusheng Zhang.
Combinatorics, Probability and Computing, published online, May 2022. Prelminary version
appeared in Proceedings of RANDOM 2021.
[arXiv]
-
Entropy decay in the Swendsen-Wang dynamics on Z^d
- Antonio Blanca, Pietro Caputo, Daniel Parisi, Alistair Sinclair and Eric Vigoda.
Annals of Applied Probability 32 (2022), pp. 1018-1057.
Preliminary version in Proceedings of ACM STOC 2021, pp. 1551-1564.
[arXiv]
-
Correlation decay and partition function zeros: Algorithms and phase transitions
- Jingcheng Liu, Alistair Sinclair and Piyush Srivastava.
SIAM Journal on Computing, Invited Special Issue for IEEE FOCS 2019.
[Substantially modified and expanded version of the FOCS version below.]
[arXiv]
-
A deterministic algorithm for counting colorings with 2Δ colors
- Jingcheng Liu, Alistair Sinclair and Piyush Srivastava.
Proceedings of IEEE FOCS 2019, pp. 1380-1404>.
[arXiv]
-
Efficiently list-edge coloring multigraphs asymptotically optimally
- Fotis Iliopoulos and Alistair Sinclair.
Random Structures & Algorithms 61 (2022), pp. 724-753. Preliminary version
appeared in Proceedings of ACM/SIAM SODA 2020, pp. 2319-2336.
[arXiv]
-
Beyond the Lovasz Local Lemma: Point to set correlations and their algorithmic applications
- Dimitris Achlioptas, Fotis Iliopoulos and Alistair Sinclair.
Proceedings of IEEE FOCS 2019, pp. 725-744.
[arXiv]
-
Fisher zeros and correlation decay in the Ising model
- Jingcheng Liu, Alistair Sinclair and Piyush Srivastava.
Journal of Mathematical Physics 60 (2019).
Extended abstract appeared in Proceedings of ITCS 2019.
[arXiv]
-
The Ising partition function: zeros and deterministic approximation
- Jingcheng Liu, Alistair Sinclair and Piyush Srivastava.
Journal of Statistical Physics 174 (2019), pp. 287-315.
Preliminary version appeared in Proceedings of IEEE FOCS 2017.
[arXiv]
-
Spatial mixing and non-local Markov chains
- Antonio Blanca, Pietro Caputo, Alistair Sinclair and Eric Vigoda.
Random Structures and Algorithms 55 (2019), pp. 584-614.
Preliminary version appeared in Proceedings of ACM-SIAM SODA 2018.
[arXiv]
-
Entropy production in nonlinear recombination models
- Pietro Caputo and Alistair Sinclair.
Bernoulli 24 (2018), pp. 3246-3282.
[arXiv]
-
Analysis of a classical matrix preconditioning algorithm
- Leonard Schulman and Alistair Sinclair.
Journal of the ACM 64 (2017), article #9.
Preliminary version appeared in Proceedings of ACM STOC 2015, pp. 831-840.
[arXiv]
-
Dynamics of lattice triangulations on thin rectangles
- Pietro Caputo, Fabio Martinelli, Alistair Sinclair and Alexandre Stauffer.
Electronic Journal of Probability 21 #29 (2016).
-
Random-cluster dynamics in Z^2
- Antonio Blanca and Alistair Sinclair.
Probability Theory and Related Fields 168 (2017), pp. 821-847.
Preliminary version appeared in Proceedings of ACM-SIAM SODA 2016, pp. 498-513.
[arXiv]
-
Spatial mixing and the connective constant: Optimal bounds
- Alistair Sinclair, Piyush Srivastava, Daniel Stefankovic and Yitong Yin.
Probability Theory and Related Fields 168 (2017), pp. 153-197.
Preliminary version appeared in Proceedings of ACM-SIAM SODA 2015, pp. 1549-1563.
[arXiv]
-
Symbolic integration and the complexity of computing averages
- Leonard Schulman, Alistair Sinclair and Piyush Srivastava.
Proceedings of IEEE FOCS 2015, pp. 1231-1245.
-
Dynamics for the mean-field random-cluster model
- Antonio Blanca and Alistair Sinclair.
Proceedings of RANDOM 2015, pp. 528-543.
[arXiv]
-
Spatial mixing and approximation algorithms for graphs with bounded connective constant
- Alistair Sinclair, Piyush Srivastava and Yitong Yin.
Proceedings of IEEE FOCS 2013, pp. 300-309.
[arXiv]
-
Lee-Yang theorems and the complexity of computing averages
- Alistair Sinclair and Piyush Srivastava.
Communications in Mathematical Physics 329 (2014), pp. 827-858.
Preliminary version appeared in Proceedings of ACM STOC 2013, pp. 625-634.
[arXiv]
-
Random lattice triangulations: Structure and algorithms
- Pietro Caputo, Fabio Martinelli, Alistair Sinclair and Alexandre Stauffer.
Annals of Applied Probability 25 (2015), pp. 1650-1685.
Preliminary version appeared in Proceedings of ACM STOC 2013, pp. 615-624.
[arXiv]
-
Approximation algorithms for two-state antiferromagnetic spin systems on bounded degree
graphs
- Alistair Sinclair, Piyush Srivastava and Marc Thurley.
Journal of Statistical Physics 155 (2014), pp. 666-686.
Preliminary version appeared in Proceedings of ACM-SIAM SODA 2012, pp. 941-953.
[arXiv]
-
Almost settling the hardness of noncommutative determinant
- Steve Chien, Prahladh Harsha, Alistair Sinclair and Srikanth Srinivasan.
Proceedings of ACM STOC 2011, pp. 499-508.
[arXiv]
-
Mobile geometric graphs: Detection, coverage and percolation
- Yuval Peres, Alistair Sinclair, Perla Sousi and Alexandre Stauffer.
Probability Theory and Related Fields 156 (2013), pp. 273-305.
Preliminary version appeared in Proceedings of ACM-SIAM SODA 2011, pp. 412-428.
[arXiv]
-
Liftings of tree-structured Markov chains
- Tom Hayes and Alistair Sinclair.
Proceedings of APPROX/RANDOM 2010, pp. 602-616.
-
Delaying satisfiability for random 2SAT
- Alistair Sinclair and Dan Vilenchik.
Random Structures & Algorithms 43 (2013), pp. 251-263.
Preliminary version appeared in Proceedings of APPROX/RANDOM 2010, pp. 710-723.
-
Mixing time for the Solid-on-Solid model
- Fabio Martinelli and Alistair Sinclair.
Annals of Applied Probability 22 (2012), pp. 1136-1166.
Preliminary version appeared in Proceedings of ACM STOC 2009, pp. 571-580.
[arXiv]
-
Sherali-Adams relaxations of the matching polytope
- Claire Mathieu and Alistair Sinclair.
Proceedings of ACM STOC 2009, pp. 293-302.
-
Strong and Pareto price of anarchy in congestion games
- Steve Chien and Alistair Sinclair.
Proceedings of ICALP 2009, pp. 279-291.
-
The extended k-tree algorithm
- Lorenz Minder and Alistair Sinclair.
Journal of Cryptology 25 (2012), pp. 349-382.
Preliminary version appeared in Proceedings of ACM-SIAM SODA 2009, pp. 586-595.
-
Convergence to approximate Nash equilibria in congestion games
- Steve Chien and Alistair Sinclair.
Games & Economic Behavior 71 (2011), pp. 315-327.
Preliminary version appeared in Proceedings of ACM-SIAM SODA 2007, pp. 169-178.
-
Low distortion maps between point sets
- Claire Kenyon, Yuval Rabani and Alistair Sinclair.
SIAM Journal on Computing 39 (2009), pp.1617-1636.
Preliminary version in Proceedings of ACM STOC 2004, pp. 272-280.
-
On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
- Elitza Maneva and Alistair Sinclair.
Theoretical Computer Science 407 (2008), pp. 259-369.
-
Algebras with polynomial identities and computing the determinant
- Steve Chien and Alistair Sinclair.
Full version appeared in
SIAM Journal on Computing 37 (2007), pp. 252-266.
Preliminary version appeared in Proceedings of IEEE FOCS 2004, pp. 352-361.
-
A general lower bound for mixing of single site dynamics on graphs
- Tom Hayes and Alistair Sinclair.
Annals of Applied Probability 17 (2007), pp. 931-952.
Preliminary version appeared in Proceedings of IEEE FOCS 2005, pp. 511-520.
-
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. 134-172.
Extended abstract appeared in
Proceedings of ACM-SIAM SODA 2004, pp. 449-458.
-
Negative examples for sequential importance sampling of binary contingency tables
- Ivona Bezáková, Alistair Sinclair, Daniel tefankovič and Eric Vigoda.
Algorithmica 64 (2012), pp. 606-620.
Preliminary version in Proceedings of European Symposium on Algorithms (ESA), 2006,
pp. 136-147.
-
Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs
- Assaf Naor, Yuval Rabani and Alistair Sinclair.
Journal of Functional Analysis 227 (2005), pp. 273-303.
-
Shuffling by semi-random transpositions
- Elchanan Mossel, Yuval Peres and Alistair Sinclair.
Mathematics arXiv math.PR/0404438 (April 2004).
Conference version appeared in IEEE FOCS 2004, pp. 572-581.
-
The Ising model on trees: Boundary conditions and mixing time
- Fabio Martinelli, Alistair Sinclair and Dror Weitz.
Technical Report UCB//CSD-03-1256, UC Berkeley, July 2003.
(Extended abstract appeared in Proceedings of FOCS 2003.
Slightly modified version appeared in Communications in Mathematical
Physics 250 (2004), pp. 301-334.)
- Embedding k-Outerplanar Graphs into l_1
- Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich and Alistair Sinclair.
Proceedings of ACM-SIAM SODA 2003, pp. 527-536.
Full version appeared in SIAM Journal on Discrete Mathematics 20 (2006),
pp. 119-136.
- 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. 461-479.
Preliminary version in Proceedings of RANDOM 2002, pp. 149-163.
- Random walks on truncated cubes and sampling
0-1 knapsack solutions
- Ben Morris and Alistair Sinclair, July 2002. Slightly revised version appeared in
SIAM Journal on Computing 34 (2005), pp. 195-226.
Preliminary version in IEEE FOCS 1999, pp. 230-240.
- Finding points on curves over finite fields
- Joachim von zur Gathen, Igor Shparlinski and Alistair Sinclair.
SIAM Journal on Computing 32 (2003), pp. 1436-1448.
- 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. 263-290.
Preliminary version in ACM STOC 2002, pp. 222-231.
- A polynomial-time approximation algorithm for the
permanent of a matrix with non-negative entries
- Mark Jerrum, Alistair Sinclair and Eric Vigoda, ACM STOC 2001, pp. 712-721.
Extended version available on ECCC, here;
revised version appeared in Journal of the ACM 51 (2004), pp. 671-697.
- Cuts, trees and l_1-embeddings of graphs
- Anupam Gupta, Ilan Newman, Yuri Rabinovich and Alistair Sinclair,
Combinatorica 24 (2004), pp. 233-269. Preliminary version in IEEE FOCS 1999, pp. 399-408.
- Local Divergence of Markov chains and the
analysis of iterative load-balancing schemes
- Yuval Rabani, Alistair Sinclair and Rolf Wanka, Proceedings of IEEE FOCS 1998,
pp. 694-703
- Spatial codes and the hardness of string
folding problems
- Ashwin Nayak, Alistair Sinclair and Uri Zwick, Proceedings of ACM-SIAM SODA 1998,
pp. 639-648
- 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. 1-18
- The Markov chain Monte Carlo method:
an approach to approximate counting and integration
- Mark Jerrum and Alistair Sinclair, in "Approximation Algorithms for NP-hard 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. 351-358
- Approximating the number of dimer
coverings of a lattice
- Claire Kenyon, Dana Randall and Alistair Sinclair, Journal of Statistical Physics 83 (1996), pp. 637-659.
Preliminary version in ACM STOC 1993.
- Markov Chain Algorithms for Planar Lattice Structures
- Michael Luby, Dana Randall and Alistair Sinclair, IEEE FOCS 1995, pp. 150-159
- A computational view of population genetics
- Yuval Rabani, Yuri Rabinovich and Alistair Sinclair, ACM STOC 1995, pp. 83-92
- Testable Algorithms for Self-Avoiding Walks
- Dana Randall and Alistair Sinclair, ACM/SIAM SODA 1994
- Polynomial-time Approximation Algorithms for the
Ising Model
- Mark Jerrum and Alistair Sinclair, SIAM Journal on Computing 22 (1993), pp. 1087-1116
- Optimal Speedup of Las Vegas Algorithms
- Michael Luby, Alistair Sinclair and David Zuckerman, Information Processing Letters 47 (1993), pp. 173-180
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- Alistair Sinclair, Combinatorics, Probability and Computing 1 (1992), pp. 351-370
- Quadratic Dynamical Systems
- Yuri Rabinovich, Alistair Sinclair and Avi Wigderson, FOCS 1992, pp. 304-313
- 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. 101-115.
- Fast Uniform Generation of Regular Graphs
- Mark Jerrum and Alistair Sinclair, Theoretical Computer Science 73 (1990), pp. 91-100
- Approximating the Permanent
- Mark Jerrum and Alistair Sinclair, SIAM Journal on Computing 18 (1989), pp. 1149-1178.
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. 93-133.
Current and former graduate students
Contact information
Prof. Alistair Sinclair
Computer Science Division
Soda Hall
University of California
Berkeley, CA 94720-1776
Phone: (510) 643-8144
Fax: (510) 642-5775
Email: sinclair ATSIGN cs DOT berkeley DOT edu