We show that the flip chain for non-crossing spanning trees of n+1 points in convex position mixes in time O(n⁸log n). We use connections between Fuss-Catalan structures to construct a comparison argument with a chain similar to Wilson’s lattice path chain (Wilson 2004).

We present a simple algorithm that perfectly samples configurations from the unique Gibbs measure of a spin system on a potentially infinite graph $G$. The sampling algorithm assumes strong spatial mixing together with subexponential growth of $G$. It produces a finite window onto a perfect sample from the Gibbs distribution. The run-time is linear in the size of the window, in particular it is constant for each vertex.

Jerrum, Sinclair, and Vigoda [ J. ACM, 51 (2004), pp. 671--697] showed that the permanent of any square matrix can be estimated in polynomial time. This computation can be viewed as approximating the partition function of edge-weighted matchings in a bipartite graph. Equivalently, this may be viewed as approximating the partition function of vertex-weighted independent sets in the line graph of a bipartite graph. Line graphs of bipartite graphs are perfect graphs and are known to be precisely the class of (claw, diamond, odd hole)-free graphs. So how far does the result of Jerrum, Sinclair, and Vigoda extend? We first show that it extends to (claw, odd hole)-free graphs, and then show that it extends to the even larger class of (fork, odd hole)-free graphs. Our techniques are based on graph decompositions, which have been the focus of much recent work in structural graph theory, and on structural results of Chvátal and Sbihi [ J. Combin. Theory Ser. B, 44 (1988)], Maffray and Reed [ J. Combin. Theory Ser. B, 75 (1999)], and Lozin and Milanič [ J. Discrete Algorithms, 6 (2008), pp. 595--604].

