Arrow Research search

Author name cluster

Alistair Sinclair

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

46 papers
2 author rows

Possible papers

46

STOC Conference 2024 Conference Paper

Nonlinear Dynamics for the Ising Model

  • Pietro Caputo
  • Alistair Sinclair

We introduce and analyze a natural class of nonlinear dynamics for spin systems such as the Ising model. This class of dynamics is based on the framework of mass action kinetics, which models the evolution of systems of entities under pairwise interactions, and captures a number of important nonlinear models from various fields, including chemical reaction networks, Boltzmann’s model of an ideal gas, recombination in population genetics, and genetic algorithms. In the context of spin systems, it is a natural generalization of linear dynamics based on Markov chains, such as Glauber dynamics and block dynamics, which are by now well understood. However, the inherent nonlinearity makes the dynamics much harder to analyze, and rigorous quantitative results so far are limited to processes which converge to essentially trivial stationary distributions that are product measures. In this paper we provide the first quantitative convergence analysis for natural nonlinear dynamics in a combinatorial setting where the stationary distribution contains non-trivial correlations, namely spin systems at high temperatures. We prove that nonlinear versions of both the Glauber dynamics and the block dynamics converge to the Gibbs distribution of the Ising model (with given external fields) in times O ( n log n ) and O (log n ) respectively, where n is the size of the underlying graph (number of spins). Given the lack of general analytical methods for such nonlinear systems, our analysis is unconventional, and combines tools such as information percolation (due in the linear setting to Lubetzky and Sly), a novel coupling of the Ising model with Erdős-Rényi random graphs, and non-traditional branching processes augmented by a ”fragmentation” process. Our results extend immediately to any spin system with a finite number of spins and bounded interactions.

Details

SODA Conference 2023 Conference Paper

Spatial mixing and the random-cluster dynamics on lattices

  • Reza Gheissari
  • Alistair Sinclair

An important paradigm in the understanding of mixing times of Glauber dynamics for spin systems is the correspondence between spatial mixing properties of the models and bounds on the mixing time of the dynamics. This includes, in particular, the classical notions of weak and strong spatial mixing, which have been used to show the best known mixing time bounds in the high-temperature regime for the Glauber dynamics for the Ising and Potts models. Glauber dynamics for the random-cluster model does not naturally fit into this spin systems framework because its transition rules are not local. In this paper, we present various implications between weak spatial mixing, strong spatial mixing, and the newer notion of spatial mixing within a phase, and mixing time bounds for the random-cluster dynamics in finite subsets of ℤ d for general d  2. These imply a host of new results, including optimal O(N log N ) mixing for the random cluster dynamics on torii and boxes on N vertices in ℤ d at all high temperatures and at sufficiently low temperatures, and for large values of q quasi-polynomial (or quasi-linear when d = 2) mixing time bounds from random phase initializations on torii at the critical point (where by contrast the mixing time from worst-case initializations is exponentially large). In the same parameter regimes, these results translate to fast sampling algorithms for the Potts model on ℤ d for general d. * The full version of the paper can be accessed at https: //arxiv. org/abs/2207. 11195

Details

STOC Conference 2022 Conference Paper

Low-temperature Ising dynamics with random initializations

  • Reza Gheissari
  • Alistair Sinclair

Glauber dynamics on spin systems are well known to suffer exponential slowdowns at low temperatures due to the emergence of multiple metastable phases, separated by narrow bottlenecks that are hard for the dynamics to cross. It is a folklore belief that if the dynamics is initialized from an appropriate random mixture of ground states, one for each phase, then convergence to the Gibbs distribution should be much faster. However, such phenomena have largely evaded rigorous analysis, as most tools in the study of Markov chain mixing times are tailored to worst-case initializations. In this paper we develop a general framework towards establishing this conjectured behavior for the Ising model. In the classical setting of the Ising model on an N -vertex torus in ℤ d , our framework implies that the mixing time for the Glauber dynamics, initialized from a 1/2-1/2 mixture of the all-plus and all-minus configurations, is N 1+ o (1) in dimension d =2, and at most quasi-polynomial in all dimensions d ≥ 3, at all temperatures below the critical one. The key innovation in our analysis is the introduction of the notion of ”weak spatial mixing within a phase”, a low-temperature adaptation of the classical concept of weak spatial mixing. We show both that this new notion is strong enough to control the mixing time from the above random initialization (by relating it to the mixing time with plus boundary condition at O (log N ) scales), and that it holds at all low temperatures in all dimensions. This framework naturally extends to more general families of graphs. To illustrate this, we use the same approach to establish optimal O ( N log N ) mixing for the Ising Glauber dynamics on random regular graphs at sufficiently low temperatures, when initialized from the same random mixture.

