Each symmetric matrix A defines a graph homomorphism function ZA(⋅), also known as the partition function. We prove that the Bulatov-Grohe dichotomy [4] for ZA(⋅) holds for bounded degree graphs. This resolves a problem that has been open for 15 years. Specifically, we prove that for any nonnegative symmetric matrix A with algebraic entries, either ZA(G) is in polynomial time for all graphs G, or it is #P-hard for bounded degree (and simple) graphs G. We further extend the complexity dichotomy to include nonnegative vertex weights. Additionally, we prove that the #P-hardness part of the dichotomy by Goldberg et al. [12] for ZA(⋅) also holds for simple graphs, where A is any real symmetric matrix.

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 examine the problem of exactly or approximately counting all perfect matchings in hereditary classes of nonbipartite graphs. In particular, we consider the switch Markov chain of Diaconis, Graham, and Holmes. We determine the largest hereditary class for which the chain is ergodic, and define a large new hereditary class of graphs for which it is rapidly mixing. We go on to show that the chain has exponential mixing time for a slightly larger class. We also examine the question of ergodicity of the switch chain in an arbitrary graph. Finally, we give exact counting algorithms for three classes.

For any class C of bipartite graphs, we define quasi-C to be the class of all graphs G such that every bipartition of G belongs to C. This definition is motivated by a generalisation of the switch Markov chain on perfect matchings from bipartite graphs to nonbipartite graphs. The monotone graphs, also known as bipartite permutation graphs and proper interval bigraphs, are such a class of bipartite graphs. We investigate the structure of quasi-monotone graphs and hence construct a polynomial time recognition algorithm for graphs in this class.

We consider an asynchronous voting process on graphs called discordant voting, which can be described as follows. Initially each vertex holds one of two opinions, red or blue. Neighboring vertices with different opinions interact pairwise along an edge. After an interaction both vertices have the same color. The quantity of interest is the time to reach consensus, i.e., the number of steps needed for all vertices have the same color. We show that for a given initial coloring of the vertices, the expected time to reach consensus depends strongly on the underlying graph and the update rule (i.e., push, pull, oblivious).

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 consider an asynchronous voting process on graphs which we call discordant voting, and which can be described as follows. Initially each vertex holds one of two opinions, red or blue say. Neighbouring vertices with different opinions interact pairwise. After an interaction both vertices have the same colour. The quantity of interest is T, the time to reach consensus, i.e. the number of interactions needed for all vertices have the same colour. An edge whose endpoint colours differ (i.e. one vertex is coloured red and the other one blue) is said to be discordant. A vertex is discordant if its is incident with a discordant edge. In discordant voting, all interactions are based on discordant edges. Because the voting process is asynchronous there are several ways to update the colours of the interacting vertices. - Push: Pick a random discordant vertex and push its colour to a random discordant neighbour. - Pull: Pick a random discordant vertex and pull the colour of a random discordant neighbour. - Oblivious: Pick a random endpoint of a random discordant edge and push the colour to the other end point. We show that ET, the expected time to reach consensus, depends strongly on the underlying graph and the update rule. For connected graphs on n vertices, and an initial half red, half blue colouring the following hold. For oblivious voting, ET = (n^2)/4 independent of the underlying graph. For the complete graph Kn, the push protocol has ET = Theta(n*log(n)), whereas the pull protocol has ET = Theta(2^n). For the cycle C_n all three protocols have ET = Theta(n^2). For the star graph however, the pull protocol has ET = O(n^2), whereas the push protocol is slower with ET = Theta(n^2*log(n)). The wide variation in ET for the pull protocol is to be contrasted with the well known model of synchronous pull voting, for which ET = O(n) on many classes of expanders.

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 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.

Bulatov [Proceedings of the $35$th International Colloquium on Automata, Languages and Programming (Part 1), Lecture Notes in Comput. Sci. 5125, Springer, New York, 2008, pp. 646--661] gave a dichotomy for the counting constraint satisfaction problem \#CSP. A problem from \#CSP is characterized by a constraint language $\Gamma\!$, a fixed, finite set of relations over a finite domain $D$. An instance of the problem uses these relations to constrain an arbitrarily large finite set of variables. Bulatov showed that the problem of counting the satisfying assignments of instances of any problem from \#CSP is either in polynomial time (FP) or is \#P-complete. His proof draws heavily on techniques from universal algebra and cannot be understood without a secure grasp of that field. We give an elementary proof of Bulatov's dichotomy, based on succinct representations, which we call frames, of a class of highly structured relations, which we call strongly rectangular. We show that these are precisely the relations which are invariant under a Mal'tsev polymorphism. En route, we give a simplification of a decision algorithm for strongly rectangular constraint languages due to Bulatov and Dalmau [SIAM J. Comput., 36 (2006), pp. 16--27]. We establish a new criterion for the #CSP dichotomy, which we call strong balance, and we prove that this property is decidable. In fact, we establish membership in NP. Thus, we show that the dichotomy is effective, resolving the most important open question concerning the \#CSP dichotomy.

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 present a family of peer-to-peer network protocols that yield regular graph topologies having known Hamilton cycles. These topologics are equivalent, in a well-defined sense, to the random regular graph. As a consequence, we have connectivity deterministically, and logarithmic diameter and expansion properties with high probability. We study the efficacy of certain simple topology-altering operations, designed to introduce randomness. These operations enable the network to self-stabilise when damaged. They resemble the operations used by Cooper, Dyer and Greenhill (2007) for a similar purpose in the case of random regular graphs. There is a link between our protocols and certain combinatorial structures which have been studied previously, in particular discordant permutations and Latin rectangles. We give the first rigorous polynomial mixing-time bounds for natural Markov chains that sample these objects at random. We do so by developing a novel extension to the canonical path technique for bounding mixing times: routing via a random destination. This resembles a technique used by Valiant (1982) for low-congestion routing in hypercubes.

