Alistair Sinclair

According to our database, Alistair Sinclair authored at least 72 papers between 1988 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2023

Spatial mixing and the random-cluster dynamics on lattices.

Reza Gheissari, Alistair Sinclair

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2022

Efficiently list-edge coloring multigraphs asymptotically optimally.

Fotis Iliopoulos, Alistair Sinclair

Random Struct. Algorithms, 2022

The critical mean-field Chayes-Machta dynamics.

Antonio Blanca, Alistair Sinclair, Xusheng Zhang

Comb. Probab. Comput., 2022

Low-temperature Ising dynamics with random initializations.

Reza Gheissari, Alistair Sinclair

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

Entropy decay in the Swendsen-Wang dynamics on ℤ^<i>d</i>.

Antonio Blanca, Pietro Caputo, Daniel Parisi, Alistair Sinclair, Eric Vigoda

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

2019

Spatial mixing and nonlocal Markov chains.

Antonio Blanca, Pietro Caputo, Alistair Sinclair, Eric Vigoda

Random Struct. Algorithms, 2019

A deterministic algorithm for counting colorings with 2Δ colors.

Jingcheng Liu, Alistair Sinclair, Piyush Srivastava

CoRR, 2019

Fisher Zeros and Correlation Decay in the Ising Model.

Jingcheng Liu, Alistair Sinclair, Piyush Srivastava

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Beyond the Lovász Local Lemma: Point to Set Correlations and Their Algorithmic Applications.

Dimitris Achlioptas, Fotis Iliopoulos, Alistair Sinclair

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

A Deterministic Algorithm for Counting Colorings with 2-Delta Colors.

Jingcheng Liu, Alistair Sinclair, Piyush Srivastava

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

A New Perspective on Stochastic Local Search and the Lovasz Local Lemma.

Dimitris Achlioptas, Fotis Iliopoulos, Alistair Sinclair

CoRR, 2018

Spatial Mixing and Non-local Markov chains.

Antonio Blanca, Pietro Caputo, Alistair Sinclair, Eric Vigoda

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

Analysis of a Classical Matrix Preconditioning Algorithm.

Leonard J. Schulman, Alistair Sinclair

J. ACM, 2017

The Ising Partition Function: Zeros and Deterministic Approximation.

Jingcheng Liu, Alistair Sinclair, Piyush Srivastava

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Random-Cluster Dynamics in ℤ².

Antonio Blanca, Alistair Sinclair

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

Dynamics of Lattice Triangulations on Thin Rectangles.

Pietro Caputo, Fabio Martinelli, Alistair Sinclair, Alexandre Stauffer

CoRR, 2015

Spatial mixing and the connective constant: Optimal bounds.

Alistair Sinclair, Piyush Srivastava, Daniel Stefankovic, Yitong Yin

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Symbolic Integration and the Complexity of Computing Averages.

Leonard J. Schulman, Alistair Sinclair, Piyush Srivastava

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Dynamics for the Mean-field Random-cluster Model.

Antonio Blanca, Alistair Sinclair

Proceedings of the Approximation, 2015

2013

Delaying satisfiability for random 2SAT.

Alistair Sinclair, Dan Vilenchik

Random Struct. Algorithms, 2013

Lee-Yang theorems and the complexity of computing averages.

Alistair Sinclair, Piyush Srivastava

Proceedings of the Symposium on Theory of Computing Conference, 2013

Random lattice triangulations: structure and algorithms.

Pietro Caputo, Fabio Martinelli, Alistair Sinclair, Alexandre Stauffer

Proceedings of the Symposium on Theory of Computing Conference, 2013

Spatial Mixing and Approximation Algorithms for Graphs with Bounded Connective Constant.

Alistair Sinclair, Piyush Srivastava, Yitong Yin

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

The Extended k-tree Algorithm.

Lorenz Minder, Alistair Sinclair

J. Cryptol., 2012

Negative Examples for Sequential Importance Sampling of Binary Contingency Tables.

Ivona Bezáková, Alistair Sinclair, Daniel Stefankovic, Eric Vigoda

Algorithmica, 2012

Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs.

Alistair Sinclair, Piyush Srivastava, Marc Thurley

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

Convergence to approximate Nash equilibria in congestion games.

Steve Chien, Alistair Sinclair

Games Econ. Behav., 2011

Almost settling the hardness of noncommutative determinant.

Steve Chien, Prahladh Harsha, Alistair Sinclair, Srikanth Srinivasan

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Mobile Geometric Graphs: Detection, Coverage and Percolation.

Yuval Peres, Alistair Sinclair, Perla Sousi, Alexandre Stauffer

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010

Mobile Geometric Graphs, and Detection and Communication Problems in Mobile Wireless Networks

Alistair Sinclair, Alexandre Stauffer

CoRR, 2010

Liftings of Tree-Structured Markov Chains - (Extended Abstract).

Thomas P. Hayes, Alistair Sinclair

Proceedings of the Approximation, 2010

2009

Low Distortion Maps Between Point Sets.

Claire Kenyon, Yuval Rabani, Alistair Sinclair

SIAM J. Comput., 2009

Sherali-adams relaxations of the matching polytope.

Claire Mathieu, Alistair Sinclair

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Mixing time for the solid-on-solid model.