Details

FOCS Conference 2019 Conference Paper

A Deterministic Algorithm for Counting Colorings with 2-Delta Colors

  • Jingcheng Liu 0001
  • Alistair Sinclair
  • Piyush Srivastava 0001

We give a polynomial time deterministic approximation algorithm (an FPTAS) for counting the number of q-colorings of a graph of maximum degree Delta, provided only that q ≥ 2Delta. This substantially improves on previous deterministic algorithms for this problem, the best of which requires q ≥ 2. 58Delta, and matches the natural bound for randomized algorithms obtained by a straightforward application of Markov chain Monte Carlo. In the case when the graph is also triangle-free, we show that our algorithm applies under the weaker condition q ≥ αΔ+β, where α ≈ 1. 764 and β = β(α) are absolute constants. Our result applies more generally to list colorings, and to the partition function of the anti-ferromagnetic Potts model. The core of our argument is the establishment of a region in the complex plane in which the Potts model partition function (a classical graph polynomial) has no zeros. This result, which substantially sharpens previous work on the same problem, is of independent interest. Our algorithms follow immediately from zero-freeness via the “polynomial interpolation" method of Barvinok. Interestingly, our method for identifying the zero-free region leverages probabilistic and combinatorial ideas that have been used in the analysis of Markov chains.

Details

FOCS Conference 2019 Conference Paper

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

  • Dimitris Achlioptas
  • Fotis Iliopoulos
  • Alistair Sinclair

Following the groundbreaking algorithm of Moser and Tardos for the Lovasz Local Lemma (LLL), there has been a plethora of results analyzing local search algorithms for various constraint satisfaction problems. The algorithms considered fall into two broad categories: resampling algorithms, analyzed via different algorithmic LLL conditions; and backtracking algorithms, analyzed via entropy compression arguments. This paper introduces a new convergence condition that seamlessly handles resampling, backtracking, and hybrid algorithms, i. e. , algorithms that perform both resampling and backtracking steps. Unlike previous work on the LLL, our condition replaces the notion of a dependency or causality graph by quantifying point-to-set correlations between bad events. As a result, our condition simultaneously: (i) captures the most general algorithmic LLL condition known as a special case; (ii) significantly simplifies the analysis of entropy compression applications; (iii) relates backtracking algorithms, which are conceptually very different from resampling algorithms, to the LLL; and most importantly (iv) allows for the analysis of hybrid algorithms, which were outside the scope of previous techniques. We give several applications of our condition, including a new hybrid vertex coloring algorithm that extends the recent breakthrough result of Molloy for coloring triangle-free graphs to arbitrary graphs.

Details

FOCS Conference 2017 Conference Paper

The Ising Partition Function: Zeros and Deterministic Approximation

  • Jingcheng Liu 0001
  • Alistair Sinclair
  • Piyush Srivastava 0001

We study the problem of approximating the partition function of the ferromagnetic Ising model in graphs and hypergraphs. Our first result is a deterministic approximation scheme (an FPTAS) for the partition function in bounded degree graphs that is valid over the entire range of parameters β (the interaction) and λ (the external field), except for the case |λ| = 1 (the “zero-field” case). A randomized algorithm (FPRAS) for all graphs, and all β, λ, has long been known. Unlike most other deterministic approximation algorithms for problems in statistical physics and counting, our algorithm does not rely on the “decay of correlations” property. Rather, we exploit and extend machinery developed recently by Barvinok, and Patel and Regts, based on the location of the complex zeros of the partition function, which can be seen as an algorithmic realization of the classical Lee-Yang approach to phase transitions. Our approach extends to the more general setting of the Ising model on hypergraphs of bounded degree and edge size, where no previous algorithms (even randomized) were known for a wide range of parameters. In order to achieve this extension, we establish a tight version of the Lee-Yang theorem for the Ising model on hypergraphs, improving a classical result of Suzuki and Fisher.

