Alistair Sinclair

Ivona Bezáková, Alistair Sinclair, Daniel Stefankovic, Eric Vigoda: Negative Examples for Sequential Importance Sampling of Binary Contingency Tables. Algorithmica 64(4): 606-620 (2012)

Lorenz Minder, Alistair Sinclair: The Extended k-tree Algorithm. J. Cryptology 25(2): 349-382 (2012)

Alistair Sinclair, Piyush Srivastava, Marc Thurley: Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs. SODA 2012: 941-953

Alistair Sinclair, Piyush Srivastava: Lee-Yang theorems and the complexity of computing averages. CoRR abs/1211.2376 (2012)

Steve Chien, Alistair Sinclair: Convergence to approximate Nash equilibria in congestion games. Games and Economic Behavior 71(2): 315-327 (2011)

Yuval Peres, Alistair Sinclair, Perla Sousi, Alexandre Stauffer: Mobile Geometric Graphs: Detection, Coverage and Percolation. SODA 2011: 412-428

Steve Chien, Prahladh Harsha, Alistair Sinclair, Srikanth Srinivasan: Almost settling the hardness of noncommutative determinant. STOC 2011: 499-508

Steve Chien, Prahladh Harsha, Alistair Sinclair, Srikanth Srinivasan: Almost Settling the Hardness of Noncommutative Determinant. CoRR abs/1101.1169 (2011)

Alistair Sinclair, Piyush Srivastava, Marc Thurley: Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs. CoRR abs/1107.2368 (2011)

Thomas P. Hayes, Alistair Sinclair: Liftings of Tree-Structured Markov Chains - (Extended Abstract). APPROX-RANDOM 2010: 602-616

Alistair Sinclair, Dan Vilenchik: Delaying Satisfiability for Random 2SAT. APPROX-RANDOM 2010: 710-723

Alistair Sinclair, Alexandre Stauffer: Mobile Geometric Graphs, and Detection and Communication Problems in Mobile Wireless Networks. CoRR abs/1005.1117 (2010)

Yuval Peres, Alistair Sinclair, Perla Sousi, Alexandre Stauffer: Mobile Geometric Graphs: Detection, Coverage and Percolation. CoRR abs/1008.0075 (2010)

Fabio Martinelli, Alistair Sinclair: Mixing Time for the Solid-on-Solid Model. CoRR abs/1008.0125 (2010)

Claire Kenyon, Yuval Rabani, Alistair Sinclair: Low Distortion Maps Between Point Sets. SIAM J. Comput. 39(4): 1617-1636 (2009)

Steve Chien, Alistair Sinclair: Strong and Pareto Price of Anarchy in Congestion Games. ICALP (1) 2009: 279-291

Lorenz Minder, Alistair Sinclair: The extended k-tree algorithm. SODA 2009: 586-595

Claire Mathieu, Alistair Sinclair: Sherali-adams relaxations of the matching polytope. STOC 2009: 293-302

Fabio Martinelli, Alistair Sinclair: Mixing time for the solid-on-solid model. STOC 2009: 571-580

Elitza N. Maneva, Alistair Sinclair: On the satisfiability threshold and clustering of solutions of random 3-SAT formulas. Theor. Comput. Sci. 407(1-3): 359-369 (2008)

Fabio Martinelli, Alistair Sinclair, Dror Weitz: Fast mixing for independent sets, colorings, and other models on trees. Random Struct. Algorithms 31(2): 134-172 (2007)

Steve Chien, Alistair Sinclair: Algebras with Polynomial Identities and Computing the Determinant. SIAM J. Comput. 37(1): 252-266 (2007)

Steve Chien, Alistair Sinclair: Convergence to approximate Nash equilibria in congestion games. SODA 2007: 169-178

Elitza N. Maneva, Alistair Sinclair: On the Satisfiability Threshold and Clustering of Solutions of Random 3-SAT Formulas. CoRR abs/0710.0805 (2007)

Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair: Embedding k-Outerplanar Graphs into l ₁. SIAM J. Discrete Math. 20(1): 119-136 (2006)

Ivona Bezáková, Alistair Sinclair, Daniel Stefankovic, Eric Vigoda: Negative Examples for Sequential Importance Sampling of Binary Contingency Tables. ESA 2006: 136-147

Thomas P. Hayes, Alistair Sinclair: A general lower bound for mixing of single-site dynamics on graphs. FOCS 2005: 511-520

Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair: Cuts, Trees and l₁-Embeddings of Graphs. Combinatorica 24(2): 233-269 (2004)

Mark Jerrum, Alistair Sinclair, Eric Vigoda: A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM 51(4): 671-697 (2004)

Martin E. Dyer, Alistair Sinclair, Eric Vigoda, Dror Weitz: Mixing in time and space for lattice spin systems: A combinatorial view. Random Struct. Algorithms 24(4): 461-479 (2004)

Ben Morris, Alistair Sinclair: Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions. SIAM J. Comput. 34(1): 195-226 (2004)

Steve Chien, Alistair Sinclair: Algebras with Polynomial Identities and Computing the Determinant. FOCS 2004: 352-361

Elchanan Mossel, Yuval Peres, Alistair Sinclair: Shuffling by Semi-Random Transpositions. FOCS 2004: 572-581

Fabio Martinelli, Alistair Sinclair, Dror Weitz: Fast mixing for independent sets, colorings and other models on trees. SODA 2004: 456-465

Claire Kenyon, Yuval Rabani, Alistair Sinclair: Low distortion maps between point sets. STOC 2004: 272-280