Fabio Martinelli, Alistair Sinclair

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

The extended <i>k</i>-tree algorithm.

Lorenz Minder, Alistair Sinclair

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Strong and Pareto Price of Anarchy in Congestion Games.

Steve Chien, Alistair Sinclair

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

2008

On the satisfiability threshold and clustering of solutions of random 3-SAT formulas.

Elitza N. Maneva, Alistair Sinclair

Theor. Comput. Sci., 2008

2007

Algebras with Polynomial Identities and Computing the Determinant.

Steve Chien, Alistair Sinclair

SIAM J. Comput., 2007

Fast mixing for independent sets, colorings, and other models on trees.

Fabio Martinelli, Alistair Sinclair, Dror Weitz

Random Struct. Algorithms, 2007

2006

Embedding <i>k</i>-Outerplanar Graphs into <i>l</i> ₁.

Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair

SIAM J. Discret. Math., 2006

2005

A general lower bound for mixing of single-site dynamics on graphs.

Thomas P. Hayes, Alistair Sinclair

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004

Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions.

Ben Morris, Alistair Sinclair

SIAM J. Comput., 2004

Mixing in time and space for lattice spin systems: A combinatorial view.

Martin E. Dyer, Alistair Sinclair, Eric Vigoda, Dror Weitz

Random Struct. Algorithms, 2004

A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.

Mark Jerrum, Alistair Sinclair, Eric Vigoda

J. ACM, 2004

Cuts, Trees and l₁-Embeddings of Graphs.

Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair

Comb., 2004

Shuffling by Semi-Random Transpositions.

Elchanan Mossel, Yuval Peres, Alistair Sinclair

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003

Finding Points on Curves over Finite Fields.

Joachim von zur Gathen, Igor E. Shparlinski, Alistair Sinclair

SIAM J. Comput., 2003

Clifford algebras and approximating the permanent.

Steve Chien, Lars Eilstrup Rasmussen, Alistair Sinclair

J. Comput. Syst. Sci., 2003

Embedding k-outerplanar graphs into l1.

Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

The Ising Model on Trees: Boundary Conditions and Mixing Time.

Fabio Martinelli, Alistair Sinclair, Dror Weitz

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2001

Markov Chain Algorithms for Planar Lattice Structures.

Michael Luby, Dana Randall, Alistair Sinclair

SIAM J. Comput., 2001

A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries.

Mark Jerrum, Alistair Sinclair, Eric Vigoda

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

1999

Spatial Codes and the Hardness of String Folding Problems.

Ashwin Nayak, Alistair Sinclair, Uri Zwick

J. Comput. Biol., 1999

1998

A computational view of population genetics.

Yuval Rabani, Yuri Rabinovich, Alistair Sinclair

Random Struct. Algorithms, 1998

Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing.

Claire Kenyon, Yuval Rabani, Alistair Sinclair

J. Algorithms, 1998

Spatial Codes and the Hardness of String Folding Problems (Extended Abstract).

Ashwin Nayak, Alistair Sinclair, Uri Zwick

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Local Divergence of Markov Chains and the Analysis of Iterative Load Balancing Schemes.

Yuval Rabani, Alistair Sinclair, Rolf Wanka

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1996

Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing (Preliminary Version).

Claire Kenyon, Yuval Rabani, Alistair Sinclair

Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

1995

Markov Chain Algorithms for Planar Lattice Structures (Extended Abstract).

Michael Luby, Dana Randall, Alistair Sinclair

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

Testable Algorithms for Self-Avoiding Walks.

Dana Randall, Alistair Sinclair

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993

Polynomial-Time Approximation Algorithms for the Ising Model.

Mark Jerrum, Alistair Sinclair

SIAM J. Comput., 1993

Optimal Speedup of Las Vegas Algorithms.

Michael Luby, Alistair Sinclair, David Zuckerman

Inf. Process. Lett., 1993

Matchings in lattice graphs.

Claire Kenyon, Dana Randall, Alistair Sinclair

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Algorithms for random generation and counting - a Markov chain approach.

Alistair Sinclair

Progress in theoretical computer science, Birkhäuser, ISBN: 978-0-8176-3658-6, 1993

1992

Improved Bounds for Mixing Rates of Marcov Chains and Multicommodity Flow.

Alistair Sinclair

Comb. Probab. Comput., 1992

Improved Bounds for Mixing Rates of Marked Chains and Multicommodity Flow.

Alistair Sinclair

Proceedings of the LATIN '92, 1992

Quadratic Dynamical Systems (Preliminary Version)

Yuri Rabinovich, Alistair Sinclair, Avi Wigderson

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1990

Fast Uniform Generation of Regular Graphs.

Mark Jerrum, Alistair Sinclair

Theor. Comput. Sci., 1990

Polynomial-Time Approximation Algorithms for Ising Model (Extended Abstract).

Mark Jerrum, Alistair Sinclair

Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

1989

Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains

Alistair Sinclair, Mark Jerrum

Inf. Comput., July, 1989

Approximating the Permanent.

Mark Jerrum, Alistair Sinclair

SIAM J. Comput., 1989

1988

Conductance and the Rapid Mixing Property for Markov Chains: the Approximation of the Permanent Resolved (Preliminary Version)

Mark Jerrum, Alistair Sinclair

Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988