Details

SODA Conference 2016 Conference Paper

Random-Cluster Dynamics in ℤ 2

  • Antonio Blanca
  • Alistair Sinclair

The random-cluster model has been widely studied as a unifying framework for random graphs, spin systems and electrical networks, but its dynamics have so far largely resisted analysis. In this paper we analyze the Glauber dynamics of the random-cluster model in the canonical case where the underlying graph is an n × n box in the Cartesian lattice ℤ 2. Our main result is a O ( n 2 log n ) upper bound for the mixing time at all values of the model parameter p except the critical point p = p c ( q ), and for all values of the second model parameter q ≥ 1. We also provide a matching lower bound proving that our result is tight. Our analysis takes as its starting point the recent breakthrough by Beffara and Duminil-Copin on the location of the random-cluster phase transition in ℤ 2. It is reminiscent of similar results for spin systems such as the Ising and Potts models, but requires the reworking of several standard tools in the context of the random-cluster model, which is not a spin system in the usual sense.

Details

STOC Conference 2015 Conference Paper

Analysis of a Classical Matrix Preconditioning Algorithm

  • Leonard J. Schulman
  • Alistair Sinclair

We study a classical iterative algorithm for the problem of balancing matrices in the L ∞ norm via a scaling transformation. This algorithm, which goes back to Osborne and Parlett & Reinsch in the 1960s, is implemented as a standard preconditioner in many numerical linear algebra packages. Surprisingly, despite its widespread use over several decades, no bounds were known on its rate of convergence. In this paper we prove that, for a large class of irreducible n x n (real or complex) input matrices~$A$, a natural variant of the algorithm converges in O(n 3 log(nρ/ε)) elementary balancing operations, where ρ measures the initial imbalance of A and ε is the target imbalance of the output matrix. (The imbalance of A is max i |log(a i out /a i in )|, where a i out ,a i in are the maximum entries in magnitude in the ith row and column respectively.) This bound is tight up to the log n factor. A balancing operation scales the ith row and column so that their maximum entries are equal, and requires O(m/n) arithmetic operations on average, where m is the number of non-zero elements in A. Thus the running time of the iterative algorithm is ~O(n 2 m). This is the first time bound of any kind on any variant of the Osborne-Parlett-Reinsch algorithm. The class of matrices for which the above analysis holds are those which satisfy a condition we call Unique Balance , meaning that the limit of the iterative balancing process does not depend on the order in which balancing operations are performed. We also prove a combinatorial characterization of the Unique Balance property, which had earlier been conjectured by Chen.

Details

SODA Conference 2015 Conference Paper

Spatial mixing and the connective constant: Optimal bounds

  • Alistair Sinclair
  • Piyush Srivastava 0001
  • Daniel Stefankovic
  • Yitong Yin

We study the problem of deterministic approximate counting of matchings and independent sets in graphs of bounded connective constant. More generally, we consider the problem of evaluating the partition functions of the monomer-dimer model (which is defined as a weighted sum over all matchings where each matching is given a weight γ | V | – 2| M | in terms of a fixed parameter γ called the monomer activity ) and the hard core model (which is defined as a weighted sum over all independent sets where an independent set I is given a weight γ | I | in terms of a fixed parameter γ called the vertex activity ). The connective constant is a natural measure of the average degree of a graph which has been studied extensively in combinatorics and mathematical physics, and can be bounded by a constant even for certain unbounded degree graphs such as those sampled from the sparse Erdös-Rényi model ( n, d / n ). Our main technical contribution is to prove the best possible rates of decay of correlations in the natural probability distributions induced by both the hard core model and the monomer-dimer model in graphs with a given bound on the connective constant. These results on decay of correlations are obtained using a new framework based on the so-called message approach that has been extensively used recently to prove such results for bounded degree graphs. We then use these optimal decay of correlations results to obtain FPTASs for the two problems on graphs of bounded connective constant. In particular, for the monomer-dimer model, we give a deterministic FPTAS for the partition function on all graphs of bounded connective constant for any given value of the monomer activity. The best previously known deterministic algorithm was due to Bayati, Gamarnik, Katz, Nair and Tetali [STOC 2007], and gave the same runtime guarantees as our results but only for the case of bounded degree graphs. For the hard core model, we give an FPTAS for graphs of connective constant Δ whenever the vertex activity λ < λ c (Δ), where; this result is optimal in the sense that an FPTAS for any λ > λ c (Δ) would imply that NP=RP [Sly, FOCS 2010]. The previous best known result in this direction was a recent paper by a subset of the current authors [FOCS 2013], where the result was established under the suboptimal condition λ < λ c (Δ + 1). Our techniques also allow us to improve upon known bounds for decay of correlations for the hard core model on various regular lattices, including those obtained by Restrepo, Shin, Vigoda and Tetali [FOCS 11] for the special case of ℤ 2 using sophisticated numerically intensive methods tailored to that special case.