Bulatov (2008) and Dyer and Richerby (2010) have established the following dichotomy for the counting constraint satisfaction problem (#CSP): for any constraint language Gamma, the problem of computing the number of satisfying assignments to constraints drawn from Gamma is either in FP or is #P-complete, depending on the structure of Gamma. The principal question left open by this research was whether the criterion of the dichotomy is decidable. We show that it is; in fact, it is in NP.

The degree of a CSP instance is the maximum number of times that a variable may appear in the scope of constraints. We consider the approximate counting problem for Boolean CSPs with bounded-degree instances, for constraint languages containing the two unary constant relations $\{0\}$ and $\{1\}$. When the maximum degree is at least $25$ we obtain a complete classification of the complexity of this problem. It is exactly solvable in polynomial-time if every relation in the constraint language is affine. It is equivalent to the problem of approximately counting independent sets in bipartite graphs if every relation can be expressed as conjunctions of $\{0\}$, $\{1\}$ and binary implication. Otherwise, there is no FPRAS unless $\NPtime = \RPtime$. For lower degree bounds, additional cases arise in which the complexity is related to the complexity of approximately counting independent sets in hypergraphs.

Bulatov (2008) has given a dichotomy for the counting constraint satisfaction problem, #CSP. A problem from #CSP is characterized by a constraint language γ, which is a fixed, finite set of relations over a finite domain. An instance of the problem uses these relations to constrain the values taken by a finite set of variables. Bulatov showed that, for any fixed γ, the problem of counting the satisfying assignments of instances of any problem from #CSP is either in polynomial time (FP) or #P-complete, according on the structure of the constraint language γ. His proof draws heavily on techniques from universal algebra and cannot be understood without a secure grasp of that field.

We consider the problem of approximately counting integral flows in a network. We show that there is a fully polynomial randomized approximation scheme (FPRAS) based on volume estimation if all capacities are sufficiently large, generalizing a result of Dyer, Kannan, and Mount [Random Structures Algorithms, 10 (1997), pp. 487–506]. We apply this to approximating the number of contingency tables with prescribed cell bounds when the number of rows is constant, but the row sums, column sums, and cell bounds may be arbitrary. We provide an FPRAS for this problem via a combination of dynamic programming and volume estimation. This generalizes an algorithm of Cryan and Dyer [J. Comput. System Sci., 67 (2003), pp. 291–310] for standard contingency tables, but the analysis here is considerably more intricate.

We define a network that relies on its protocol's emergent behaviour to maintain the useful properties of a random regular topology. It does this by spontaneously performing flips in an effort to randomise [15], allowing it to repair damage and to embed new peers without over-complicated joining schema.

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.

It is known that if P and NP are different then there is an infinite hierarchy of different complexity classes that lie strictly between them. Thus, if P ≠ NP, it is not possible to classify NP using any finite collection of complexity classes. This situation has led to attempts to identify smaller classes of problems within NP where dichotomy results may hold: every problem is either in P or is NP-complete. A similar situation exists for counting problems. If P ≠#P, there is an infinite hierarchy in between and it is important to identify subclasses of #P where dichotomy results hold. Graph homomorphism problems are a fertile setting in which to explore dichotomy theorems. Indeed, Feder and Vardi have shown that a dichotomy theorem for the problem of deciding whether there is a homomorphism to a fixed directed acyclic graph would resolve their long-standing dichotomy conjecture for all constraint satisfaction problems. In this article, we give a dichotomy theorem for the problem of counting homomorphisms to directed acyclic graphs. Let H be a fixed directed acyclic graph. The problem is, given an input digraph G , determine how many homomorphisms there are from G to H . We give a graph-theoretic classification, showing that for some digraphs H , the problem is in P and for the rest of the digraphs H the problem is #P-complete. An interesting feature of the dichotomy, which is absent from previously known dichotomy results, is that there is a rich supply of tractable graphs H with complex structure.

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 consider the problem of approximately counting integral flows in a network. We show that there is an fpras based on volume estimation if all capacities are sufficiently large, generalising a result of Dyer, Kannan and Mount (1997). We apply this to approximating the number of contingency tables with prescribed cell bounds when the number of rows is constant, but the row sums, column sums and cell bounds may be arbitrary. We provide an fpras for this problem via a combination of dynamic programming and volume estimation. This generalises an algorithm of Cryan and Dyer (2002) for standard contingency tables, but the analysis here is considerably more intricate.

We give efficient algorithms to sample uniformly, and count approximately, the solutions to a zero-one knapsack problem. The algorithm is based on using dynamic programming to provide a deterministic relative approximation. Then "dart throwing" techniques are used to give arbitrary approximation ratios. We also indicate how further improvements can be obtained using randomized rounding. We extend the approach to several related problems: the m-constraint zero-one knapsack, the general integer knapsack (including its m-constraint version) and contingency tables with constantly many rows.

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 consider the problem of counting the number of contingency tables with given row and column sums. This problem is known to be #P-complete, even when there are only two rows [7]. In this paper we present the first fully-polynomial randomized approximation scheme for counting contingency tables when the number of rows is constant. A novel feature of our algorithm is that it is a hybrid of an exact counting technique with an approximation algorithm, giving two distinct phases. In the first, the columns are partitioned into "small" and "large". We show that the number of contingency tables can be expressed as the weighted sum of a polynomial number of new instances of the problem, where each instance consists of some new row sums and the original large column sums. In the second phase, we show how to approximately count contingency tables when all the column sums are large. In this case, we show that the solution lies in approximating the volume of a single convex body, a problem which is known to be solvable in polynomial time [5].

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}$.

