Search

Since the celebrated work of Jerrum, Sinclair, and Vigoda [J. ACM, 51 (2004), pp. 671--697], we have known that the permanent of a matrix with entries in {0, 1} can be approximated in randomized polynomial time by using a rapidly mixing Markov chain to sample perfect matchings of a bipartite graph. A separate strand of the literature has pursued the possibility of an alternate, algebraic polynomial-time approximation scheme. These schemes work by replacing each 1 with a random element of an algebra A and considering the determinant of the resulting matrix. In the case where A is noncommutative, this determinant can be defined in several ways. We show that for some estimators based on the conventional determinant, the critical ratio of the second moment to the square of the first--and therefore the number of trials we need to obtain a good estimate of the permanent--is (1 + O(1/d))n when A is the algebra of d X d matrices. These results can be extended to group algebras and semisimple algebras in general. We also study the symmetrized determinant of Barvinok, showing that the resulting estimator has small variance when d is large enough. However, if d is constant--the only case in which an efficient algorithm is known--we show that the critical ratio exceeds 2n/nO(d). Thus our results do not provide a new polynomial-time approximation scheme for the permanent. Indeed, they suggest that the algebraic approach to approximating the permanent faces significant obstacles. We obtain these results using diagrammatic techniques in which we express matrix products as contractions of tensor products. When these matrices are chosen randomly according to the Gaussian distribution, we can evaluate the trace of these products in terms of the cycle structure of a suitably random permutation. In the symmetrized case, our estimates are then derived by a connection with the character theory of the symmetric group. [ABSTRACT FROM AUTHOR]

We construct a small set of explicit linear transformations mapping ℝn to ℝt, where t = O(log(γ-1)ε-2), such that the L2 norm of any vector in ℝn is distorted by at most 1 ± ε in at least a fraction of 1-γ of the transformations in the set. Albeit the tradeoff between the size of the set and the success probability is suboptimal compared with probabilistic arguments, we nevertheless are able to apply our construction to a number of problems. In particular, we use it to construct an ε-sample (or pseudorandom generator) for linear threshold functions on 픔n-1 for ε = o(1). We also use it to construct an ε-sample for spherical digons in 픔n-1 for ε = o(1). This construction leads to an efficient oblivious derandomization of the Goemans-Williamson Max-Cut algorithm and similar approximation algorithms (i.e., we construct a small set of hyperplanes such that for any instance we can choose one of them to generate a good solution). Our technique for constructing an ε-sample for linear threshold functions on the sphere is considerably different than previous techniques that rely on k-wise independent sample spaces. [ABSTRACT FROM AUTHOR]

Let A be a 0/1 matrix of size m × n, and let p be the density of A (i.e., the number of ones divided by m · n). We show that A can be approximated in the cut norm within ϵ · mnp by a sum of cut matrices (of rank 1), where the number of summands is independent of the size m · n of A, provided that A satisfies a certain boundedness condition. This decomposition can be computed in polynomial time. This result extends the work of Frieze and Kannan [Combinatorica, 19 (1999), pp. 175-220] to sparse matrices. As an application, we obtain efficient 1-· approximation algorithms for "bounded" instances of MAX CSP problems. [ABSTRACT FROM AUTHOR]

The vertex cover problem is a classical NP–complete problem for which the best worstcase approximation ratio is 2–o(1). In this paper, we use a collection of simple graph transformations, each of which guarantees an approximation ratio of 3 2 , to find approximate vertex covers for a large collection of randomly generated graphs and test graphs from various sources. The graph reductions are extremely fast, and even though they by themselves are not guaranteed to find a vertex cover, we manage to find a 3 2 –approximate vertex cover for almost every single graph in our collection. The few graphs that we cannot solve have specific structure: they are triangle–free, with a minimum degree of at least 3, a lower bound of n 2 on the optimal vertex cover, and are unlikely to have a large bipartite subgraph. [ABSTRACT FROM AUTHOR]

This paper proposes a compositional approach to verifying whether a large discrete event system is nonblocking. The new approach avoids computing the synchronous product of a large set of finite-state machines. Instead, the synchronous product is computed gradually, and intermediate results are simplified using conflict-preserving abstractions based on process-algebraic results about fair testing. Heuristics are used to choose between different possible abstractions. By translating the problem representation, the same method can also be applied to verify safety properties, in particular, controllability. Experimental results show that the method is applicable to finite-state machine models of industrial scale and brings considerable improvements in performance over other methods for nonblocking verification. [ABSTRACT FROM AUTHOR]