Details

FOCS Conference 2015 Conference Paper

Symbolic Integration and the Complexity of Computing Averages

  • Leonard J. Schulman
  • Alistair Sinclair
  • Piyush Srivastava 0001

We study the computational complexity of several natural problems arising in statistical physics and combinatorics. In particular, we consider the following problems: the mean magnetization and mean energy of the Ising model (both the ferromagnetic and the anti-ferromagnetic settings), the average size of an independent set in the hard core model, and the average size of a matching in the monomer-dimer model. We prove that for all non-trivial values of the underlying model parameters, exactly computing these averages is #P-hard. In contrast to previous results of Sinclair and Srivastava (2013) for the mean magnetization of the ferromagnetic Ising model, our approach does not use any Lee-Yang type theorems about the complex zeros of partition functions. Indeed, it was due to the lack of suitable Lee-Yang theorems for models such as the anti-ferromagnetic Ising model that some of the problems we study here were left open by Sinclair and Srivastava. In this paper, we instead use some relatively simple and well-known ideas from the theory of automatic symbolic integration to complete our hardness reductions.

Details

FOCS Conference 2013 Conference Paper

Spatial Mixing and Approximation Algorithms for Graphs with Bounded Connective Constant

  • Alistair Sinclair
  • Piyush Srivastava 0001
  • Yitong Yin

The hard core model in statistical physics is a probability distribution on independent sets in a graph in which the weight of any independent set I is proportional to λ |I|, where λ > 0 is the vertex activity. We show that there is an intimate connection between the connective constant of a graph and the phenomenon of strong spatial mixing (decay of correlations) for the hard core model; specifically, we prove that the hard core model with vertex activity λ c (Δ+1) exhibits strong spatial mixing on any graph of connective constant Δ, irrespective of its maximum degree, and hence derive an FPTAS for the partition function of the hard core model on such graphs. Here λ c (d) ··= d d /(d-1) d+1 is the critical activity for the uniqueness of the Gibbs measure of the hard core model on the infinite d-ary tree. As an application, we show that the partition function can be efficiently approximated with high probability on graphs drawn from the random graph model G (n, d/n) for all λ <; e/d, even though the maximum degree of such graphs is unbounded with high probability. We also improve upon Weitz's bounds for strong spatial mixing on bounded degree graphs [30] by providing a computationally simple method which uses known estimates of the connective constant of a lattice to obtain bounds on the vertex activities λ for which the hard core model on the lattice exhibits strong spatial mixing. Using this framework, we improve upon these bounds for several lattices including the Cartesian lattice in dimensions 3 and higher. Our techniques also allow us to relate the threshold for the uniqueness of the Gibbs measure on a general tree to its branching factor [15].

Details

STOC Conference 2011 Conference Paper

Almost settling the hardness of noncommutative determinant

  • Steve Chien
  • Prahladh Harsha
  • Alistair Sinclair
  • Srikanth Srinivasan 0001

