Alistair Sinclair, Professor

• 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

• 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.

• Rachel Lawrence
• Fotis Iliopoulos
• Jingcheng Liu
• Antonio Blanca
• Piyush Srivastava
• Alexandre Stauffer
• Elitza Maneva
• Dror Weitz
• Steve Chien
• Ben Morris
• Anupam Gupta
• Eric Vigoda
• Lars Rasmussen
• Ari Juels
• Michael Mitzenmacher
• Dana Randall