# Faculty Publications - Alistair Sinclair

## Books

- A. Sinclair,
*Algorithms for Random Generation and Counting: A Markov Chain Approach*, Progress in Theoretical Computer Science, Boston: Birkhäuser, 1993. [abstract]

## Book chapters or sections

- I. Bezakova, A. Sinclair, D. Stefankovic, and E. Vigoda, "Negative examples for sequential importance sampling of binary contingency tables," in
*Algorithms: Proc. 14th Annual European Symp. (ESA 2006)*, Y. Azar and T. Erlebach, Eds., Lecture Notes in Computer Science, Vol. 4168, Berlin, Germany: Springer-Verlag, 2006, pp. 136-147. - S. R. Das and A. Sinclair, "A Markov Chain Monte Carlo Method for Derivative Pricing and Risk Assessment," in
*The World of Risk Management*, H. G. Fong, Ed., London, England, UK: World Scientific Publishing Company Ltd., 2005, pp. 131-150. - M. Dyer, A. Sinclair, E. Vigoda, and D. Weitz, "Mixing in time and space for lattice spin systems: A combinatorial view," in
*Randomization and Approximation Techniques in Computer Science: Proc. 6th Intl. Workshop (RANDOM 2002)*, J. D. P. Rolim and S. Vadhan, Eds., Lecture Notes in Computer Science, Vol. 2483, Berlin, Germany: Springer-Verlag, 2002, pp. 149-163. - A. Condon and R. M. Karp, "Algorithms for graph partitioning on the planted partition model," in
*Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques: Proc. RANDOM-APPROX '99*, D. Hochbaum, K. Jansen, J. D. P. Rolim, and A. Sinclair, Eds., Lecture Notes in Computer Science, Vol. 1671, Berlin, Germany: Springer-Verlag, 1999, pp. 221-232.

## Articles in journals or magazines

- E. Maneva and A. Sinclair, "On the satisfiability threshold and clustering of solutions of random 3-SAT formulas,"
*Theoretical Computer Science*, vol. 407, no. 1-3, pp. 359-369, Nov. 2008. - F. Martinelli, A. Sinclair, and D. Weitz, "Fast mixing for independent sets, colorings, and other models on trees,"
*Random Structures and Algorithms*, vol. 31, no. 2, pp. 134-172, Sep. 2007. - T. P. Hayes and A. Sinclair, "A general lower bound for mixing of single-site dynamics on graphs,"
*Annals of Applied Probability*, vol. 17, no. 3, pp. 931-952, June 2007. - S. Chien and A. Sinclair, "Algebras with polynomial identities and computing the determinant,"
*SIAM J. Computing*, vol. 37, no. 1, pp. 252-266, April 2007. - C. Chekuri, A. Gupta, I. Newman, Y. Rabinovich, and A. Sinclair, "Embedding $k$-outerplanar graphs into $l sub 1$,"
*SIAM J. Discrete Mathematics*, vol. 20, no. 1, pp. 119-136, Feb. 2006. - A. Naor, Y. Rabani, and A. Sinclair, "Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs,"
*J. Functional Analysis*, vol. 227, no. 2, pp. 273-303, Oct. 2005. - S. R. Das and A. Sinclair, "A Markov chain Monte Carlo method for derivative pricing and risk assessment,"
*J. Investment Management*, vol. 3, no. q, pp. 29-44, Jan. 2005. - B. Morris and A. Sinclair, "Random walks on truncated cubes and sampling 0-1 knapsack solutions,"
*SIAM J. Computing*, vol. 34, no. 1, pp. 195-226, 2004. - F. Martinelli, A. Sinclair, and D. Weitz, "Glauber dynamics on trees: Boundary conditions and mixing time,"
*Communications in Mathematical Physics*, vol. 250, no. 2, pp. 301-334, Sep. 2004. - M. Dyer, A. Sinclair, E. Vigoda, and D. Weitz, "Mixing in time and space for lattice spin systems: A combinatorial view,"
*Random Structures and Algorithms*, vol. 24, no. 4, pp. 461-479, July 2004. - M. Jerrum, A. Sinclair, and E. Vigoda, "A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries,"
*J. ACM*, vol. 51, no. 4, pp. 671-697, July 2004. - A. Gupta, I. Newman, Y. Rabinovich, and A. Sinclair, "Cuts, trees and $l sub 1$-embeddings of graphs,"
*Combinatorica*, vol. 24, no. 2, pp. 233-269, April 2004. - J. von zur Gathen, I. Shparlinski, and A. Sinclair, "Finding points on curves over finite fields,"
*SIAM J. Computing*, vol. 32, no. 6, pp. 1436-1448, 2003. - S. Chien, L. Rasmussen, and A. Sinclair, "Clifford algebras and approximating the permanent,"
*J. Computer and System Sciences*, vol. 67, no. 2, pp. 263-290, Sep. 2003. - M. Luby, D. Randall, and A. Sinclair, "Markov chain algorithms for planar lattice structures,"
*SIAM J. Computing*, vol. 31, no. 1, pp. 167-192, 2001. - D. Randall and A. Sinclair, "Self-testing algorithms for self-avoiding walks,"
*J. Mathematical Physics*, vol. 41, no. 3, pp. 1570-1584, March 2000. - Y. Rabani, Y. Rabinovich, and A. Sinclair, "A computational view of population genetics,"
*Random Structures & Algorithms*, vol. 12, no. 4, pp. 313-334, July 1998. - M. Jerrum and A. Sinclair, "Polynomial-time approximation algorithms for the Ising model,"
*SIAM J. Computing*, vol. 22, no. 5, pp. 1087-1116, Oct. 1993.

