Alistair Sinclair

110 papers A* 44A 3B 2Journal 52Unranked 7

Year	Rank	Type	Title / Venue / Authors
2025	J	`jnl`	Correlation Decay and Partition Function Zeros: Algorithms and Phase Transitions. SIAM J. Comput. Jingcheng Liu, Alistair Sinclair, Piyush Srivastava
2025	A	`conf`	Diversity in Evolutionary Dynamics (Extended Abstract). ITCS Yuval Rabani, Leonard J. Schulman, Alistair Sinclair
2025	J	`jnl`	On quantum to classical comparison for Davies generators. CoRR Joao Basso, Shirshendu Ganguly, Alistair Sinclair, Nikhil Srivastava, Zachary Stier, Thuy-Duong Vuong
2024	J	`jnl`	Diversity in Evolutionary Dynamics. CoRR Yuval Rabani, Leonard J. Schulman, Alistair Sinclair
2024	A*	`conf`	Nonlinear Dynamics for the Ising Model. STOC Pietro Caputo, Alistair Sinclair
2024	J	`jnl`	Spatial mixing and the random-cluster dynamics on lattices. Random Struct. Algorithms Reza Gheissari, Alistair Sinclair
2023	A*	`conf`	Spatial mixing and the random-cluster dynamics on lattices. SODA Reza Gheissari, Alistair Sinclair
2022	J	`jnl`	Efficiently list-edge coloring multigraphs asymptotically optimally. Random Struct. Algorithms Fotis Iliopoulos, Alistair Sinclair
2022	A*	`conf`	Low-temperature Ising dynamics with random initializations. STOC Reza Gheissari, Alistair Sinclair
2022	J	`jnl`	The critical mean-field Chayes-Machta dynamics. Comb. Probab. Comput. Antonio Blanca, Alistair Sinclair, Xusheng Zhang
2021	A*	`conf`	Entropy decay in the Swendsen-Wang dynamics on ℤ STOC Antonio Blanca, Pietro Caputo, Daniel Parisi, Alistair Sinclair, Eric Vigoda
2021	—	`conf`	The Critical Mean-Field Chayes-Machta Dynamics. APPROX-RANDOM Antonio Blanca, Alistair Sinclair, Xusheng Zhang
2021	J	`jnl`	The Critical Mean-field Chayes-Machta Dynamics. CoRR Antonio Blanca, Alistair Sinclair, Xusheng Zhang
2020	A*	`conf`	Efficiently list-edge coloring multigraphs asymptotically optimally. SODA Fotis Iliopoulos, Alistair Sinclair
2019	A*	`conf`	A Deterministic Algorithm for Counting Colorings with 2-Delta Colors. FOCS Jingcheng Liu, Alistair Sinclair, Piyush Srivastava
2019	J	`jnl`	A deterministic algorithm for counting colorings with 2Δ colors. CoRR Jingcheng Liu, Alistair Sinclair, Piyush Srivastava
2019	A*	`conf`	Beyond the Lovász Local Lemma: Point to Set Correlations and Their Algorithmic Applications. FOCS Dimitris Achlioptas, Fotis Iliopoulos, Alistair Sinclair
2019	A	`conf`	Fisher Zeros and Correlation Decay in the Ising Model. ITCS Jingcheng Liu, Alistair Sinclair, Piyush Srivastava
2019	J	`jnl`	Spatial mixing and nonlocal Markov chains. Random Struct. Algorithms Antonio Blanca, Pietro Caputo, Alistair Sinclair, Eric Vigoda
2018	J	`jnl`	A New Perspective on Stochastic Local Search and the Lovasz Local Lemma. CoRR Dimitris Achlioptas, Fotis Iliopoulos, Alistair Sinclair
2018	J	`jnl`	Efficiently list-edge coloring multigraphs asymptotically optimally. CoRR Fotis Iliopoulos, Alistair Sinclair
2018	J	`jnl`	Fisher zeros and correlation decay in the Ising model. CoRR Jingcheng Liu, Alistair Sinclair, Piyush Srivastava
2018	A*	`conf`	Spatial Mixing and Non-local Markov chains. SODA Antonio Blanca, Pietro Caputo, Alistair Sinclair, Eric Vigoda
2017	J	`jnl`	Analysis of a Classical Matrix Preconditioning Algorithm. J. ACM Leonard J. Schulman, Alistair Sinclair
2017	J	`jnl`	Spatial Mixing and Non-local Markov chains. CoRR Antonio Blanca, Pietro Caputo, Alistair Sinclair, Eric Vigoda
2017	A*	`conf`	The Ising Partition Function: Zeros and Deterministic Approximation. FOCS Jingcheng Liu, Alistair Sinclair, Piyush Srivastava
2017	J	`jnl`	The Ising Partition Function: Zeros and Deterministic Approximation. CoRR Jingcheng Liu, Alistair Sinclair, Piyush Srivastava
2016	A*	`conf`	Random-Cluster Dynamics in ℤ SODA Antonio Blanca, Alistair Sinclair
2015	A*	`conf`	Analysis of a Classical Matrix Preconditioning Algorithm. STOC Leonard J. Schulman, Alistair Sinclair
2015	J	`jnl`	Analysis of a Classical Matrix Preconditioning Algorithm. CoRR Leonard J. Schulman, Alistair Sinclair
2015	—	`conf`	Dynamics for the Mean-field Random-cluster Model. APPROX-RANDOM Antonio Blanca, Alistair Sinclair
2015	J	`jnl`	Dynamics of Lattice Triangulations on Thin Rectangles. CoRR Pietro Caputo, Fabio Martinelli, Alistair Sinclair, Alexandre Stauffer
2015	J	`jnl`	Random-Cluster Dynamics in ℤ CoRR Antonio Blanca, Alistair Sinclair
2015	A*	`conf`	Spatial mixing and the connective constant: Optimal bounds. SODA Alistair Sinclair, Piyush Srivastava, Daniel Stefankovic, Yitong Yin
2015	A*	`conf`	Symbolic Integration and the Complexity of Computing Averages. FOCS Leonard J. Schulman, Alistair Sinclair, Piyush Srivastava
2014	J	`jnl`	Spatial mixing and the connective constant: Optimal bounds. CoRR Alistair Sinclair, Piyush Srivastava, Daniel Stefankovic, Yitong Yin
2013	J	`jnl`	Delaying satisfiability for random 2SAT. Random Struct. Algorithms Alistair Sinclair, Dan Vilenchik
2013	A*	`conf`	Lee-Yang theorems and the complexity of computing averages. STOC Alistair Sinclair, Piyush Srivastava
2013	A*	`conf`	Random lattice triangulations: structure and algorithms. STOC Pietro Caputo, Fabio Martinelli, Alistair Sinclair, Alexandre Stauffer
2013	A*	`conf`	Spatial Mixing and Approximation Algorithms for Graphs with Bounded Connective Constant. FOCS Alistair Sinclair, Piyush Srivastava, Yitong Yin
2013	J	`jnl`	Spatial mixing and approximation algorithms for graphs with bounded connective constant. CoRR Alistair Sinclair, Piyush Srivastava, Yitong Yin
2012	A*	`conf`	Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs. SODA Alistair Sinclair, Piyush Srivastava, Marc Thurley
2012	J	`jnl`	Lee-Yang theorems and the complexity of computing averages CoRR Alistair Sinclair, Piyush Srivastava
2012	J	`jnl`	Negative Examples for Sequential Importance Sampling of Binary Contingency Tables. Algorithmica Ivona Bezáková, Alistair Sinclair, Daniel Stefankovic, Eric Vigoda
2012	J	`jnl`	The Extended k-tree Algorithm. J. Cryptol. Lorenz Minder, Alistair Sinclair
2011	J	`jnl`	Almost Settling the Hardness of Noncommutative Determinant CoRR Steve Chien, Prahladh Harsha, Alistair Sinclair, Srikanth Srinivasan
2011	A*	`conf`	Almost settling the hardness of noncommutative determinant. STOC Steve Chien, Prahladh Harsha, Alistair Sinclair, Srikanth Srinivasan
2011	J	`jnl`	Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs CoRR Alistair Sinclair, Piyush Srivastava, Marc Thurley
2011	J	`jnl`	Convergence to approximate Nash equilibria in congestion games. Games Econ. Behav. Steve Chien, Alistair Sinclair
2011	A*	`conf`	Mobile Geometric Graphs: Detection, Coverage and Percolation. SODA Yuval Peres, Alistair Sinclair, Perla Sousi, Alexandre Stauffer
2010	—	`conf`	Delaying Satisfiability for Random 2SAT. APPROX-RANDOM Alistair Sinclair, Dan Vilenchik
2010	—	`conf`	Liftings of Tree-Structured Markov Chains - (Extended Abstract). APPROX-RANDOM Thomas P. Hayes, Alistair Sinclair
2010	J	`jnl`	Mixing Time for the Solid-on-Solid Model CoRR Fabio Martinelli, Alistair Sinclair
2010	J	`jnl`	Mobile Geometric Graphs, and Detection and Communication Problems in Mobile Wireless Networks CoRR Alistair Sinclair, Alexandre Stauffer
2010	J	`jnl`	Mobile Geometric Graphs: Detection, Coverage and Percolation CoRR Yuval Peres, Alistair Sinclair, Perla Sousi, Alexandre Stauffer
2009	J	`jnl`	Low Distortion Maps Between Point Sets. SIAM J. Comput. Claire Kenyon, Yuval Rabani, Alistair Sinclair
2009	A*	`conf`	Mixing time for the solid-on-solid model. STOC Fabio Martinelli, Alistair Sinclair
2009	A*	`conf`	Sherali-adams relaxations of the matching polytope. STOC Claire Mathieu, Alistair Sinclair
2009	—	`conf`	Strong and Pareto Price of Anarchy in Congestion Games. ICALP (1) Steve Chien, Alistair Sinclair
2009	A*	`conf`	The extended SODA Lorenz Minder, Alistair Sinclair
2008	J	`jnl`	On the satisfiability threshold and clustering of solutions of random 3-SAT formulas. Theor. Comput. Sci. Elitza N. Maneva, Alistair Sinclair
2007	J	`jnl`	Algebras with Polynomial Identities and Computing the Determinant. SIAM J. Comput. Steve Chien, Alistair Sinclair
2007	A*	`conf`	Convergence to approximate Nash equilibria in congestion games. SODA Steve Chien, Alistair Sinclair
2007	J	`jnl`	Fast mixing for independent sets, colorings, and other models on trees. Random Struct. Algorithms Fabio Martinelli, Alistair Sinclair, Dror Weitz
2007	J	`jnl`	On the Satisfiability Threshold and Clustering of Solutions of Random 3-SAT Formulas CoRR Elitza N. Maneva, Alistair Sinclair
2006	J	`jnl`	Embedding SIAM J. Discret. Math. Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair
2006	A	`conf`	Negative Examples for Sequential Importance Sampling of Binary Contingency Tables. ESA Ivona Bezáková, Alistair Sinclair, Daniel Stefankovic, Eric Vigoda
2005	A*	`conf`	A general lower bound for mixing of single-site dynamics on graphs. FOCS Thomas P. Hayes, Alistair Sinclair
2004	J	`jnl`	A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM Mark Jerrum, Alistair Sinclair, Eric Vigoda
2004	A*	`conf`	Algebras with Polynomial Identities and Computing the Determinant. FOCS Steve Chien, Alistair Sinclair
2004	J	`jnl`	Cuts, Trees and l Comb. Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair
2004	A*	`conf`	Fast mixing for independent sets, colorings and other models on trees. SODA Fabio Martinelli, Alistair Sinclair, Dror Weitz
2004	A*	`conf`	Low distortion maps between point sets. STOC Claire Kenyon, Yuval Rabani, Alistair Sinclair
2004	J	`jnl`	Mixing in time and space for lattice spin systems: A combinatorial view. Random Struct. Algorithms Martin E. Dyer, Alistair Sinclair, Eric Vigoda, Dror Weitz
2004	J	`jnl`	Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions. SIAM J. Comput. Ben Morris, Alistair Sinclair
2004	A*	`conf`	Shuffling by Semi-Random Transpositions. FOCS Elchanan Mossel, Yuval Peres, Alistair Sinclair
2003	J	`jnl`	Clifford algebras and approximating the permanent. J. Comput. Syst. Sci. Steve Chien, Lars Eilstrup Rasmussen, Alistair Sinclair
2003	A*	`conf`	Embedding k-outerplanar graphs into l1. SODA Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair
2003	J	`jnl`	Finding Points on Curves over Finite Fields. SIAM J. Comput. Joachim von zur Gathen, Igor E. Shparlinski, Alistair Sinclair
2003	A*	`conf`	The Ising Model on Trees: Boundary Conditions and Mixing Time. FOCS Fabio Martinelli, Alistair Sinclair, Dror Weitz
2002	A*	`conf`	Clifford algebras and approximating the permanent. STOC Steve Chien, Lars Eilstrup Rasmussen, Alistair Sinclair
2002	—	`conf`	Mixing in Time and Space for Lattice Spin Systems: A Combinatorial View. RANDOM Martin E. Dyer, Alistair Sinclair, Eric Vigoda, Dror Weitz
2001	A*	`conf`	A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. STOC Mark Jerrum, Alistair Sinclair, Eric Vigoda
2001	J	`jnl`	Markov Chain Algorithms for Planar Lattice Structures. SIAM J. Comput. Michael Luby, Dana Randall, Alistair Sinclair
1999	A*	`conf`	Cuts, Trees and l FOCS Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair
1999	A*	`conf`	Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions. FOCS Ben Morris, Alistair Sinclair
1999	—	`ed.`	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 RANDOM-APPROX Dorit S. Hochbaum, Klaus Jansen, José D. P. Rolim, Alistair Sinclair
1999	J	`jnl`	Spatial Codes and the Hardness of String Folding Problems. J. Comput. Biol. Ashwin Nayak, Alistair Sinclair, Uri Zwick
1998	J	`jnl`	A computational view of population genetics. Random Struct. Algorithms Yuval Rabani, Yuri Rabinovich, Alistair Sinclair
1998	J	`jnl`	Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing. J. Algorithms Claire Kenyon, Yuval Rabani, Alistair Sinclair
1998	A*	`conf`	Local Divergence of Markov Chains and the Analysis of Iterative Load Balancing Schemes. FOCS Yuval Rabani, Alistair Sinclair, Rolf Wanka
1998	A*	`conf`	Spatial Codes and the Hardness of String Folding Problems (Extended Abstract). SODA Ashwin Nayak, Alistair Sinclair, Uri Zwick
1996	A*	`conf`	Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing (Preliminary Version). SODA Claire Kenyon, Yuval Rabani, Alistair Sinclair
1995	A*	`conf`	A computational view of population genetics. STOC Yuval Rabani, Yuri Rabinovich, Alistair Sinclair
1995	A*	`conf`	Markov Chain Algorithms for Planar Lattice Structures (Extended Abstract). FOCS Michael Luby, Dana Randall, Alistair Sinclair
1994	A*	`conf`	Testable Algorithms for Self-Avoiding Walks. SODA Dana Randall, Alistair Sinclair
1993	—	`book`	Algorithms for random generation and counting - a Markov chain approach. Alistair Sinclair
1993	A*	`conf`	Matchings in lattice graphs. STOC Claire Kenyon, Dana Randall, Alistair Sinclair
1993	—	`conf`	Optimal Speedup of Las Vegas Algorithms. ISTCS Michael Luby, Alistair Sinclair, David Zuckerman
1993	J	`jnl`	Optimal Speedup of Las Vegas Algorithms. Inf. Process. Lett. Michael Luby, Alistair Sinclair, David Zuckerman
1993	J	`jnl`	Polynomial-Time Approximation Algorithms for the Ising Model. SIAM J. Comput. Mark Jerrum, Alistair Sinclair
1992	J	`jnl`	Improved Bounds for Mixing Rates of Marcov Chains and Multicommodity Flow. Comb. Probab. Comput. Alistair Sinclair
1992	B	`conf`	Improved Bounds for Mixing Rates of Marked Chains and Multicommodity Flow. LATIN Alistair Sinclair
1992	A*	`conf`	Quadratic Dynamical Systems (Preliminary Version) FOCS Yuri Rabinovich, Alistair Sinclair, Avi Wigderson
1990	J	`jnl`	Fast Uniform Generation of Regular Graphs. Theor. Comput. Sci. Mark Jerrum, Alistair Sinclair
1990	A*	`conf`	Polynomial-Time Approximation Algorithms for Ising Model (Extended Abstract). ICALP Mark Jerrum, Alistair Sinclair
1989	J	`jnl`	Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains Inf. Comput. Alistair Sinclair, Mark Jerrum
1989	J	`jnl`	Approximating the Permanent. SIAM J. Comput. Mark Jerrum, Alistair Sinclair
1988	A*	`conf`	Conductance and the Rapid Mixing Property for Markov Chains: the Approximation of the Permanent Resolved (Preliminary Version) STOC Mark Jerrum, Alistair Sinclair
1987	B	`conf`	Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains. WG Alistair Sinclair, Mark Jerrum