In this paper, we study the complexity of computing the determinant of a matrix over a noncommutative algebra. In particular, we ask the question: "Over which algebras is the determinant easier to compute than the permanent?" Towards resolving this question, we show the following results for noncommutative determinant computation: [Hardness] Computing the determinant of an n x n matrix whose entries are themselves 2 x 2 matrices over any field of zero or odd characteristic is as hard as computing the permanent over the field. This extends the recent result of Arvind and Srinivasan, which required the entries to be matrices of dimension linear in n. [Easiness] The determinant of an n x n matrix whose entries are themselves d x d upper triangular matrices can be computed in poly(n d ) time. Combining the above with the decomposition theorem for finite dimensional algebras (and in particular exploiting the simple structure of 2 x 2 matrix algebras), we can extend the above hardness and easiness statements to more general algebras as follows. Let A be a finite dimensional algebra over a finite field of odd characteristic with radical R(A). [Hardness] If the quotient A/R(A) is noncommutative, then computing the determinant over the algebra A is as hard as computing the permanent. [Easiness] If the quotient A/R(A) is commutative, and furthermore R(A) has nilpotency index d (i.e., d is the smallest integer such that R(A) d =0), then there exists a poly(n d )-time algorithm that computes determinants over the algebra A. In particular, for any constant dimensional algebra A over a finite field of odd characteristic, since the nilpotency index of R(A) is at most a constant, we have the following dichotomy theorem: if A/R(A) is commutative then efficient determinant computation is possible, and otherwise determinant is as hard as permanent.

Details

SODA Conference 2011 Conference Paper

Mobile Geometric Graphs: Detection, Coverage and Percolation

  • Yuval Peres
  • Alistair Sinclair
  • Perla Sousi
  • Alexandre Stauffer

Static wireless networks are by now quite well understood mathematically through the random geometric graph model. By contrast, there are relatively few rigorous results on the practically important case of mobile networks. In this paper we consider a natural extension of the random geometric graph model to the mobile setting by allowing nodes to move in space according to Brownian motion. We study three fundamental questions in this model: detection (the time until a given target point—which may be either fixed or moving—is detected by the network), coverage (the time until all points inside a finite box are detected by the network), and percolation (the time until a given node is able to communicate with the giant component of the network). We derive precise asymptotics for these problems by combining ideas from stochastic geometry, coupling and multi-scale analysis. We also give an application of our results to analyze the time to broadcast a message in a mobile network.

Details

STOC Conference 2009 Conference Paper

Mixing time for the solid-on-solid model

  • Fabio Martinelli
  • Alistair Sinclair

We analyze the mixing time of a natural local Markov chain (the Glauber dynamics) on configurations of the solid-on-solid model of statistical physics. This model has been proposed, among other things, as an idealization of the behavior of contours in the Ising model at low temperatures. Our main result is an upper bound on the mixing time of O~(n 3.5 ), which is tight within a factor of O~(√n). The proof, which in addition gives insight into the actual evolution of the contours, requires the introduction of several novel analytical techniques that we conjecture will have other applications.

Details

TCS Journal 2008 Journal Article

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

  • Elitza Maneva
  • Alistair Sinclair

We study the structure of satisfying assignments of a random 3-Sat formula. In particular, we show that a random formula of density α ≥ 4. 453 almost surely has no non-trivial “core” assignments. Core assignments are certain partial assignments that can be extended to satisfying assignments, and have been studied recently in connection with the Survey Propagation heuristic for random Sat. Their existence implies the presence of clusters of solutions, and they have been shown to exist with high probability below the satisfiability threshold for k -Sat with k ≥ 9 [D. Achlioptas, F. Ricci-Tersenghi, On the solution-space geometry of random constraint satisfaction problems, in: Proc. 38th ACM Symp. Theory of Computing, STOC, 2006, pp. 130–139]. Our result implies that either this does not hold for 3-Sat, or the threshold density for satisfiability in 3-Sat lies below 4. 453. The main technical tool that we use is a novel simple application of the first moment method.

Details DOI

FOCS Conference 2005 Conference Paper

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

  • Thomas P. Hayes
  • Alistair Sinclair

We prove that any Markov chain that performs local, reversible updates on randomly chosen vertices of a bounded-degree graph necessarily has mixing time at least /spl Omega/(n log n), where it is the number of vertices. Our bound applies to the so-called "Glauber dynamics" that has been used extensively in algorithms for the Ising model, independent sets, graph colorings and other structures in computer science and statistical physics, and demonstrates that many of these algorithms are optimal up to constant factors within their class. Previously no super-linear lower bound for this class of algorithms was known. Though widely conjectured, such a bound had been proved previously only in very restricted circumstances, such as for the empty graph and the path. We also show that the assumption of bounded degree is necessary by giving a family of dynamics on graphs of unbounded degree with mixing time O(n).