We consider the problem of generating a random q-colouring of a graph G=(V, E). We consider the simple Glauber Dynamics chain. We show that if the maximum degree /spl Delta/>c/sub l/ ln n and the girth g>c/sub 2/ ln ln n (n=|V|), then this chain mixes rapidly provided C/sub 1/, C/sub 2/ are sufficiently large, q/A>/spl beta/, where /spl beta//spl ap/1.763 is the root of /spl beta/=e/sup 1//spl beta//. For this class of graphs, this beats the 11/spl Delta//6 bound of E. Vigoda (1999) for general graphs. We extend the result to random graphs.

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 describe a deterministic parallel algorithm for linear programming in fixed dimension d that takes poly(log log n) time in the common concurrent read concurrent write (CRCW) PRAM model and does optimal O(n) work. In the exclusive read exclusive write (EREW) model, the algorithm runs in O(log n · log log d-1 n ) time. Our algorithm is based on multidimensional search and effective use of approximation algorithms to speed up the basic search in the CRCW model. Our method also yields very fast poly(log log n) algorithms for smallest enclosing sphere and approximate ham-sandwich cuts and an O(log n) time work-optimal algorithm for exact ham-sandwich cuts of separable point sets. For these problems, in particular for fixed-dimensional linear programming, o(log n) time efficient deterministic PRAM algorithms were not known until very recently.

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 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.

This paper gives various (positive and negative) results on the complexity of the problem of computing and approximating mixed volumes of polytopes and more general convex bodies in arbitrary dimension. On the negative side, we present several $#\P$-hardness results that focus on the difference of computing mixed volumes versus computing the volume of polytopes. We show that computing the volume of zonotopes is $#\P$-hard (while each corresponding mixed volume can be computed easily) but also give examples showing that computing mixed volumes is hard even when computing the volume is easy. On the positive side, we derive a randomized algorithm for computing the mixed volumes $$ V(\overbrace{K_1\ld K_1}^{m_1}, \overbrace{K_2,\dots,K_2}^{m_2},\dots,\overbrace{K_s,\dots,K_s}^{m_s}) $$ of well-presented convex bodies $K_1,\dots,K_s$, where $m_1,\dots,m_s \in \N_0$ and $m_1 \geq n-\psi(n)$ with $\psi(n)=o(\frac{\log n}{\log \log n})$. The algorithm is an interpolation method based on polynomial-time randomized algorithms for computing the volume of convex bodies. This paper concludes with applications of our results to various problems in discrete mathematics, combinatorics, computational convexity, algebraic geometry, geometry of numbers, and operations research.