We study the mixing time of random walks on small-world networks modelled as follows: starting with the 2-dimensional periodic grid, each pair of vertices {u,v} with distance d> 1 is added as a “long-range” edge with probability proportional to d -r , where r≥ 0 is a parameter of the model. Kleinberg [33{ studied a close variant of this network model and proved that the (decentralised) routing time is O((log n ) 2 ) when r =2 and n Ω (1) when r≠ 2. Here, we prove that the random walk also undergoes a phase transition at r=2 , but in this case, the phase transition is of a different form. We establish that the mixing time is ϴ (log n) for r< 2, O((log n ) 4 ) for r =2, and n Ω (1) for r> 2.

We propose a new algorithmic framework, called partial rejection sampling , to draw samples exactly from a product distribution, conditioned on none of a number of bad events occurring. Our framework builds new connections between the variable framework of the Lovász Local Lemma and some classical sampling algorithms such as the cycle-popping algorithm for rooted spanning trees. Among other applications, we discover new algorithms to sample satisfying assignments of k -CNF formulas with bounded variable occurrences.

We give a fully polynomial-time randomized approximation scheme (FPRAS) for the all-terminal network reliability problem, which is to determine the probability that in an undirected graph, assuming each edge fails independently, the remainder of the graph is still connected. Our main contribution is to confirm a conjecture by Gorodezky and Pak [ Random Structures Algorithms, 44 (2014), pp. 201--223] that the expected running time of the “cluster-popping” algorithm in bidirected graphs is bounded by a polynomial in the size of the input.

We give a fully polynomial-time randomized approximation scheme (FPRAS) for the all-terminal network reliability problem, which is to determine the probability that, in a undirected graph, assuming each edge fails independently, the remaining graph is still connected. Our main contribution is to confirm a conjecture by Gorodezky and Pak (Random Struct. Algorithms, 2014), that the expected running time of the "cluster-popping" algorithm in bi-directed graphs is bounded by a polynomial in the size of the input.

We present a perfect simulation of the hard disks model via the partial rejection sampling method. Provided the density of disks is not too high, the method produces exact samples in O(log n) rounds, where n is the expected number of disks. The method extends easily to the hard spheres model in d>2 dimensions. In order to apply the partial rejection method to this continuous setting, we provide an alternative perspective of its correctness and run-time analysis that is valid for general state spaces.

We show for the first time that the mixing time of Glauber (single edge update) dynamics for the random cluster model at q = 2 is bounded by a polynomial in the size of the underlying graph. As a consequence, the Swendsen- Wang algorithm for the ferromagnetic Ising model at any temperature has the same polynomial mixing time bound.

We propose a new algorithmic framework, called “partial rejection sampling”, to draw samples exactly from a product distribution, conditioned on none of a number of bad events occurring. Our framework builds (perhaps surprising) new connections between the variable framework of the Lovász Local Lemma and some clas- sical sampling algorithms such as the “cycle-popping” algorithm for rooted spanning trees by Wilson. Among other applications, we discover new algorithms to sample satisfying assignments of k-CNF formulas with bounded variable occurrences.

We study a simple Markov chain, the switch chain, on the set of all perfect matchings in a bipartite graph. This Markov chain was proposed by Diaconis, Graham and Holmes as a possible approach to a sampling problem arising in Statistics. We ask: for which hereditary classes of graphs is the Markov chain ergodic and for which is it rapidly mixing? We provide a precise answer to the ergodicity question and close bounds on the mixing question. We show for the first time that the mixing time of the switch chain is polynomial in the case of monotone graphs, a class that includes examples of interest in the statistical setting.

We examine the computational complexity of approximately counting the list H-colourings of a graph. We discover a natural graph-theoretic trichotomy based on the structure of the graph H. If H is an irreflexive bipartite graph or a reflexive complete graph then counting list H-colourings is trivially in polynomial time. Otherwise, if H is an irreflexive bipartite permutation graph or a reflexive proper interval graph then approximately counting list H-colourings is equivalent to #BIS, the problem of approximately counting independent sets in a bipartite graph. This is a well-studied problem which is believed to be of intermediate complexity - it is believed that it does not have an FPRAS, but that it is not as difficult as approximating the most difficult counting problems in #P. For every other graph H, approximately counting list H-colourings is complete for #P with respect to approximation-preserving reductions (so there is no FPRAS unless NP = RP). Two pleasing features of the trichotomy are (i) it has a natural formulation in terms of hereditary graph classes, and (ii) the proof is largely self-contained and does not require any universal algebra (unlike similar dichotomies in the weighted case). We are able to extend the hardness results to the bounded-degree setting, showing that all hardness results apply to input graphs with maximum degree at most 6.

We study a simple Markov chain, the switch chain, on the set of all perfect matchings in a bipartite graph. This Markov chain was proposed by Diaconis, Graham and Holmes as a possible approach to a sampling problem arising in Statistics. They considered several classes of graphs, and conjectured that the switch chain would mix rapidly for graphs in these classes. Here we settle their conjecture almost completely. We ask: for which graph classes is the Markov chain ergodic and for which is it rapidly mixing? We provide a precise answer to the ergodicity question and close bounds on the mixing question. We show for the first time that the mixing time of the switch chain is polynomial in the class of monotone graphs. This class was identified by Diaconis, Graham and Holmes as being of particular interest in the statistical setting.

We consider the problem of counting $H$-colorings from an input graph $G$ to a target graph $H$. We show that if $H$ is any fixed graph without trivial components, then the problem is as hard as the well-known problem $\#\mathrm{BIS}$, which is the problem of (approximately) counting independent sets in a bipartite graph. $\#\mathrm{BIS}$ is a complete problem in an important complexity class for approximate counting, and is believed not to have a fully polynomial randomized approximation scheme (FPRAS). If this is so, then our result shows that for every graph $H$ without trivial components, the $H$-coloring counting problem has no FPRAS. This problem was studied a decade ago by Goldberg, Kelk, and Paterson. They were able to show that approximately sampling $H$-colorings is $\#\mathrm{BIS}$-hard, but it was not known how to get the result for approximate counting. Our solution builds on nonconstructive ideas using the work of Lovász.

Counting independent sets on bipartite graphs (#BIS) is considered a canonical counting problem of intermediate approximation complexity. It is conjectured that #BIS neither has an FPRAS nor is as hard as #SAT to approximate. We study #BIS in the general framework of two-state spin systems in bipartite graphs. Such a system is parameterized by three numbers (beta,gamma,lambda), where beta (respectively gamma) represents the weight of an edge (or "interaction strength") whose endpoints are of the same 0 (respectively 1) spin, and lambda is the weight of a 1 vertex, also known as an "external field". By convention, the edge weight with unequal 0/1 end points and the vertex weight with spin 0 are both normalized to 1. The partition function of the special case beta=1, gamma=0, and lambda=1 counts the number of independent sets. We define two notions, nearly-independent phase-correlated spins and symmetry breaking. We prove that it is #BIS-hard to approximate the partition function of any two-spin system on bipartite graphs supporting these two notions. As a consequence, we show that #BIS on graphs of degree at most 6 is as hard to approximate as #BIS~without degree bound. The degree bound 6 is the best possible as Weitz presented an FPTAS to count independent sets on graphs of maximum degree 5. This result extends to the hard-core model and to other anti-ferromagnetic two-spin models. In particular, for all antiferromagnetic two-spin systems, namely those satisfying beta*gamma<1, we prove that when the infinite (Delta-1)-ary tree lies in the non-uniqueness region then it is #BIS-hard to approximate the partition function on bipartite graphs of maximum degree Delta, except for the case beta=gamma and lambda=1. The exceptional case is precisely the antiferromagnetic Ising model without an external field, and we show that it has an FPRAS on bipartite graphs. Our inapproximability results match the approximability results of Li et al., who presented an FPTAS for general graphs of maximum degree Delta when the parameters lie in the uniqueness region.

We study the complexity of computing the sign of the Tutte polynomial of a graph. As there are only three possible outcomes (positive, negative, and zero), this seems at first sight more like a decision problem than a counting problem. Surprisingly, however, there are large regions of the parameter space for which computing the sign of the Tutte polynomial is actually \#P-hard. As a trivial consequence, approximating the polynomial is also \#P-hard in this case. Thus, approximately evaluating the Tutte polynomial in these regions is as hard as exactly counting the satisfying assignments to a CNF Boolean formula. For most other points in the parameter space, we show that computing the sign of the polynomial is in FP, whereas approximating the polynomial can be done in polynomial time with an NP oracle. As a special case, we completely resolve the complexity of computing the sign of the chromatic polynomial---this is easily computable at q=2 and when $q\leq 32/27$, and is NP-hard to compute for all other values of the parameter q.

We study the complexity of approximation for a weighted counting constraint satisfaction problem #CSP(F). In the conservative case, where F contains all unary functions, a classification is known for the Boolean domain. We give a classification for problems with general finite domain. We define weak log-modularity and weak log-supermodularity, and show that #CSP(F) is in FP if F is weakly log-modular. Otherwise, it is at least as hard to approximate as #BIS, counting independent sets in bipartite graphs, which is believed to be intractable. We further sub-divide the #BIS-hard case. If F is weakly log-supermodular, we show that #CSP(F) is as easy as Boolean log-supermodular weighted #CSP. Otherwise, it is NP-hard to approximate. Finally, we give a trichotomy for the arity-2 case. Then, #CSP(F) is in FP, is #BIS-equivalent, or is equivalent to #SAT, the problem of approximately counting satisfying assignments of a CNF Boolean formula.

An important tool in the study of the complexity of Constraint Satisfaction Problems (CSPs) is the notion of a relational clone, which is the set of all relations expressible using primitive positive formulas over a particular set of base relations. Post's lattice gives a complete classification of all Boolean relational clones, and this has been used to classify the computational difficulty of CSPs. Motivated by a desire to understand the computational complexity of (weighted) counting CSPs, we develop an analogous notion of functional clones and study the landscape of these clones. One of these clones is the collection of log-supermodular (lsm) functions, which turns out to play a significant role in classifying counting CSPs. In the conservative case (where all nonnegative unary functions are available), we show that there are no functional clones lying strictly between the clone of lsm functions and the total clone (containing all functions). Thus, any counting CSP that contains a single nontrivial non-lsm function is computationally as hard to approximate as any problem in #P. Furthermore, we show that any nontrivial functional clone (in a sense that will be made precise) contains the binary function “implies”. As a consequence, in the conservative case, all nontrivial counting CSPs are as hard to approximate as #BIS, the problem of counting independent sets in a bipartite graph. Given the complexity-theoretic results, it is natural to ask whether the “implies” clone is equivalent to the clone of lsm functions. We use the Möbius transform and the Fourier transform to show that these clones coincide precisely up to arity 3. It is an intriguing open question whether the lsm clone is finitely generated. Finally, we investigate functional clones in which only restricted classes of unary functions are available.

We investigate the computational difficulty of approximating the partition function of the ferromagnetic Ising model on a regular matroid. Jerrum and Sinclair have shown that there is a fully polynomial randomized approximation scheme (FPRAS) for the class of graphic matroids. On the other hand, the authors have previously shown, subject to a complexity-theoretic assumption, that there is no FPRAS for the class of binary matroids, which is a proper superset of the class of graphic matroids. In order to map out the region where approximation is feasible, we focus on the class of regular matroids, an important class of matroids which properly includes the class of graphic matroids and is properly included in the class of binary matroids. Using Seymour's decomposition theorem, we give an FPRAS for the class of regular matroids.

Motivated by a desire to understand the computational complexity of counting constraint satisfaction problems (counting CSPs), particularly the complexity of approximation, we study functional clones of functions on the Boolean domain, which are analogous to the familiar relational clones constituting Post's lattice. One of these clones is the collection of log-supermodular (lsm) functions, which turns out to play a significant role in classifying counting CSPs. In our study, we assume that non-negative unary functions (weights) are available. Given this, we prove that there are no functional clones lying strictly between the clone of lsm functions and the total clone (containing all functions). Thus, any counting CSP that contains a single nontrivial non-lsm function is computationally as hard as any problem in #P. Furthermore, any non-trivial functional clone (in a sense that will be made precise below) contains the binary function "implies". As a consequence, all non-trivial counting CSPs (with non-negative unary weights assumed to be available) are computationally at least as difficult as #BIS, the problem of counting independent sets in a bipartite graph. There is empirical evidence that #BIS is hard to solve, even approximately.

We provide evidence that it is computationally difficult to approximate the partition function of the ferromagnetic q -state Potts model when q > 2. Specifically, we show that the partition function is hard for the complexity class #RHPi under approximation-preserving reducibility. Thus, it is as hard to approximate the partition function as it is to find approximate solutions to a wide range of counting problems, including that of determining the number of independent sets in a bipartite graph. Our proof exploits the first-order phase transition of the “random cluster” model, which is a probability distribution on graphs that is closely related to the q -state Potts model.

Partition functions, also known as homomorphism functions, form a rich family of graph invariants that contain combinatorial invariants such as the number of k-colorings or the number of independent sets of a graph and also the partition functions of certain “spin glass” models of statistical physics such as the Ising model. Building on earlier work by Dyer and Greenhill [Random Structures Algorithms, 17 (2000), pp. 260–289] and Bulatov and Grohe [Theoret. Comput. Sci., 348 (2005), pp. 148–186], we completely classify the computational complexity of partition functions. Our main result is a dichotomy theorem stating that every partition function is either computable in polynomial time or #P-complete. Partition functions are described by symmetric matrices with real entries, and we prove that it is decidable in polynomial time in terms of the matrix whether a given partition function is in polynomial time or #P-complete. While in general it is very complicated to give an explicit algebraic or combinatorial description of the tractable cases, for partition functions described by Hadamard matrices (these turn out to be central in our proofs) we obtain a simple algebraic tractability criterion, which says that the tractable cases are those “representable” by a quadratic polynomial over the field $\mathbb{F}_2$.

\emph{Partition functions}, also known as \emph{homomorphism functions}, form a rich family of graph invariants that contain combinatorial invariants such as the number of $k$-colourings or the number of independent sets of a graph and also the partition functions of certain ``spin glass'' models of statistical physics such as the Ising model. Building on earlier work by Dyer and Greenhill (2000) and Bulatov and Grohe (2005), we completely classify the computational complexity of partition functions. Our main result is a dichotomy theorem stating that every partition function is either computable in polynomial time or \#P-complete. Partition functions are described by symmetric matrices with real entries, and we prove that it is decidable in polynomial time in terms of the matrix whether a given partition function is in polynomial time or \#P-complete. While in general it is very complicated to give an explicit algebraic or combinatorial description of the tractable cases, for partition functions described by a Hadamard matrices --- these turn out to be central in our proofs --- we obtain a simple algebraic tractability criterion, which says that the tractable cases are those ``representable'' by a quadratic polynomial over the field $\ensuremath{\mathbb{F}_2}$.

This paper gives a dichotomy theorem for the complexity of computing the partition function of an instance of a weighted Boolean constraint satisfaction problem. The problem is parameterized by a finite set $\mathcal{F}$ of nonnegative functions that may be used to assign weights to the configurations (feasible solutions) of a problem instance. Classical constraint satisfaction problems correspond to the special case of 0,1-valued functions. We show that computing the partition function, i.e., the sum of the weights of all configurations, is $\text{{\sf FP}}^{\text{{\sf#P}}}$-complete unless either (1) every function in $\mathcal{F}$ is of “product type,” or (2) every function in $\mathcal{F}$ is “pure affine.” In the remaining cases, computing the partition function is in P.

The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes many interesting properties of the graph. We study the complexityof the following problem, for rationals x and y: take as input a graph G, and output a value which is a good approximation to T(G;x,y). We are interested in determining for which points (x,y) there is a fullypolynomial randomised approximation scheme (FPRAS) for T(G;x,y). Our main contribution is a substantial widening of the region known to benon-FPRASable.

We consider Glauber dynamics on finite spin systems. The mixing time of Glauber dynamics can be bounded in terms of the influences of sites on each other. We consider three parameters bounding these influences: α, the total influence on a site, as studied by Dobrushin; α′, the total influence of a site, as studied by Dobrushin and Shlosman; and α″, the total influence of a site in any given context, which is related to the path-coupling method of Bubley and Dyer. It is known that if any of these parameters is less than 1 then random-update Glauber dynamics (in which a randomly chosen site is updated at each step) is rapidly mixing. It is also known that the Dobrushin condition α < 1 implies that systematic-scan Glauber dynamics (in which sites are updated in a deterministic order) is rapidly mixing. This paper studies two related issues, primarily in the context of systematic scan: (1) the relationship between the parameters α, α′ and α″, and (2) the relationship between proofs of rapid mixing using Dobrushin uniqueness (which typically use analysis techniques) and proofs of rapid mixing using path coupling. We use matrix balancing to show that the Dobrushin–Shlosman condition α′ < 1 implies rapid mixing of systematic scan. An interesting question is whether the rapid mixing results for scan can be extended to the α = 1 or α′ = 1 case. We give positive results for the rapid mixing of systematic scan for certain α = 1 cases. As an application, we show rapid mixing of systematic scan (for any scan order) for heat-bath Glauber dynamics for properq-colourings of a degree-Δ graphGwhenq≥ 2Δ.

We consider the problem of sampling almost uniformly from the set of contingency tables with given row and column sums, when the number of rows is a constant. Cryan and Dyer [J. Comput. System Sci., 67 (2003), pp. 291-310] have recently given a fully polynomial randomized approximation scheme (fpras) for the related counting problem, which employs Markov chain methods indirectly. They leave open the question as to whether a natural Markov chain on such tables mixes rapidly. Here we show that the "2 x 2 heat-bath" Markov chain is rapidly mixing. We prove this by considering first a heat-bath chain operating on a larger window. Using techniques developed by Morris [Random Walks in Convex Sets, Ph.D. thesis, Department of Statistics, University of California, Berkeley, CA, 2000] and Morris and Sinclair [SIAM J. Comput., 34 (2004), pp. 195-226] for the multidimensional knapsack problem, we show that this chain mixes rapidly. We then apply the comparison method of Diaconis and Saloff-Coste [Ann. Appl. Probab., 3 (1993), pp. 696-730] to show that the 2 x 2 chain is also rapidly mixing.

We present a polynomial-time randomized algorithm for estimating the permanent of an arbitrary n × n matrix with nonnegative entries. This algorithm---technically a "fully-polynomial randomized approximation scheme"---computes an approximation that is, with high probability, within arbitrarily small specified relative error of the true value of the permanent.

We study contention-resolution protocols for multiple-access channels. We show that every backoff protocol is transient if the arrival rate, $\lambda$, is at least 0.42 and that the capacity of every backoff protocol is at most 0.42. Thus, we show that backoff protocols have (provably) smaller capacity than full-sensing protocols. Finally, we show that the corresponding results, with the larger arrival bound of 0.531, also hold for every acknowledgment-based protocol.

We consider the problem of sampling almost uniformly from the set of contingency tables with given row and column sums, when the number of rows is a constant. (2002) have recently given a fully polynomial randomized approximation scheme (fpras) for the related counting problem, which only employs Markov chain methods indirectly. But they leave open the question as to whether a natural Markov chain on such tables mixes rapidly. Here we answer this question in the affirmative, and hence provide a very different proof of the main result of Cryan and Dyer. We show that the "2 /spl times/ 2 heat-bath" Markov chain is rapidly mixing. We prove this by considering first a heat-bath chain operating on a larger window. Using techniques developed by Morris and Sinclair (2002) (see also Morris (2002)) for the multidimensional knapsack problem, we show that this chain mixes rapidly. We then apply the comparison method of Diaconis and Saloff-Coste (1993) to show that the 2 /spl times/ 2 chain is rapidly mixing. As part of our analysis, we give the first proof that the 2 /spl times/ 2 chain mixes in time polynomial in the input size when both the number of rows and the number of columns is constant.

We compute tight lower bounds on the log-Sobolev constant of a class of inductively defined Markov chains, which contains the bases-exchange walks for balanced matroids studied by Feder and Mihail. As a corollary, we obtain improved upper bounds for the mixing time of a variety of Markov chains. An example: the "natural" random walk on spanning trees of a graph G as proposed by Broder - which has been studied by a number of authors - mixes in time O(mn log n), where n is the number of vertices of G and m the number of edges. This beats the best previous upper bound on this walk by a factor n/sup 2/.

We prove two results concerning approximate counting of independent sets in graphs with constant maximum degree $\Delta$. The first implies that the Markov chain Monte Carlo technique is likely to fail if $\Delta \geq 6$. The second shows that no fully polynomial randomized approximation scheme can exist for $\Delta \geq 25$, unless $\mathrm{RP}=\mathrm{NP}$.

A new method for analyzing the mixing time of Markov chains is described. This method is an extension of path coupling and involves analyzing the coupling over multiple steps.The expected behavior of the coupling at a certain stopping time is used to bound the expected behavior of the coupling after a fixed number of steps. The new method is applied to analyze the mixing time of the Glauber dynamics for graph colorings. We show that the Glauber dynamics has O(n log(n)) mixing time for triangle-free $\Delta$-regular graphs if k colors are used, where $k\geq (2-\eta)\Delta$, for some small positive constant $\eta$. This is the first proof of an optimal upper bound for the mixing time of the Glauber dynamics for some values of k in the range $k\leq 2\Delta$.

We prove two results concerning approximate counting of independent sets in graphs with constant maximum degree /spl Delta/. The first result implies that the Monte-Carlo Markov chain technique is likely to fail if /spl Delta//spl ges/6. The second shows that no fully polynomial randomized approximation scheme can exist for /spl Delta//spl ges/25, unless P=NP under randomized reductions.

We consider approximate counting of colorings of an n-vertex graph using rapidly mixing Markov chains. It has been shown by Jerrum and by Salas and Sokal that a simple random walk on graph colorings would mix rapidly, provided the number of colors k exceeded the maximum degree $\Delta$ of the graph by a factor of at least 2. We prove that this is not a necessary condition for rapid mixing by considering the simplest case of 5-coloring graphs of maximum degree 3. Our proof involves a computer-assisted proof technique to establish rapid mixing of a new "heat bath" Markov chain on colorings using the method of path coupling. We outline an extension to 7-colorings of triangle-free 4-regular graphs. Since rapid mixing implies approximate counting in polynomial time, we show in contrast that exact counting is unlikely to be possible (in polynomial time). We give a general proof that the problem of exactly counting the number of proper k-colorings of graphs with maximum degree $\Delta$ is $# P$-complete whenever $k\geq 3$ and $\Delta \geq 3$.

We give a polynomial-time algorithm for the following problem: Given a degree sequence in which each degree is bounded from above by a constant, select, uniformly at random, an unlabelled connected multigraph with the given degree sequence. We also give a polynomial-time algorithm for the following related problem: Given a molecular formula, select, uniformly at random, a structural isomer having the given formula.

We describe fully polynomial randomized approximation schemes for the problems of determining the number of Hamilton paths and cycles in an n-vertex graph with minimum degree $(\frac{1}{2}+\a)n$, for any fixed a > 0. We show that the exact counting problems are #P-complete. We also describe fully polynomial randomized approximation schemes for counting paths and cycles of all sizes in such graphs.

Opticalcommunication is likely to significantly speed up parallel computation because the vast bandwidth of the optical medium can be divided to produce communication networks of very high degree. However, the problem of contention in high-degree networks makes the routing problem in these networks theoretically (and practically) difficult. In this paper we examine Valiant's h-relation routing problem, which is a fundamental problem in the theory of parallel computing. The h-relation routing problem arises both in the direct implementation of specific parallel algorithms on distributed-memory machines and in the general simulation of shared-memory models such as the PRAM on distributed-memory machines. In an h-relation routing problem each processor has up to h messages that it wishes to send to other processors and each processor is the destination of at most h messages. We present a lower bound for routing an h-relation (for any h > 1) on a complete optical network of size n. Our lower bound applies to any randomized distributed algorithm for this task. Specifically, we show that the expected number of communication steps required to route an arbitrary h-relation is $\Omega(h + \sqrt{\,\log\log n}\,)$. This is the first known lower bound for this problem which does not restrict the class of algorithms under consideration.

The Swendsen Wang process provides one possible dynamics for the q-state Potts model. Computer simulations of this process are widely used to estimate the expectations of various observables (random variables) of a Potts system in the equilibrium (or Gibbs) distribution. The legitimacy of such simulations depends on the rate of convergence of the process to equilibrium, as measured by the ``mixing time.' ' Empirical observations suggest that the mixing time of the Swendsen Wang process is short in many instances of practical interest, although proofs of this desirable behavior are known only for some very special cases. Nevertheless, we show that there are occasions when the mixing time of the Swendsen Wang process is exponential in the size of the system. This undesirable behavior is related to the phenomenon of first-order phase transitions in Potts systems with q>2 states. KEY WORDS: Ferromagnetic Potts model; first-order phase transition; mixing time; random graph model; Swendsen Wang dynamics.

A quasi-polynomial-time algorithm is presented for sampling almost uniformly at random from then-slice of the languageL(G) generated by an arbitrary context-free grammarG. (Then-slice of a languageLover an alphabetΣis the subsetL∩Σnof words of length exactlyn.) The time complexity of the algorithm isε−2(n |G|)O(log n)where the parameterεbounds the variation of the output distribution from uniform, and |G| is a natural measure of the size of grammarG. The algorithm applies to a class of language sampling problems that includes slices of context-free languages as a proper subclass. For the restricted case of homogeneous languages expressed by regular expressions without Kleene-star, a truly polynomial-time algorithm is presented.

In this paper, we consider the problem of interprocessor communication on parallel computers that have optical communication networks. We consider the completely connected optical-communication parallel computer (OCPC), which has a completely connected optical network, and also the mesh-of-optical-buses parallel computer (MOB-PC), which has a mesh of optical buses as its communication network. The particular communication problem that we study is that of realizing an h-relation. In this problem, each processor has at most h messages to send and at most h messages to receive. It is clear that any 1-relation can be realized in one communication step on an OCPC. However, the best previously known p-processor OCPC algorithm for realizing an arbitrary h-relation for h > 1 requires $\Theta(h + \log p)$ expected communication steps. (This algorithm is due to Valiant and is based on earlier work of Anderson and Miller.) Valiant's algorithm is optimal only for $h=\Omega(\log p)$, and it is an open question of Geréb-Graus and Tsantilas whether there is a faster algorithm for h=o(log p). In this paper, we answer this question in the affirmative and we extend the range of optimality by considering the case in which $h\leq \log p$. In particular, we present a $\Theta(h + \log\log p)$-communication-step randomized algorithm that realizes an arbitrary h-relation on a p-processor OCPC. We show that if $h\leq \log p$, then the failure probability can be made as small as $p^{-\alpha}$ for any positive constant $\alpha$. We use the OCPC algorithm as a subroutine in a $\Theta(h + \log\log p)$-communication-step randomized algorithm that realizes an arbitrary h-relation on a $p\times p$-processor MOB-PC. Once again, we show that if $h\leq \log p$, then the failure probability can be made as small as $p^{-\alpha}$ for any positive constant $\alpha$.

We present a polynomial time algorithm to learn (in Valiant's PAC model) an arbitrarily oriented cube in n-space, given uniformly distributed sample points from it. In fact, we solve the more general problem of learning, in polynomial time, a linear (affine) transformation of a product distribution.

A polynomial-time algorithm is presented for deciding bisimulation equivalence of so-called Basic Parallel Processes: multisets of elementary processes combined by a commutative parallel-composition operator.

A polynomial-time procedure is presented for deciding bisimilarity of normed context-free processes. It follows as a corollary that language equivalence of simple context-free grammars is decidable in polynomial time.>

Optical communication is likely to significantly speed up parallel computation because the vast bandwidth of the optical medium can be divided to produce communication networks of very high degree. However, the problem of contention in high-degree networks makes the routing problem in these networks theoretically (and practically) difficult. In this paper we examine Valiant's h-relation routing problem, which is a fundamental problem in the theory of parallel computing. The h-relation routing problem arises both in the direct implementation of specific parallel algorithms on distributed-memory machines and in the general simulation of shared memory models such as the PRAM on distributed-memory machines. In an h

Suppose there is a three-dimensional table of cross-tabulated nonnegative integer statistics, and suppose that all of the row, column, and “file” sums are revealed together with the values in some of the individual cells in the table. The question arises as to whether, as a consequence, the values contained in some of the other (suppressed) cells can be deduced from the information revealed. The corresponding problem in two dimensions has been comprehensively studied by Gusfield [SIAM J. Comput., 17 (1988), pp. 552–571], who derived elegant polynomial-time algorithms for the identification of any such “compromised” cells, and for calculating the tightest bounds on the values contained in all cells that follow from the information revealed. In this note it is shown, by contrast, that the three-dimensional version of the problem is NP-complete. It is also shown that if the suggested row, column, and file sums for an unknown three-dimensional table are given, with or without the values in some of the cells, the problem of determining whether there exists any table with the given sums is NP-complete. In the course of proving these results, the NP-completeness of some constrained Latin square construction problems, which are of some interest in their own right, is established.

Abstract. The Vapnik-Chervonenkis (V-C) dimension is an important combinatorial tool in the analysis of learning problems in the PAC framework. For polynomial learnability, we seek upper bounds on the V-C dimension that are polynomial in the syntactic complexity of concepts. Such upper bounds are automatic for discrete concept classes, but hitherto little has been known about what general conditions guarantee polynomial bounds on V-C dimension for classes in which concepts and examples are represented by tuples of real numbers. In this paper, we show that for two general kinds of concept class the V-C dimension is polynomially bounded in the number of real numbers used to define a problem instance. One is classes where the criterion for membership of an instance in a concept can be expressed as a formula (in the first-order theory of the reals) with fixed quantification depth and exponentially-bounded length, whose atomic predicates are polynomial inequalities of exponentially-bounded degree. The other is classes where containment of an instance in a concept is testable in polynomial time, assuming we may compute standard arithmetic operations on reals exactly in constant time. Our results show that in the continuous case, as in the discrete, the real barrier to efficient learning in the Occam sense is complexity-theoretic and not information-theoretic. We present examples to show how these results apply to concept classes defined by geometrical figures and neural nets, and derive polynomial bounds on the V-C dimension for these classes. Keywords: Concept learning, information theory, Vapnik-Chervonenkis dimension, Milnor’s theorem 1.

We resolve in the affirmative a question of R.B. Boppana and T. Bui: whether simulated annealing can with high probability and in polynomial time, find the optimal bisection of a random graph an G/sub npr/ when p-r=(/spl Theta/n/sup /spl Delta/-2/) for /spl Delta//spl les/2. (The random graph model G/sub npr/ specifies a "planted" bisection of density r, separating two n/2-vertex subsets of slightly higher density p.) We show that simulated "annealing" at an appropriate fixed temperature (i.e., the Metropolis algorithm) finds the unique smallest bisection in O(n/sup 2+/spl epsi//) steps with very high probability, provided /spl Delta/>11/6. (By using a slightly modified neighborhood structure, the number of steps can be reduced to O(n/sup 1+/spl epsi//).) We leave open the question of whether annealing is effective for /spl Delta/ in the range 3/2>

paper we consider the probcommunication on a Compltd ely Connected Optical Communication Parallel Computer (OCPC).The particular problem we study is that of realizing an h-r-elation.In this problem, each processor has at most h messages to send and at most h messages to receive.It is clear that any 1-relation can be realized in one communication step on an OCPC.However, the best known p-processor OCPC algorithm for realizing an arbitrary h-relation for h > 1 requires @(h + logp) expected communication steps.(This algorithm is due to Valiant and is based on earlier work of Anderson and Miller.) Valiant's algorithm is optimal only for h = f2(log p) and it is an open question of Ger6b-Graus and Tsantilas whether there is a faster algorithm for h = o(logp).In this paper we answer this question in the affirmative by presenting 1

The paper presents a randomised algorithm which evaluates the partition function of an arbitrary ferromagnetic Ising system to any specified degree of accuracy. The running time of the algorithm increases only polynomially with the size of the system (i.e., the number of sites) and a parameter which controls the accuracy of the result. Further approximation algorithms are presented for the mean energy and the mean magnetic moment of ferromagnetic Ising systems. The algorithms are based on Monte Carlo simulation of a suitably defined ergodic Markov chain. The states of the chain are not, as is customary, Ising spin configurations, but spanning subgraphs of the interaction graph of the system. It is shown that the expectations of simple operators on these configurations give numerical information about the partition function and related quantities. The performance guarantees for the algorithms are rigorously derived and rest on the fact that the Markov chain in question is rapidly mixing, i.e., converges to its equilibrium distribution in a polynomial number of steps. This is apparently the first time that rapid mixing has been demonstrated at all temperatures for a Markov chain related to the Ising model.

An approximation algorithm for the permanent of an n*n 0,1-matrix is presented. The algorithm is shown to have worst-case time complexity exp (0(n/sup 1/2/ log/sup 2/ n)). Asymptotically, this represents a considerable improvement over the best existing algorithm, which has worst-case time complexity of the form e/sup theta (n)/.>

A randomised approximation scheme for the permanent of a 0–1s presented. The task of estimating a permanent is reduced to that of almost uniformly generating perfect matchings in a graph; the latter is accomplished by simulating a Markov chain whose states are the matchings in the graph. For a wide class of 0–1 matrices the approximation scheme is fully-polynomial, i.e., runs in time polynomial in the size of the matrix and a parameter that controls the accuracy of the output. This class includes all dense matrices (those that contain sufficiently many 1’s) and almost all sparse matrices in some reasonable probabilistic model for 0–1 matrices of given density. For the approach sketched above to be computationally efficient, the Markov chain must be rapidly mixing: informally, it must converge in a short time to its stationary distribution. A major portion of the paper is devoted to demonstrating that the matchings chain is rapidly mixing, apparently the first such result for a Markov chain with genuinely complex structure. The techniques used seem to have general applicability, and are applied again in the paper to validate a fully-polynomial randomised approximation scheme for the partition function of an arbitrary monomer-dimer system.

We give an Ο(n3·log n) time and Ο(n3) space algorithm for the continuous homotopic one layer routing problem. The main contribution is an extension of the sweep paradigm to a universal cover space of the plane.

The permanent of an n x n matrix A with 0-1 entries aij is defined by per (A) = Σ/σ Π/n-1/i=ο aiσ(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 = (V1, V2, E), where V1 = V2 = [n] and (i,j) ∈ E iff aij = 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.

A construction is presented which, given a fixed undirected graph of low degree and small average path length, yields an infinite sequence of low diameter graphs of increasing order and fixed degree. As examples of the construction, infinite sequences of low diameter graphs are presented with degrees in the range 3 to 30. Expressed as a function of the order of the graphs, the degree 3 sequence has diameter bounded above by 1.4722 log2 N + O(1), and the degree 4 sequence by 0.9083 log2N + O(1).

An O(n2) space representation for permutation groups of degree n is presented. The representation can be constructed in time O(n5), and supports fast membership testing. Applications of the representation to the generation of systems of coset representatives, and of complete block systems, are discussed.

The problem of computing polynomials in certain semmngs is considered.Precise bounds are obtained on the number of multiplications required by straight-hne algorithms which compute such functions as iterated matrix multiplication, iterated convolution, and permanent Usmg these bounds, tt is shown that the use of branching can exponentially speed up computations using the min, + operations, and that subtraction can exponentially speed up arithmetic computations These results can be interpreted as denying the existence of fast "universal" algorithms for computing certain polynomials K~V wol~os AND prmASES artthmeuc complexity, convexity theory, Farkas Lemma, minimax algebra, straight-hne algorithm Categories and SubJect Descriptors: F. 1 1