Details

FOCS Conference 2004 Conference Paper

Algebras with Polynomial Identities and Computing the Determinant

  • Steve Chien
  • Alistair Sinclair

Nisan (1991) proved an exponential lower bound on the size of an algebraic branching program (ABP) that computes the determinant of a matrix in the non-commutative "free algebra" setting, in which there are no non-trivial relationships between the matrix entries. By contrast, when the matrix entries commute there are polynomial size ABPs for the determinant. This paper extends Nisan's result to a much wider class of non-commutative algebras, including all non-trivial matrix algebras over any field of characteristic 0, group algebras of all non-abelian finite groups over algebraically closed fields of characteristic 0, the quaternion algebra and the Clifford algebras. As a result, we obtain more compelling evidence for the essential role played by commutativity in the efficient computation of the determinant. The key to our approach is a characterization of non-commutative algebras by means of the polynomial identities that they satisfy. Extending Nisan's lower bound framework, we find that any reduction in complexity compared to the free algebra must arise from the ability of the identities to reduce the rank of certain naturally associated matrices. Using results from the theory of algebras with polynomial identities, we are able to show that none of the identities of the above classes of algebras is able to achieve such a rank reduction.

Details

STOC Conference 2004 Conference Paper

Low distortion maps between point sets

  • Claire Mathieu
  • Yuval Rabani
  • Alistair Sinclair

We initiate the study of the minimum distortion problem: given as input two n-point metric spaces, find a bijection between them with minimum distortion. This is an abstraction of certain geometric problems in shape and image matching, and is also a natural variation and extension of the fundamental problems of graph isomorphism and bandwidth. Our focus is on algorithms that find an optimal (or near-optimal) bijection when the distortion is fairly small. We present a polynomial time algorithm that finds an optimal bijection between two line metrics, provided the distortion is less than 3+2√2. We also give a parameterized polynomial time algorithm that finds an optimal bijection between an arbitrary unweighted graph metric and a bounded-degree tree metric.

Details

FOCS Conference 2004 Conference Paper

Shuffling by Semi-Random Transpositions

  • Elchanan Mossel
  • Yuval Peres
  • Alistair Sinclair

In the cyclic-to-random shuffle, we are given n cards arranged in a circle. At step k, we exchange the kth card along the circle with a uniformly chosen random card. The problem of determining the mixing time of the cyclic-to-random shuffle was raised by Aldous and Diaconis in 1986. Mironov used this shuffle as a model for the cryptographic system known as RC4, and proved an upper bound of O(n log n) for the mixing time. We prove a matching lower bound, thus establishing that the mixing time is indeed of order /spl Theta/(n log n). We also prove an upper bound of O(n log n) for the mixing time of any "semirandom transposition shuffle", i. e. , any shuffle in which a random card is exchanged with another card chosen according to an arbitrary (deterministic or random) rule. To prove our lower bound, we exhibit an explicit complex-valued test function which typically takes very different values for permutations arising from few iterations of the cyclic-to-random-shuffle and for uniform random permutations. Perhaps surprisingly, the proof hinges on the fact that the function e/sup z/ - 1 has nonzero fixed points in the complex plane. A key insight from our work is the importance of complex analysis tools for uncovering structure in nonreversible Markov chains.

Details

FOCS Conference 2003 Conference Paper

The Ising Model on Trees: Boundary Conditions and Mixing Time

  • Fabio Martinelli
  • Alistair Sinclair
  • Dror Weitz

We give the first comprehensive analysis of the effect of boundary conditions on the mixing time of the Glauber dynamics for the Ising model. Specifically, we show that the mixing time on an n-vertex regular tree with (+) boundary remains O(n log n) at all temperatures (in contrast to the free boundary case, where the mixing time is not bounded by any fixed polynomial at low temperatures). We also show that this bound continues to hold in the presence of an arbitrary external field. Our results are actually stronger, and provide tight bounds on the log-Sobolev constant and the spectral gap of the dynamics. In addition, our methods yield simpler proofs and stronger results for the mixing time in the regime where it is insensitive to the boundary condition. Our techniques also apply to a much wider class of models, including those with hard constraints like the antiferromagnetic Potts model at zero temperature (colorings) and the hard-core model (independent sets).

