Alistair Sinclair, Professor

• Design and analysis of algorithms, especially randomized ones
• Computational applications of stochastic processes and nonlinear dynamical systems
• Monte Carlo methods in Statistical Physics
• Combinatorial optimization

• Mixing time for the Solid-on-Solid model
  Fabio Martinelli and Alistair Sinclair. Proceedings of ACM STOC 2009, pp. 571-580.
• 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. Submitted, 2009. Preliminary version appeared in Proceedings of ICALP 2009, pp. 279-291.
• The extended k-tree algorithm
  Lorenz Minder and Alistair Sinclair. Submitted, 2009. 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. Full version to appear in Games & Economic Behavior. Preliminary version appeared in Proceedings of ACM-SIAM SODA 2007, pp. 169-178.
• 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. Full version submitted. Preliminary version in Proceedings of European Symposium on Algorithms, 2006, pp. 136-147.
• 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.
• Low distortion maps between point sets
  Claire Kenyon, Yuval Rabani and Alistair Sinclair. Full version to appear in SIAM Journal on Computing. Preliminary version in Proceedings of ACM STOC 2004, pp. 272-280.
• 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.)
• 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, IEEE FOCS 1998, pp. 694-703
• Spatial codes and the hardness of string folding problems
  Ashwin Nayak, Alistair Sinclair and Uri Zwick, 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 monomer-dimer coverings of a lattice
  Claire Kenyon, Dana Randall and Alistair Sinclair, Journal of Statistical Physics 83 (1996), pp. 637-659
• 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

• Piyush Srivastava
• Alexandre Stauffer
• Elitza Maneva
• Dror Weitz
• Steve Chien
• Ben Morris
• Anupam Gupta
• Eric Vigoda
• Lars Rasmussen
• Ari Juels
• Michael Mitzenmacher
• Dana Randall

• CS294, Markov Chain Monte Carlo: Foundations and Applications, Fall 2009

• Theory seminars at Berkeley
• The International Computer Science Institute (ICSI)