The main technique used in algorithm design for approximating #P-hard counting problems is the Markov chain Monte Carlo method. At the heart of the method is the study of the convergence (mixing) rates of particular Markov chains of interest. In this paper we illustrate a new approach to the coupling technique, which we call path coupling, for bounding mixing rates. Previous applications of coupling have required detailed insights into the combinatorics of the problem at hand, and this complexity can make the technique extremely difficult to apply successfully. Path coupling helps to minimize the combinatorial difficulty and in all cases provides simpler convergence proofs than does the standard coupling method. However the true power of the method is that the simplification obtained may allow coupling proofs which were previously unknown, or provide significantly better bounds than those obtained using the standard method. We apply the path coupling method to several hard combinatorial problems, obtaining new or improved results. We examine combinatorial problems such as graph colouring and TWICE-SAT, and problems from statistical physics, such as the antiferromagnetic Potts model and the hard-core lattice gas model. In each case we provide either a proof of rapid mixing where none was known previously, or substantial simplification of existing proofs with consequent gains in the performance of the resulting algorithms.

The emergence of low latency, high throughput routers means that network locality issues no longer dominate the performance of parallel algorithms. One of the key performance issues is now the even distribution of work across the machine, as the problem size and number of processors increase. This paper describes the implementation of a highly scalable shared queue, supporting the concurrent insertion and deletion of elements. The main characteristics of the queue are that there is no fixed limit on the number of outstanding requests and the performance scales linearly with the number of processors (subject to increasing network latencies). The queue is implemented using a general-purpose computational model, called the WPRAM. The model includes a shared address space which uses weak coherency semantics. The implementation makes extensive use of pairwise synchronization and concurrent atomic operations to achieve scalable performance. The WPRAM is targeted at the class of distributed memory machines which use a scalable interconnection network.

Article Free Access Share on A parallel algorithm for linear programming in fixed dimension Author: Martin Dyer School of Computer Studies, University of Leeds, Leeds, UK School of Computer Studies, University of Leeds, Leeds, UKView Profile Authors Info & Claims SCG '95: Proceedings of the eleventh annual symposium on Computational geometrySeptember 1995 Pages 345–349https://doi.org/10.1145/220279.220316Published:01 September 1995Publication History 11citation274DownloadsMetricsTotal Citations11Total Downloads274Last 12 Months18Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on An optimal randomized planar convex hull algorithm with good empirical performance Authors: Martin Dyer University of Leeds, Leeds LS2 9JT, UK University of Leeds, Leeds LS2 9JT, UKView Profile , Jonathan Nash University of Leeds, Leeds LS2 9JT, UK University of Leeds, Leeds LS2 9JT, UKView Profile , Peter Dew University of Leeds, Leeds LS2 9JT, UK University of Leeds, Leeds LS2 9JT, UKView Profile Authors Info & Claims SPAA '95: Proceedings of the seventh annual ACM symposium on Parallel algorithms and architecturesJuly 1995 Pages 21–26https://doi.org/10.1145/215399.215407Published:20 July 1995Publication History 3citation191DownloadsMetricsTotal Citations3Total Downloads191Last 12 Months11Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We consider the solution of convex programs in a small number of variables but large number of constraints, where all but a small number of the constraints are linear. We develop a general framework for obtaining algorithms for these problems which run in time linear in the number of constraints. We give an application to computing minimum spanning ellipsoids in fixed dimension.

A randomized polynomial-time algorithm for approximating the volume of a convex body K in n -dimensional Euclidean space is presented. The proof of correctness of the algorithm relies on recent theory of rapidly mixing Markov chains and isoperimetric inequalities to show that a certain random walk can be used to sample nearly uniformly from within K .

Some reductions of the computational problem of counting all the integer lattice points in an arbitrary convex polyhedron in a fixed number of dimensions d are considered. It is shown that only odd d need to be studied. In three dimensions the problem is reduced to the computation of Dedekind sums. Hence it is shown that the counting problem in three or four dimensions is in polynomial time. A corresponding reduction of the five-dimensional problem is also examined, but is not shown to lead to polynomial-time algorithms.

We present a randomised polynomial time algorithm for approximating the volume of a convex body K in n-dimensional Euclidean space. The proof of correctness of the algorithm relies on recent theory of rapidly mixing Markov chains and isoperimetric inequalities to show that a certain random walk can be used to sample nearly uniformly from within K.

We show that computing the volume of a polyhedron given either as a list of facets or as a list of vertices is as hard as computing the permanent of a matrix.

The paper is divided into two main sections. The first deals with a multidimensional search technique of Megiddo [J. Assoc. Comput. Mach., 31 (1984), pp. 114–127], and suggests an improvement. The second gives an application of the technique to the Euclidean one-centre problem in $\mathbb{R}^d $. An algorithm of time-complexity $O(3^{(d + 2)^2 } n)$ is derived for this problem. This improves the best previous bound even in the case $d = 2$.

$O(n)$ time algorithms for linear programming problems with two or three variables and n constraints are described. The approach uses convexity, dominance of linear functions and linear-time median finding algorithms. The algorithms improve the previously known best bounds of $O(n\log n)$ time for both of these problems.