## Articles in conference proceedings

- S. Chien and A. Sinclair, "Convergence to approximate Nash equilibria in congestion games," in
*Proc. 18th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 2007)*, Philadelphia, PA: Society for Industrial and Applied Mathematics, 2007, pp. 169-178. - T. P. Hayes and A. Sinclair, "A general lower bound for mixing of single-site dynamics on graphs," in
*Proc. 46th Annual IEEE Symp. on Foundations of Computer Science (FOCS 2007)*, Los Alamitos, CA: IEEE Computer Society, 2005, pp. 511-520. - E. Mossel, Y. Peres, and A. Sinclair, "Shuffling by semi-random transpositions," in
*Proc. 45th Annual IEEE Symp. on Foundations of Computer Science (FOCS 2004)*, Los Alamitos, CA: IEEE Computer Society, 2004, pp. 572-581. - S. Chien and A. Sinclair, "Algebras with polynomial identities and computing the determinant," in
*Proc. 45th Annual IEEE Symp. on Foundations of Computer Science (FOCS 2004)*, Los Alamitos, CA: IEEE Computer Society, 2004, pp. 352-361. - C. Kenyon, Y. Rabani, and A. Sinclair, "Low distortion maps between point sets," in
*Proc. 36th Annual ACM Symp. on Theory of Computing (STOC 2004)*, New York, NY: The Association for Computing Machinery, Inc., 2004, pp. 272-280. - F. Martinelli, A. Sinclair, and D. Weitz, "Fast mixing for independent sets, colorings and other models on trees," in
*Proc. 15th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 2004)*, Philadelphia, PA: Society for Industrial and Applied Mathematics, 2004, pp. 456-465. - F. Martinelli, A. Sinclair, and D. Weitz, "The Ising model on trees: Boundary conditions and mixing time," in
*Proc. 44th Annual IEEE Symp. on Foundations of Computer Science (FOCS 2003)*, Los Alamitos, CA: IEEE Computer Society, 2003, pp. 628-639. - C. Chekuri, A. Gupta, I. Newman, Y. Rabinovich, and A. Sinclair, "Embedding $k$-outerplanar graphs into $l sub 1$," in
*Proc. 14th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 2003)*, Philadelphia, PA: Society for Industrial and Applied Mathematics, 2003, pp. 527-536. - S. Chien, L. Rasmussen, and A. Sinclair, "Clifford algebras and approximating the permanent," in
*Proc. 34th Annual ACM Symp. onTheory of Computing (STOC 2002)*, New York, NY: The Association for Computing Machinery, Inc., 2002, pp. 222-231. - M. Jerrum, A. Sinclair, and E. Vigoda, "A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries," in
*proc. 33rd Annual ACM Symp. on Theory of Computing (STOC 2001)*, New York, NY: The Association for Computing Machinery, Inc., 2001, pp. 712-721. - Y. Rabinovich, A. Sinclair, and A. Wigderson, "Quadratic dynamical systems," in
*Proc. 33rd Annual Symp. on Foundations of Computer Science*, Los Alamitos, CA: IEEE Computer Society Press, 1992, pp. 304-313.

## Conference proceedings (edited)

- D. S. Hochbaum, K. Jansen, J. D. P. Rolim, and A. Sinclair, Eds.,
*Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques: Proc. 3rd. Intl. Workshop (RANDOM-APPROX 1999)*, Lecture Notes in Computer Science, Vol. 1671, Berlin, Germany: Springer-Verlag, 1999.

## Technical Reports

- F. Martinelli, A. Sinclair, and D. Weitz, "The Ising model on trees: Boundary conditions and mixing time," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-03-1256, July 2003. [abstract]