Details

STOC Conference 2002 Conference Paper

Clifford algebras and approximating the permanent

  • Steve Chien
  • Lars Eilstrup Rasmussen
  • Alistair Sinclair

(MATH) We study approximation algorithms for the permanent of an n x n (0,1) matrix A based on the following simple idea: obtain a random matrix B by replacing each 1-entry of A independently by ± e , where e is a random basis element of a suitable algebra; then output |det( B )| 2 . This estimator is always unbiased, but it may have exponentially large variance. In our first main result we show that, if we take the algebra to be a Clifford algebra of dimension polynomial in n , then we get an estimator with small variance. Hence only a constant number of trials suffices to estimate the permanent to good accuracy. The idea of using Clifford algebras is a natural extension of earlier work by Godsil and Gutman, Karmarkar et al. , and Barvinok, who used the real numbers, complex numbers and quaternions respectively.(MATH) The above result implies that, in principle, this approach gives a fully-polynomial randomized approximation scheme for the permanent, provided |det( B )| 2 can be efficiently computed in the Clifford algebras. Since these algebras are non-commutative it is not clear how to do this. However, our second main result shows how to compute in polynomial time an estimator with the same mean and variance over the 4-dimensional algebra (which is the quaternions, and is non-commutative); in addition to providing some hope that the computations can be performed in higher dimensions, this quaternion algorithm provides an exponential improvement in the variance over that of the 2-dimensional complex version studied by Karmarkar et al .

Details

FOCS Conference 1999 Conference Paper

Cuts, Trees and l 1 -Embeddings of Graphs

  • Anupam Gupta 0001
  • Ilan Newman
  • Yuri Rabinovich
  • Alistair Sinclair

Motivated by many recent algorithmic applications, the paper aims to promote a systematic study of the relationship between the topology of a graph and the metric distortion incurred where the graph is embedded into l/sub 1/ space. The main results are: 1. Explicit constant-distortion embeddings of all series parallel graphs, and all graphs with bounded Euler number. These are thus the first natural families known to have constant distortion (strictly greater than 1). Using the above embeddings, we obtain algorithms to approximate the sparsest cut in such graphs to within a constant factor. 2) A constant-distortion embedding of outerplanar graphs into the restricted class of l/sub 1/-metrics known as "dominating tree metrics". We also show a lower bound of /spl Omega/(log n) on the distortion for embeddings of series-parallel graphs into (distributions over) dominating tree metrics. This shows, surprisingly, that such metrics approximate distances very poorly even for families of graphs with low tree width, and excludes the possibility of using them to explore the finer structure of l/sub 1/-embeddability.

Details

FOCS Conference 1999 Conference Paper

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

  • Ben Morris 0001
  • Alistair Sinclair

We solve an open problem concerning the mixing time of a symmetric random walk on an n-dimensional cube truncated by a hyperplane, showing that it is polynomial in n. As a consequence, we obtain a full-polynomial randomized approximation scheme for counting the feasible solutions of a 0-1 knapsack problem. The key ingredient in our analysis is a combinatorial construction we call a "balanced almost uniform permutation", which seems to be of independent interest.

Details

FOCS Conference 1998 Conference Paper

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

  • Yuval Rabani
  • Alistair Sinclair
  • Rolf Wanka

We develop a general technique for the quantitative analysis of iterative distributed load balancing schemes. We illustrate the technique by studying two simple, intuitively appealing models that are prevalent in the literature: the diffusive paradigm, and periodic balancing circuits (or the dimension exchange paradigm). It is well known that such load balancing schemes can be roughly modeled by Markov chains, but also that this approximation can be quite inaccurate. Our main contribution is an effective way of characterizing the deviation between the actual loads and the distribution generated by a related Markov chain, in terms of a natural quantity which we call the local divergence. We apply this technique to obtain bounds on the number of rounds required to achieve coarse balancing in general networks, cycles and meshes in these models. For balancing circuits, we also present bounds for the stronger requirement of perfect balancing, or counting.

Details

FOCS Conference 1995 Conference Paper

Markov Chain Algorithms for Planar Lattice Structures (Extended Abstract)

  • Michael Luby
  • Dana Randall
  • Alistair Sinclair

