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

• Convergence to approximate Nash equilibria in congestion games
  Steve Chien and Alistair Sinclair. Full version submitted. Preliminary version appeared in Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, 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. 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

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

• CS70, Discrete Mathematics for Computer Science, Fall 2007

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