Steve Chien, Lars Eilstrup Rasmussen, Alistair Sinclair: Clifford algebras and approximating the permanent. J. Comput. Syst. Sci. 67(2): 263-290 (2003)

Joachim von zur Gathen, Igor Shparlinski, Alistair Sinclair: Finding Points on Curves over Finite Fields. SIAM J. Comput. 32(6): 1436-1448 (2003)

Fabio Martinelli, Alistair Sinclair, Dror Weitz: The Ising Model on Trees: Boundary Conditions and Mixing Time. FOCS 2003: 628-639

Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair: Embedding k-outerplanar graphs into l1. SODA 2003: 527-536

Martin E. Dyer, Alistair Sinclair, Eric Vigoda, Dror Weitz: Mixing in Time and Space for Lattice Spin Systems: A Combinatorial View. RANDOM 2002: 149-163

Steve Chien, Lars Eilstrup Rasmussen, Alistair Sinclair: Clifford algebras and approximating the permanent. STOC 2002: 222-231

Michael Luby, Dana Randall, Alistair Sinclair: Markov Chain Algorithms for Planar Lattice Structures. SIAM J. Comput. 31(1): 167-192 (2001)

Mark Jerrum, Alistair Sinclair, Eric Vigoda: A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. STOC 2001: 712-721

Ashwin Nayak, Alistair Sinclair, Uri Zwick: Spatial Codes and the Hardness of String Folding Problems. Journal of Computational Biology 6(1): 13-36 (1999)

Ben Morris, Alistair Sinclair: Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions. FOCS 1999: 230-240

Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair: Cuts, Trees and l₁-Embeddings of Graphs. FOCS 1999: 399-409

Dorit S. Hochbaum, Klaus Jansen, José D. P. Rolim, Alistair Sinclair (Eds.): Randomization, Approximation, and Combinatorial Algorithms and Techniques, Third International Workshop on Randomization and Approximation Techniques in Computer Science, and Second International Workshop on Approximation Algorithms for Combinatorial Optimization Problems RANDOM-APPROX'99, Berkeley, CA, USA, August 8-11, 1999, Proceedings. Lecture Notes in Computer Science 1671, Springer 1999, isbn 3-540-66329-0

Claire Kenyon, Yuval Rabani, Alistair Sinclair: Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing. J. Algorithms 27(2): 218-235 (1998)

Yuval Rabani, Yuri Rabinovich, Alistair Sinclair: A computational view of population genetics. Random Struct. Algorithms 12(4): 313-334 (1998)

Yuval Rabani, Alistair Sinclair, Rolf Wanka: Local Divergence of Markov Chains and the Analysis of Iterative Load Balancing Schemes. FOCS 1998: 694-705

Ashwin Nayak, Alistair Sinclair, Uri Zwick: Spatial Codes and the Hardness of String Folding Problems (Extended Abstract). SODA 1998: 639-648

Claire Kenyon, Yuval Rabani, Alistair Sinclair: Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing (Preliminary Version). SODA 1996: 351-358

Michael Luby, Dana Randall, Alistair Sinclair: Markov Chain Algorithms for Planar Lattice Structures (Extended Abstract). FOCS 1995: 150-159

Yuval Rabani, Yuri Rabinovich, Alistair Sinclair: A computational view of population genetics. STOC 1995: 83-92

Dana Randall, Alistair Sinclair: Testable Algorithms for Self-Avoiding Walks. SODA 1994: 593-602

Alistair Sinclair: Algorithms for random generation and counting - a Markov chain approach. Progress in theoretical computer science, Birkhäuser 1993, isbn 978-0-8176-3658-6, pp. 1-146

Michael Luby, Alistair Sinclair, David Zuckerman: Optimal Speedup of Las Vegas Algorithms. Inf. Process. Lett. 47(4): 173-180 (1993)

Mark Jerrum, Alistair Sinclair: Polynomial-Time Approximation Algorithms for the Ising Model. SIAM J. Comput. 22(5): 1087-1116 (1993)

Michael Luby, Alistair Sinclair, David Zuckerman: Optimal Speedup of Las Vegas Algorithms. ISTCS 1993: 128-133

Claire Kenyon, Dana Randall, Alistair Sinclair: Matchings in lattice graphs. STOC 1993: 738-746

Alistair Sinclair: Improved Bounds for Mixing Rates of Marcov Chains and Multicommodity Flow. Combinatorics, Probability & Computing 1: 351-370 (1992)

Yuri Rabinovich, Alistair Sinclair, Avi Wigderson: Quadratic Dynamical Systems (Preliminary Version). FOCS 1992: 304-313

Alistair Sinclair: Improved Bounds for Mixing Rates of Marked Chains and Multicommodity Flow. LATIN 1992: 474-487

Mark Jerrum, Alistair Sinclair: Fast Uniform Generation of Regular Graphs. Theor. Comput. Sci. 73(1): 91-100 (1990)

Mark Jerrum, Alistair Sinclair: Polynomial-Time Approximation Algorithms for Ising Model (Extended Abstract). ICALP 1990: 462-475

Alistair Sinclair, Mark Jerrum: Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains. Inf. Comput. 82(1): 93-133 (1989)

Mark Jerrum, Alistair Sinclair: Approximating the Permanent. SIAM J. Comput. 18(6): 1149-1178 (1989)

Mark Jerrum, Alistair Sinclair: Conductance and the Rapid Mixing Property for Markov Chains: the Approximation of the Permanent Resolved (Preliminary Version). STOC 1988: 235-244

Alistair Sinclair, Mark Jerrum: Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains. WG 1987: 134-148