Consider the following Markov chain, whose states are all domino tilings of a 2n/spl times/2n chessboard: starting from some arbitrary tiling, pick a 2/spl times/2 window uniformly at random. If the four squares appearing in this window are covered by two parallel dominoes, rotate the dominoes in place. Repeat many times. This process is used in practice to generate a random tiling and is a key tool in the study of the combinatorics of tilings and the behavior of dimer systems in statistical physics. Analogous Markov chains are used to randomly generate other structures on various two-dimensional lattices. The paper presents techniques which prove for the first time that, in many interesting cases, a small number of random moves suffice to obtain a uniform distribution.

Details

FOCS Conference 1992 Conference Paper

Quadratic Dynamical Systems (Preliminary Version)

  • Yuri Rabinovich
  • Alistair Sinclair
  • Avi Wigderson

The paper promotes the study of computational aspects, primarily the convergence rate, of nonlinear dynamical systems from a combinatorial perspective. The authors identify the class of symmetric quadratic systems. Such systems have been widely used to model phenomena in the natural sciences, and also provide an appropriate framework for the study of genetic algorithms in combinatorial optimisation. They prove several fundamental general properties of these systems, notably that every trajectory converges to a fixed point. They go on to give a detailed analysis of a quadratic system defined in a natural way on probability distributions over the set of matchings in a graph. In particular, they prove that convergence to the limit requires only polynomial time when the graph is a tree. This result demonstrates that such systems, though nonlinear, are amenable to quantitative analysis. >

Details

TCS Journal 1990 Journal Article

Fast uniform generation of regular graphs

  • Mark Jerrum
  • Alistair Sinclair

An algorithm is presented which randomly selects a labelled graph with specified vertex degrees from a distribution which is arbitrarily close to uniform. The algorithm is based on simulation of a rapidly convergent stochastic process, and runs in polynomial time for a wide class of degree sequences, including all regular sequences and all n-vertex sequences with no degree exceeding √n/2. The algorithm can be extended to cover the selection of a graph with given degree sequence which avoids a specified set of edges. One consequence of this extension is the existence of a polynomial-time algorithm for selecting an f-factor in a sufficiently dense graph. A companion algorithm for counting degree-constrained graphs is also presented; this algorithm has exactly the same range of validity as the one for selection.

Details DOI

I&C Journal 1989 Journal Article

Approximate counting, uniform generation and rapidly mixing Markov chains

  • Alistair Sinclair
  • Mark Jerrum

The paper studies effective approximate solutions to combinatorial counting and unform generation problems. Using a technique based on the simulation of ergodic Markov chains, it is shown that, for self-reducible structures, almost uniform generation is possible in polynomial time provided only that randomised approximate counting to within some arbitrary polynomial factor is possible in polynomial time. It follows that, for self-reducible structures, polynomial time randomised algorithms for counting to within factors of the form (1 + n −β ) are available either for all β ϵ R or for no β ϵ R. A substantial part of the paper is devoted to investigating the rate of convergence of finite ergodic Markov chains, and a simple but powerful characterisation of rapid convergence for a broad class of chains based on a structural property of the underlying graph is established. Finally, the general techniques of the paper are used to derive an almost uniform generation procedure for labelled graphs with a given degree sequence which is valid over a much wider range of degrees than previous methods: this in turn leads to randomised approximate counting algorithms for these graphs with very good asymptotic behaviour.

Details DOI

STOC Conference 1988 Conference Paper

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

  • Mark Jerrum
  • Alistair Sinclair

The permanent of an n x n matrix A with 0-1 entries a ij is defined by per ( A ) = Σ/σ Π/ n -1/ i = ο a i σ( i ) , where the sum is over all permutations σ of [ n ] = {0, …, n - 1}. Evaluating per ( A ) is equivalent to counting perfect matchings (1-factors) in the bipartite graph G = ( V 1 , V 2 , E ), where V 1 = V 2 = [ n ] and ( i , j ) ∈ E iff a ij = 1. The permanent function arises naturally in a number of fields, including algebra, combinatorial enumeration and the physical sciences, and has been an object of study by mathematicians for many years (see [14] for background). Despite considerable effort, and in contrast with the syntactically very similar determinant, no efficient procedure for computing this function is known.

Details
v2026.09.13