Valiant's Holant theorem is a powerful tool for algorithms and reductions for counting problems. It states that if two sets $\mathcal{F}$ and $\mathcal{G}$ of tensors (a.k.a. constraint functions or signatures) are related by a \emph{holographic transformation}, then $\mathcal{F}$ and $\mathcal{G}$ are \emph{Holant-indistinguishable}, i.e., every tensor network using tensors from $\mathcal{F}$, resp. from $\mathcal{G}$, contracts to the same value. Xia (ICALP 2010) conjectured the converse of the Holant theorem, but a counterexample was found based on \emph{vanishing} signatures, those which are Holant-indistinguishable from 0. We prove two near-converses of the Holant theorem using techniques from invariant theory. (I) Holant-indistinguishable $\mathcal{F}$ and $\mathcal{G}$ always admit two sequences of holographic transformations mapping them arbitrarily close to each other, i.e., their $\text{GL}_q$-orbit closures intersect. (II) We show that vanishing signatures are the only true obstacle to a converse of the Holant theorem. As corollaries of the two theorems we obtain the first characterization of homomorphism-indistinguishability over graphs of bounded degree, a long standing open problem, and show that two graphs with invertible adjacency matrices are isomorphic if and only if they are homomorphism-indistinguishable over graphs with maximum degree at most three. We also show that Holant-indistinguishability is complete for a complexity class \textbf{TOCI} introduced by Lysikov and Walter, and hence hard for graph isomorphism.

We prove a complete complexity classification theorem for the planar eight-vertex model. For every parameter setting in ℂ for the eight-vertex model, the partition function is either (1) computable in P-time for every graph, or (2) #P-hard for general graphs but computable in P-time for planar graphs, or (3) #P-hard even for planar graphs. The classification has an explicit criterion. In (2), we discover new P-time computable eight-vertex models on planar graphs beyond Kasteleyn’s algorithm for counting planar perfect matchings. They are obtained by a combinatorial transformation to the planar Even Coloring problem followed by a holographic transformation to the tractable cases in the planar six-vertex model. In the process, we also encounter non-local connections between the planar eight vertex model and the bipartite Ising model, conformal lattice interpolation and Möbius transformation from complex analysis. The proof also makes use of cyclotomic fields.

Recently, Cai [ 3 ] showed that Shor’s quantum factoring algorithm fails to factor large integers when algorithm’s quantum Fourier transform (QFT) is corrupted by a vanishing level of random noise on the QFT’s precise controlled rotation gates. We show that under the same error model, Shor’s quantum discrete log algorithm, and its various modifications, fail to compute discrete logs modulo P for a positive density of primes P and a similarly vanishing level of noise. We also show that the same noise level causes Shor’s algorithm to fail with probability \(1-o(1)\) to compute discrete logs modulo P for randomly selected primes P .

Abstract We consider Shor’s quantum factoring algorithm in the setting of noisy quantum gates. Under a generic model of random noise for (controlled) rotation gates, we prove that the algorithm does not factor integers of the form pq when the noise exceeds a vanishingly small level in terms of n —the number of bits of the integer to be factored, where p and q are from a well-defined set of primes of positive density. We further prove that with probability 1 − o (1) over random prime pairs ( p, q ), Shor’s factoring algorithm does not factor numbers of the form pq , with the same level of random noise present.

We study the properties of elections that have a given position matrix (in such elections each candidate is ranked on each position by a number of voters specified in the matrix). We show that counting elections that generate a given position matrix is #P-complete. Consequently, sampling such elections uniformly at random seems challenging and we propose a simpler algorithm, without hard guarantees. Next, we consider the problem of testing if a given matrix can be implemented by an election with a certain structure (such as single-peakedness or group-separability). Finally, we consider the problem of checking if a given position matrix can be implemented by an election with a Condorcet winner. We complement our theoretical findings with experiments.

Recently, Mančinska and Roberson proved [Mančinska and Roberson, 2020] that two graphs G and G' are quantum isomorphic if and only if they admit the same number of homomorphisms from all planar graphs. We extend this result to planar #CSP with any pair of sets ℱ and ℱ' of real-valued, arbitrary-arity constraint functions. Graph homomorphism is the special case where each of ℱ and ℱ' contains a single symmetric 0-1-valued binary constraint function. Our treatment uses the framework of planar Holant problems. To prove that quantum isomorphic constraint function sets give the same value on any planar #CSP instance, we apply a novel form of holographic transformation of Valiant [Valiant, 2008], using the quantum permutation matrix 𝒰 defining the quantum isomorphism. Due to the noncommutativity of 𝒰’s entries, it turns out that this form of holographic transformation is only applicable to planar Holant. To prove the converse, we introduce the quantum automorphism group Qut(ℱ) of a set of constraint functions/tensors ℱ, and characterize the intertwiners of Qut(ℱ) as the signature matrices of planar Holant(ℱ | EQ) quantum gadgets. Then we define a new notion of (projective) connectivity for constraint functions and reduce arity while preserving the quantum automorphism group. Finally, to address the challenges posed by generalizing from 0-1 valued to real-valued constraint functions, we adapt a technique of Lovász [László Lovász, 1967] in the classical setting for isomorphisms of real-weighted graphs to the setting of quantum isomorphisms.

We prove a complexity dichotomy theorem for counting planar graph homomorphisms of domain size 3. Given any 3 by 3 real valued symmetric matrix H defining a graph homomorphism from all planar graphs G ↦ ZH(G), we completely classify the computational complexity of this problem according to the matrix H. We show that for every H, the problem is either polynomial time computable or #P-hard. The P-time computable cases consist of precisely those that are P-time computable for general graphs (a complete classification is known) or computable by Valiant’s holographic algorithm via matchgates. We also prove several results about planar graph homomorphisms for general domain size q. The proof uses mainly analytic arguments.

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.

Abstract We prove a complexity classification for Holant problems defined by an arbitrary set of complex-valued symmetric constraint functions on Boolean variables. This is to specifically answer the question: Is the Fisher-Kasteleyn-Temperley (FKT) algorithm under a holographic transformation (Valiant, SIAM J. Comput. 37(5), 1565–1594 2008) a universal strategy to obtain polynomial-time algorithms for problems over planar graphs that are intractable on general graphs? There are problems that are #P-hard on general graphs but polynomial-time solvable on planar graphs. For spin systems (Kowalczyk 2010) and counting constraint satisfaction problems (#CSP) (Guo and Williams, J. Comput. Syst. Sci. 107, 1–27 2020), a recurring theme has emerged that a holographic reduction to FKT precisely captures these problems. Surprisingly, for Holant, we discover new planar tractable problems that are not expressible by a holographic reduction to FKT. In particular, a straightforward formulation of a dichotomy for planar Holant problems along the above recurring theme is false. A dichotomy theorem for #CSPd, which denotes #CSP where every variable appears a multiple of d times, has been an important tool in previous work. However the proof for the #CSPd dichotomy violates planarity, and it does not generalize to the planar case easily. In fact, due to our newly discovered tractable problems, the putative form of a planar #CSPd dichotomy is false when d ≥ 5. Nevertheless, we prove a dichotomy for planar #CSP2. In this case, the putative form of the dichotomy is true. (This is presented in Part II of the paper.) We manage to prove the planar Holant dichotomy relying only on this planar #CSP2 dichotomy, without resorting to a more general planar #CSPd dichotomy for d ≥ 3. A special case of the new polynomial-time computable problems is counting perfect matchings (#PM) over k-uniform hypergraphs when the incidence graph is planar and k ≥ 5. The same problem is #P-hard when k = 3 or k = 4, which is also a consequence of our dichotomy. When k = 2, it becomes #PM over planar graphs and is tractable again. More generally, over hypergraphs with specified hyperedge sizes and the same planarity assumption, #PM is polynomial-time computable if the greatest common divisor (gcd) of all hyperedge sizes is at least 5. It is worth noting that it is the gcd, and not a bound on hyperedge sizes, that is the criterion for tractability.

We prove a complexity classification theorem that classifies all counting constraint satisfaction problems (\#CSP) over Boolean variables into exactly three classes: (1) polynomial-time solvable; (2) \#P-hard for general instances but solvable in polynomial time over planar structures; and (3) \#P-hard over planar structures. The classification applies to all finite sets of local, not necessarily symmetric, constraint functions on Boolean variables that take algebraic complex values. It is shown that Valiant's holographic algorithm with matchgates is a universal strategy for all problems in class (2).

We discover new P-time computable six-vertex models on planar graphs beyond Kasteleyn's algorithm for counting planar perfect matchings.∗ We further prove that there are no more: Together, they exhaust all P-time computable six-vertex models on planar graphs, assuming #P is not P. This leads to the following exact complexity classification: For every parameter setting in ℂ for the six-vertex model, the partition function is either (1) computable in P-time for every graph, or (2) #P-hard for general graphs but computable in P-time for planar graphs, or (3) #P-hard even for planar graphs. The classification has an explicit criterion. The new P-time cases in (2) provably cannot be subsumed by Kasteleyn's algorithm. They are obtained by a non-local connection to #CSP, defined in terms of a “loop space”. This is the first substantive advance toward a planar Holant classification with not necessarily symmetric constraints. We introduce Möbius transformation on ℂ as a powerful new tool in hardness proofs for counting problems.

We give the first efficient approximate counting and sampling algorithms for the six-vertex model and the eight-vertex model on regions of the square lattice ℤ2 in the low temperature regime. All previous algorithms for these problems are for high temperature settings, and rely on the rapid mixing of Markov chains. We prove that these natural Markov chains are torpidly mixing (exponentially slowly) in the low temperature settings. Rather than depending on rapid mixing MCMC, our algorithms are obtained by defining a special edge-2-coloring model, and showing an equivalence to (a linear combination of) abstract polymer models. We then prove the convergence of the cluster expansion of these polymer models. This allows us to employ the approach recently developed by Helmuth, Perkins, and Regts [25]. This combined with Barvinok's method [3, 42] via Taylor expansion (zero-free region of log partition function) gives the approximate counting and sampling algorithms. Significantly, these results provide the first counting problems that admit a fully polynomial time approximation scheme (FPTAS) on square lattice graphs but NP-hard to approximate even on bipartite graphs (rather than the weaker #BIS-hardness.)

We initiate a study of the classification of approximation complexity of the eight-vertex model defined over 4-regular graphs. The eight-vertex model, together with its special case the six-vertex model, is one of the most extensively studied models in statistical physics, and can be stated as a problem of counting weighted orientations in graph theory. Our result concerns the approximability of the partition function on all 4-regular graphs, classified according to the parameters of the model. Our complexity results conform to the phase transition phenomenon from physics. We introduce a quantum decomposition of the eight-vertex model and prove a set of closure properties in various regions of the parameter space. Furthermore, we show that there are extra closure properties on 4-regular planar graphs. These regions of the parameter space are concordant with the phase transition threshold. Using these closure properties, we derive polynomial time approximation algorithms via Markov chain Monte Carlo. We also show that the eight-vertex model is NP-hard to approximate on the other side of the phase transition threshold.

We prove a complexity dichotomy for Holant problems on the boolean domain with arbitrary sets of real-valued constraint functions. These constraint functions need not be symmetric nor do we assume any auxiliary functions. It is proved that for every set F of real-valued constraint functions, Holant(F) is either P-time computable or #P-hard. The classification has an explicit criterion. This is a culmination of much research on this problem, and it uses many previous results and techniques. Dealing with some concrete functions plays an important role in this proof. In particular, two functions, called f6 and f8, and their associated families exhibit intriguing and extraordinary closure properties related to Bell states in quantum information theory.

The complexity of graph homomorphisms has been a subject of intense study [1], [2], [3], [4], [5], [6], [7], [8]. The partition function ZA(·) of graph homomorphism is defined by a symmetric matrix A over C. We prove that the complexity dichotomy of [7] extends to bounded degree graphs. More precisely, we prove that either G → ZA(G) is computable in polynomial-time for every G, or for some Δ > 0 it is #P-hard over (simple) graphs G with maximum degree Δ(G) ≤ Δ. The tractability criterion on A for this dichotomy is explicit, and can be decided in polynomial-time in the size of A. We also show that the dichotomy is effective in that either a P-time algorithm for, or a reduction from #SAT to, ZA(·) can be constructed from A, in the respective cases.cases.

Holant problems are intimately connected with quantum theory as tensor networks. We first use techniques from Holant theory to derive new and improved results for quantum entanglement theory. We discover two particular entangled states |Ψ₆⟩ of 6 qubits and |Ψ₈⟩ of 8 qubits respectively, that have extraordinary closure properties in terms of the Bell property. Then we use entanglement properties of constraint functions to derive a new complexity dichotomy for all real-valued Holant problems containing a signature of odd arity. The signatures need not be symmetric, and no auxiliary signatures are assumed.

We study the approximation complexity of the partition function of the eight-vertex model on general 4-regular graphs. For the first time, we relate the approximability of the eight-vertex model to the complexity of approximately counting perfect matchings, a central open problem in this field. Our results extend those in arXiv:1811.03126 [cs.CC]. In a region of the parameter space where no previous approximation complexity was known, we show that approximating the partition function is at least as hard as approximately counting perfect matchings via approximation-preserving reductions. In another region of the parameter space which is larger than the previously known FPRASable region, we show that computing the partition function can be reduced to (with or without approximation) counting perfect matchings. Moreover, we give a complete characterization of nonnegatively weighted (not necessarily planar) 4-ary matchgates, which has been open for several years. The key ingredient of our proof is a geometric lemma. We also identify a region of the parameter space where approximating the partition function on planar 4-regular graphs is feasible but on general 4-regular graphs is equivalent to approximately counting perfect matchings. To our best knowledge, these are the first problems of this kind.

Graph homomorphism has been an important research topic since its introduction [László Lovász, 1967]. Stated in the language of binary relational structures in that paper [László Lovász, 1967], Lovász proved a fundamental theorem that the graph homomorphism function G ↦ hom(G, H) for 0-1 valued H (as the adjacency matrix of a graph) determines the isomorphism type of H. In the past 50 years various extensions have been proved by Lovász and others [László Lovász, 2006; Michael Freedman et al., 2007; Christian Borgs et al., 2008; Alexander Schrijver, 2009; László Lovász and Balázs Szegedy, 2009]. These extend the basic 0-1 case to admit vertex and edge weights; but always with some restrictions such as all vertex weights must be positive. In this paper we prove a general form of this theorem where H can have arbitrary vertex and edge weights. An innovative aspect is that we prove this by a surprisingly simple and unified argument. This bypasses various technical obstacles and unifies and extends all previous known versions of this theorem on graphs. The constructive proof of our theorem can be used to make various complexity dichotomy theorems for graph homomorphism effective, i.e., it provides an algorithm that for any H either outputs a P-time algorithm solving hom(⋅, H) or a P-time reduction from a canonical #P-hard problem to hom(⋅, H).

We develop a theory of graph algebras over general fields. This is modeled after the theory developed by Freedman, Lovász and Schrijver in [22] for connection matrices, in the study of graph homomorphism functions over real edge weight and positive vertex weight. We introduce connection tensors for graph properties. This notion naturally generalizes the concept of connection matrices. It is shown that counting perfect matchings, and a host of other graph properties naturally defined as Holant problems (edge models), cannot be expressed by graph homomorphism functions over the complex numbers (or even more general fields). Our necessary and sufficient condition in terms of connection tensors is a simple exponential rank bound. It shows that positive semidefiniteness is not needed in the more general setting.

We take the first step toward a classification of the approximation complexity of the six-vertex model. This is a subject of extensive research in statistical physics. Our result concerns the approximability of the partition function on 4-regular graphs, classified according to the parameters of the model. Our complexity results conform to the phase transition phenomenon from physics. We show that the approximation complexity of the six-vertex model behaves dramatically differently on the two sides separated by the phase transition threshold. Furthermore, we present structural properties of the six-vertex model on planar graphs for parameter settings that have known relations to the Tutte polynomial T(G; x, y).

Suppose \varphi and \psi are two angles satisfying \tan(\varphi) = 2 \tan(\psi) > 0. We prove that under this condition \varphi and \psi cannot be both rational multiples of \pi. We use this number theoretic result to prove a classification of the computational complexity of spin systems on k-regular graphs with general (not necessarily symmetric) real valued edge weights. We establish explicit criteria, according to which the partition functions of all such systems are classified into three classes: (1) Polynomial time computable, (2) \#P-hard in general but polynomial time computable on planar graphs, and (3) \#P-hard on planar graphs. In particular problems in (2) are precisely those that can be transformed to a form solvable by the Fisher-Kasteleyn-Temperley algorithm by a holographic reduction.

Holant problems capture a class of Sum-of-Product computations such as counting matchings. It is inspired by holographic algorithms and is equivalent to tensor networks, with counting CSP being a special case. A complexity classification for Holant problems is more difficult to prove, not only because it logically implies a classification for counting CSP, but also due to the deeper reason that there exist more intricate polynomial time tractable problems in the broader framework. We discover a new family of constraint functions ℒ which define polynomial time computable counting problems. These do not appear in counting CSP, and no newly discovered tractable constraints can be symmetric. It has a delicate support structure related to error-correcting codes. Local holographic transformations is fundamental in its tractability. We prove a complexity dichotomy theorem for all Holant problems defined by any real valued constraint function set on Boolean variables and contains two 0–1 pinning functions. Previously, dichotomy for the same framework was only known for symmetric constraint functions. The set ℒ supplies the last piece of tractability. We also prove a dichotomy for a variant of counting CSP as a technical component toward this Holant dichotomy.

We prove a complexity classification theorem that classifies all counting constraint satisfaction problems (#CSP) over Boolean variables into exactly three classes: (1) Polynomial-time solvable; (2) #P-hard for general instances, but solvable in polynomial-time over planar structures; and (3) #P-hard over planar structures. The classification applies to all finite sets of complex-valued, not necessarily symmetric, constraint functions on Boolean variables. It is shown that Valiant's holographic algorithm with matchgates is universal strategy for all problems in class (2).

We give a complexity dichotomy theorem for the counting constraint satisfaction problem (#CSP in short) with algebraic complex weights. To this end, we give three conditions for its tractability. Let F be any finite set of algebraic complex-valued functions defined on an arbitrary finite domain. We show that #CSP( F ) is solvable in polynomial time if all three conditions are satisfied and is #P-hard otherwise. Our dichotomy theorem generalizes a long series of important results on counting problems and reaches a natural culmination: (a) the problem of counting graph homomorphisms is the special case when F has a single symmetric binary function [Dyer and Greenhill 2000; Bulatov and Grohe 2005; Goldberg et al. 2010; Cai et al. 2013]; (b) the problem of counting directed graph homomorphisms is the special case when F has a single but not necessarily symmetric binary function [Dyer et al. 2007; Cai and Chen 2010]; (c) the unweighted form of #CSP is when all functions in F take values in {0, 1} [Bulatov 2008; Dyer and Richerby 2013].

Valiant introduced matchgate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, matchgate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in the statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs and can be arbitrary real-valued symmetric functions. We prove that every problem in this class belongs to precisely three categories: (1) those which are tractable (i.e., polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but tractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.

We prove a complexity dichotomy theorem for counting constraint satisfaction problems (#CSPs) with nonnegative and algebraic weights. This caps a long series of important results on counting problems including counting unweighted and weighted graph homomorphisms and the celebrated dichotomy theorem for unweighted #CSPs. Our dichotomy theorem gives a succinct criterion for tractability. If a set $\mathcal{F}$ of constraint functions satisfies this criterion, then the problem #CSP$(\mathcal{F})$ defined by $\mathcal{F}$ is solvable in polynomial time; if $\mathcal{F}$ does not satisfy this criterion, then the problem is #P-hard. Furthermore, we show that the question of whether a given $\mathcal{F}$ satisfies the criterion or not is decidable in NP. Surprisingly, our tractability criterion is simpler than the previous criteria for the more restricted classes of counting problems, although when specialized to those classes, they are logically equivalent. Our proof mainly uses linear algebra and represents a departure from universal algebra, the dominant methodology in recent years for the study of #CSPs on large domains.

We prove a complexity dichotomy theorem for Holant problems over an arbitrary set of complex-valued symmetric constraint functions $\mathcal{F}$ on Boolean variables. This extends and unifies all previous dichotomies for Holant problems on symmetric constraint functions (taking values without a finite modulus). We define and characterize all symmetric vanishing signatures; they turn out to be essential to the complete classification of Holant problems. The dichotomy theorem has an explicit tractability criterion expressible in terms of holographic transformations. A Holant problem defined by a set of constraint functions $\mathcal{F}$ is solvable in polynomial time if it satisfies this tractability criterion, and is #P-hard otherwise. The tractability criterion can be intuitively stated as follows: A set $\mathcal{F}$ is tractable if (1) every function in $\mathcal{F}$ has arity at most two; or (2) $\mathcal{F}$ is transformable to an affine type; or (3) $\mathcal{F}$ is transformable to a product type; or (4) $\mathcal{F}$ is vanishing, combined with the right type of binary functions; or (5) $\mathcal{F}$ belongs to a special category of vanishing-type Fibonacci gates. The proof of this theorem utilizes many previous dichotomy theorems on Holant problems and Boolean constraint satisfaction problems (#CSP). Holographic transformations play an indispensable role as both a proof technique and in the statement of the tractability criterion.

We prove a complexity dichotomy for complex-weighted Holant problems with an arbitrary set of symmetric constraint functions on Boolean variables. In the study of counting complexity, such as #CSP, there are problems which are #P-hard over general graphs but P-time solvable over planar graphs. A recurring theme has been that a holographic reduction [36] to FKT precisely captures these problems. This dichotomy answers the question: Is this a universal strategy? Surprisingly, we discover new planar tractable problems in the Holant framework (which generalizes #CSP) that are not expressible by a holographic reduction to FKT. In particular, the putative form of a dichotomy for planar Holant problems is false. Nevertheless, we prove a dichotomy for #CSP2, a variant of #CSP where every variable appears even times, that the presumed universality holds for #CSP2. This becomes an important tool in the proof of the full dichotomy, which refutes this universality in general. The full dichotomy says that the new P-time algorithms and the strategy of holographic reductions to FKT together are universal for these locally defined counting problems. As a special case of our new planar tractable problems, counting perfect matchings (#PM) over k-uniform hypergraphs is P-time computable when the incidence graph is planar and k ≥ 5. The same problem is #P-hard when k = 3 or k = 4, also a consequence of the dichotomy. More generally, over hypergraphs with specified hyperedge sizes and the same planarity assumption, #PM is P-time computable if the greatest common divisor (gcd) of all hyperedge sizes is at least 5.

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 show that an effective version of Siegel's Theorem on finiteness of integer solutions for a specific algebraic curve and an application of elementary Galois theory are key ingredients in a complexity classification of some Holant problems. These Holant problems, denoted by Holant(f), are defined by a symmetric ternary function f that is invariant under any permutation of the κ ≥ 3 domain elements. We prove that Holant(f) exhibits a complexity dichotomy. The hardness, and thus the dichotomy, holds even when restricted to planar graphs. A special case of this result is that counting edge κ-colorings is #P-hard over planar 3-regular multigraphs for all κ ≥ 3. In fact, we prove that counting edge κ-colorings is #P-hard over planar r-regular multigraphs for all κ ≥ r ≥ 3. The problem is polynomial-time computable in all other parameter settings. The proof of the dichotomy theorem for Holant(f) depends on the fact that a specific polynomial p(x, y) has an explicitly listed finite set of integer solutions, and the determination of the Galois groups of some specific polynomials. In the process, we also encounter the Tutte polynomial, medial graphs, Eulerian partitions, Puiseux series, and a certain lattice condition on the (logarithm of) the roots of polynomials.

While there is a large and growing body of literature on differentially private mechanisms for answering various classes of queries, to the best of our knowledge "count-range" queries have not been studied. These are a natural class of queries that ask "is the number of rows in a relation satisfying a given predicate between two integers θ1 and θ2?" Such queries can be viewed as a simple form of SQL "having" queries. We begin by developing a provably optimal differentially private mechansim for count-range queries for a single consumer. For count queries (in contrast to countrange queries), Ghosh et al. [9] have provided a differentially private mechanism that simultaneously maximizes utility for multiple consumers. This raises the question of whether such a mechanism exists for count-range queries. We prove that the answer is no --- for count range queries, no such mechanism exists. However, perhaps surprisingly, we prove that such a mechanism does exist for "threshold" queries, which are simply count-range queries for which either θ1 = 0 or θ2 = +∞. Furthermore, we prove that this mechanism is a two-approximation for general count-range queries.

Holant problems are a general framework to study the algorithmic complexity of counting problems. Both counting constraint satisfaction problems and graph homomorphisms are special cases. All previous results of Holant problems are over the Boolean domain. In this paper, we give the first dichotomy theorem for Holant problems for domain size greater than two. We discover unexpected tractable families of counting problems, by giving new polynomial time algorithms. This paper also initiates holographic reductions in domains of size greater than two. This is our main algorithmic technique, and is used for both tractable families and hardness reductions. The dichotomy theorem is the following: For any complex-valued symmetric function F with arity 3 on domain size 3, we give an explicit criterion on F, such that if F satisfies the criterion then the problem Holant*(F) is computable in polynomial time, otherwise Holant*(F) is #P-hard.

We prove a complexity dichotomy theorem for Holant problems over an arbitrary set of complex-valued symmetric constraint functions {F} on Boolean variables. This extends and unifies all previous dichotomies for Holant problems on symmetric constraint functions (taking values without a finite modulus). We define and characterize all symmetric vanishing signatures. They turned out to be essential to the complete classification of Holant problems. The dichotomy theorem has an explicit tractability criterion. A Holant problem defined by a set of constraint functions {F} is solvable in polynomial time if it satisfies this tractability criterion, and is #P-hard otherwise. The tractability criterion can be intuitively stated as follows: A set {F} is tractable if (1) every function in {F} has arity at most two, or (2) {F} is transformable to an affine type, or (3) {F} is transformable to a product type, or (4) {F} is vanishing, combined with the right type of binary functions, or (5) {F} belongs to a special category of vanishing type Fibonacci gates. The proof of this theorem utilizes many previous dichotomy theorems on Holant problems and Boolean #CSP. Holographic transformations play an indispensable role, not only as a proof technique, but also in the statement of the dichotomy criterion.

Each symmetric matrix $\mathbf{A}$ over $\mathbb{C}$ defines a graph homomorphism function $Z_{\bf A}(\cdot)$ on undirected graphs. The function $Z_{\mathbf{A}} (\cdot)$ is also called the partition function from statistical physics, and can encode many interesting graph properties, including counting vertex covers and $k$-colorings. We study the computational complexity of $Z_{\mathbf{A}} (\cdot)$ for arbitrary symmetric matrices $\mathbf{A}$ with algebraic complex values. Building on work by Dyer and Greenhill [Random Structures and Algorithms, 17 (2000), pp. 260--289], Bulatov and Grohe [Theoretical Computer Science, 348 (2005), pp. 148--186], and especially the recent beautiful work by Goldberg et al. [SIAM J. Comput., 39 (2010), pp. 3336--3402], we prove a complete dichotomy theorem for this problem. We show that $Z_{\mathbf{A}} (\cdot)$ is either computable in polynomial-time or \#P-hard, depending explicitly on the matrix $\mathbf{A}$. We further prove that the tractability criterion on $\mathbf{A}$ is polynomial-time decidable.

In this paper, we introduce and study the minimum consistent subset cover (MCSC) problem. Given a finite ground set X and a constraint t, find the minimum number of consistent subsets that cover X, where a subset of X is consistent if it satisfies t. The MCSC problem generalizes the traditional set covering problem and has minimum clique partition (MCP), a dual problem of graph coloring, as an instance. Many common data mining tasks in rule learning, clustering, and pattern mining can be formulated as MCSC instances. In particular, we discuss the minimum rule set (MRS) problem that minimizes model complexity of decision rules, the converse k-clustering problem that minimizes the number of clusters, and the pattern summarization problem that minimizes the number of patterns. For any of these MCSC instances, our proposed generic algorithm CAG can be directly applicable. CAG starts by constructing a maximal optimal partial solution, then performs an example-driven specific-to-general search on a dynamically maintained bipartite assignment graph to simultaneously learn a set of consistent subsets with small cardinality covering the ground set.

We introduce an idea called anti-gadgets in complexity reductions. These combinatorial gadgets have the effect of erasing the presence of some other graph fragment, as if we had managed to include a negative copy of a graph gadget. We use this idea to prove a complexity dichotomy theorem for the partition function Z(G) on 3-regular directed graphs G, where each edge is given a complex-valued binary function f: {0,1}2 → C. We show that

We give a complexity dichotomy theorem for the counting constraint satisfaction problem (#CSP in short) with algebraic complex weights. To this end, we give three conditions for its tractability. Let F be any finite set of complex-valued functions. We show that #CSP(F) is solvable in polynomial time if all three conditions are satisfied; and is #P-hard otherwise. Our dichotomy theorem generalizes a long series of important results on counting problems: (a) the problem of counting graph homomorphisms is the special case when F has a single symmetric binary function; (b) the problem of counting directed graph homomorphisms is the special case when F has a single but not-necessarily-symmetric binary function; and (c) the unweighted form of #CSP is when all functions in F take values in {0,1}.

We consider differentially private frequent itemset mining. We begin by exploring the theoretical difficulty of simultaneously providing good utility and good privacy in this task. While our analysis proves that in general this is very difficult, it leaves a glimmer of hope in that our proof of difficulty relies on the existence of long transactions (that is, transactions containing many items). Accordingly, we investigate an approach that begins by truncating long transactions, trading off errors introduced by the truncation with those introduced by the noise added to guarantee privacy. Experimental results over standard benchmark databases show that truncating is indeed effective. Our algorithm solves the "classical" frequent itemset mining problem, in which the goal is to find all itemsets whose support exceeds a threshold. Related work has proposed differentially private algorithms for the top- k itemset mining problem ("find the k most frequent itemsets".) An experimental comparison with those algorithms show that our algorithm achieves better F -score unless k is small.

We prove a complexity dichotomy theorem for all non-negatively weighted counting Constraint Satisfaction Problems (#CSP). This caps a long series of important results on counting problems, including unweighted and weighted graph homomorphisms and the celebrated dichotomy theorem for unweighted #CSP. Our dichotomy theorem gives a succinct criterion for tractability. If a set F of constraint functions satisfies the criterion, then the #CSP problem defined by F is solvable in polynomial time; if it does not satisfy the criterion, then the problem is #P-hard. We furthermore show that the question of whether F satisfies the criterion is decidable in NP. Surprisingly, our tractability criterion is simpler than the previous tractability criteria for the more restricted classes of problems, although when specialized to those cases, they are logically equivalent. Our proof mainly uses Linear Algebra and represents a departure from Universal Algebra, the dominant methodology in recent years.

Holant problems are a general framework to study counting problems. Both counting Constraint Satisfaction Problems (#CSP) and graph homomorphisms are special cases. We prove a complexity dichotomy theorem for Holant*(F), where F is a set of constraint functions on Boolean variables and output complex values. The constraint functions need not be symmetric functions. We identify four classes of problems which are polynomial time computable; all other problems are proved to be #P-hard. The main proof technique and indeed the formulation of the theorem use holographic algorithms and reductions. By considering these counting problems over the complex domain, we discover surprising new tractable classes, which are associated with isotropic vectors, i.e., a (non-zero) vector whose inner product with itself is zero.

We propose and explore a novel alternative framework to study the complexity of counting problems, called Holant problems. Compared to counting constraint satisfaction problems (#CSP), it is a refinement with a more explicit role for the constraint functions. Both graph homomorphism and #CSP can be viewed as special cases of Holant problems. We prove complexity dichotomy theorems in this framework. Our dichotomy theorems apply to local constraint functions, which are symmetric functions on Boolean input variables and evaluate to arbitrary real or complex values. We discover surprising tractable subclasses of counting problems, which could not easily be specified in the #CSP framework. When all unary functions are assumed to be free ($\mathrm{Holant}^*$ problems), the tractable ones consist of functions that are degenerate, or of arity at most two, or holographic transformations of Fibonacci gates. When only two special unary functions, the constant zero and constant one functions, are assumed to be free ($\mathrm{Holant}^c$ problems), we further identify three special families of tractable cases. Then we prove that all other cases are #P-hard. The main technical tool we use and develop is holographic reductions. Another technical tool used in combination with holographic reductions is polynomial interpolations.

The complexity of graph homomorphism problems has been the subject of intense study. It is a long standing open problem to give a (decidable) complexity dichotomy theorem for the partition function of directed graph homomorphisms. In this paper, we prove a decidable complexity dichotomy theorem for this problem and our theorem applies to all non-negative weighted form of the problem: given any fixed matrix A with non-negative algebraic entries, the partition function ZA(G) of directed graph homomorphisms from any directed graph G is either tractable in polynomial time or #P-hard, depending on the matrix A. The proof of the dichotomy theorem is combinatorial, but involves the definition of an infinite family of graph homomorphism problems. The proof of its decidability is algebraic using properties of polynomials.

Valiant introduced match gate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, match gate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs, and can be arbitrary real-valued symmetric functions. We prove that, every problem in this class belongs to precisely three categories: (1) those which are tractable (i.e., polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but ractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.

We prove a complexity dichotomy theorem for Holant Problems on $3$-regular graphs with an arbitrary complex-valued edge function. Three new techniques are introduced: (1) higher dimensional iterations in interpolation; (2) Eigenvalue Shifted Pairs, which allow us to prove that a pair of combinatorial gadgets \emph{in combination} succeed in proving \#P-hardness; and (3) algebraic symmetrization, which significantly lowers the \emph{symbolic complexity} of the proof for computational complexity. With \emph{holographic reductions} the classification theorem also applies to problems beyond the basic model.

We propose and explore a novel alternative framework to study the complexity of counting problems, called Holant Problems. Compared to counting Constrained Satisfaction Problems (CSP), it is a refinement with a more explicit role for the function constraints. Both graph homomorphism and CSP can be viewed as special cases of Holant Problems. We prove complexity dichotomy theorems in this framework. Because the framework is more stringent, previous dichotomy theorems for CSP problems no longer apply. Indeed, we discover surprising tractable subclasses of counting problems, which could not have been easily specified in the CSP framework. The main technical tool we use and develop is holographic reductions. Another technical tool used in combination with holographic reductions is polynomial interpolations. The study of Holant Problems led us to discover and prove a complexity dichotomy theorem for the most general form of Boolean CSP where every constraint function takes values in the complex number field {C}.

Theory and Applications of Models of Computation (TAMC) is an international conference series with an interdisciplinary character bringing together researchers working in computer science, mathematics (especially logic) and the physical sciences. This interdisciplinary approach, with an emphasis on the theory of computation in a broad sense, gives the series its special appeal within China and internationally. At a time when the pressures are increasingly towards narrowly ad hoc research, and scientific fragmentation, meetings that reassert the importance of theory, fundamental concepts and a wider perspective have an important role to play.

Valiant has proposed a new theory of algorithmic computation based on perfect matchings and Pfaffians. We study the properties of matchgates—the basic building blocks in this new theory. We give a set of algebraic identities which completely characterizes these objects for arbitrary numbers of inputs and outputs. These identities are derived from Grassmann-Plücker identities. The 4 by 4 matchgate character matrices are of particular interest. These were used in Valiant's classical simulation of a fragment of quantum computations. For these 4 by 4 matchgates, we use Jacobi's theorem on compound matrices to prove that the invertible matchgate matrices form a multiplicative group. Our results can also be expressed in the theory of Holographic Algorithms in terms of realizable standard signatures. These results are useful in establishing limitations on the ultimate capabilities of Valiant's theory of matchgate computations and Holographic Algorithms.

We propose a new method to prove complexity dichotomy theorems. First we introduce Fibonacci gates which provide a new class of polynomial time holographic algorithms. Then we develop holographic reductions. We show that holographic reductions followed by interpolations provide a uniform strategy to prove #P-hardness.

In Valiant's theory of arithmetic complexity, the classes VP and VNP are analogs of P and NP. A fundamental problem concerning these classes is the Permanent and Determinant Problem: Given a field F of characteristic ≠2, and an integer n, what is the minimum m such that the permanent of an n x n matrix X=(xij) can be expressed as a determinant of an m x m matrix, where the entries of the determinant matrix are affine linear functions of xij's, and the equality is in F [X]. Mignon and Ressayre (2004) [11] proved a quadratic lower bound m=Ω(n2) for fields of characteristic 0. We extend the Mignon-Ressayre quadratic lower bound to all fields of characteristic ≠2.

Holographic algorithms are a novel approach to design polynomial time computations using linear superpositions. Most holographic algorithms are designed with basis vectors of dimension 2. Recently Valiant showed that a basis of dimension 4 can be used to solve in P an interesting (restrictive SAT) counting problem mod 7. This problem without modulo 7 is #P-complete, and counting mod 2 is NP-hard. We give a general collapse theorem for bases of dimension 4 to dimension 2 in the holographic algorithms framework. We also define an extension of holographic algorithms to allow more general support vectors. Finally we give a Basis Folding Theorem showing that in a natural setting the support vectors can be simulated by bases of dimension 2.

In this paper, we introduce and study the Minimum Consistent Subset Cover (MCSC) problem. Given a finite ground set X and a constraint t, find the minimum number of consistent subsets that cover X, where a subset of X is consistent if it satisfies t. The MCSC problem generalizes the traditional set covering problem and has Minimum Clique Partition, a dual problem of graph coloring, as an instance. Many practical data mining problems in the areas of rule learning, clustering, and frequent pattern mining can be formulated as MCSC instances. In particular, we discuss the Minimum Rule Set problem that minimizes model complexity of decision rules as well as some converse k-clustering problems that minimize the number of clusters satisfying certain distance constraints. We also show how the MCSC problem can find applications in frequent pattern summarization. For any of these MCSC formulations, our proposed novel graph-based generic algorithm CAG can be directly applicable. CAG starts by constructing a maximal optimal partial solution, then performs an example-driven specific-to-general search on a dynamically maintained bipartite assignment graph to simultaneously learn a set of consistent subsets with small cardinality covering the ground set. Our experiments on benchmark datasets show that CAG achieves good results compared to existing popular heuristics.

We develop the theory of holographic algorithms. We definea basis manifold and give characterizations of algebraic varieties of realizable symmetric generators and recognizers on this manifold. We present a polynomial time decision algorithm for the simultaneous realizability problem. Using the general machinery we are able to giveunexpected holographic algorithms for some counting problems, modulo certain Mersenne type integers. These counting problems are P-complete without the moduli. Going beyond symmetric signatures, we define d-admissibility and d-realizability for general signatures, and give a characterizationof 2-admissibility.

We introduce the problem of labeling a particle's mass spectrum with the substances it contains, and develop several formal representations of the problem, taking into account practical complications such as unknown compounds and noise. This task is currently a bottle-neck in analyzing data from a new generation of instruments for real-time environmental monitoring.

We consider the problem of proving circuit lower bounds against the polynomial-time hierarchy. We give both positive and negative results. For the positive side, for any fixed integer k>>0, we give an explicit $\Sigma^{\rm p}_2$ language, acceptable by a $\Sigma^{\rm p}_2$ machine with running time O(n k 2 +k ), that requires circuit size >n k . This provides a constructive version of an existence theorem of R. Kannan [Inform. and Control, 55 (1982), pp. 40--56]. Our main theorem is on the negative side. We give evidence that it is infeasible to give relativizable proofs that any single language in the polynomial-time hierarchy requires superpolynomial circuit size. Our proof techniques are based on the decision tree version of the Switching Lemma for constant depth circuits and the Nisan--Wigderson pseudorandom generator. We also take this opportunity to publish some previously unpublished older results of the first author on constant depth circuits, both straight lower bounds and inapproximability results based on decision tree--type Switching Lemmas.

XML has become the de facto standard format for Web publishing and data transportation. Since online information changes frequently, being able to quickly detect changes in XML documents is important to Internet query systems, search engines, and continuous query systems. Previous work in change detection on XML, or other hierarchically structured documents, used an ordered tree model, in which left-to-right order among siblings is important and it can affect the change result. We argue that an unordered model (only ancestor relationships are significant) is more suitable for most database applications. Using an unordered model, change detection is substantially harder than using the ordered model, but the change result that it generates is more accurate. We propose X-Diff, an effective algorithm that integrates key XML structure characteristics with standard tree-to-tree correction techniques. The algorithm is analyzed and compared with XyDiff [CAM02], a published XML diff algorithm. An experimental evaluation on both algorithms is provided.

One key component of recent pricing-based congestion control schemes is an algorithm for probabilistically setting the Explicit Congestion Notification bit at routers so that a receiver can estimate the sum of link congestion prices along a path. We consider two such algorithms - a well-known algorithm called Random Exponential Marking (REM) and a novel algorithm called Random Additive Marking (RAM). We show that if link prices are unbounded, a class of REM-like algorithms are the only ones possible. Unfortunately, REM computes a biased estimate of total price and requires setting a parameter for which no uniformly good choice exists in a network setting. However, we show that if prices can be bounded and therefore normalized, then there is an alternate class of feasible algorithms, of which RAM is representative and furthermore, only the REM-like and RAM-like classes are possible. For properly normalized link prices, RAM returns an optimal price estimate (in terms of mean squared error), outperforming REM even if the REM parameter is chosen optimally. RAM does not require setting a parameter like REM, but does require a router to know its position along the path taken by a packet. We present an implementation of RAM for the Internet that exploits the existing semantics of the time-to-live field in IP to provide the necessary path position information.

We prove a connection of the worst-case complexity to the average-case complexity based on the Closest Vector Problem (CVP) for lattices. We assume that there is an efficient algorithm which can approximately solve a random instance of CVP, with a non-trivial success probability. For lattices under a certain natural distribution, we show that one can approximately solve several lattice problems (including a version of CVP) efficiently for every lattice with high probability.

We show that the class S2is a subclass of ZPPNP. The proof uses universal hashing, approximate counting and witness sampling. As a consequence, a collapse first noticed by Samik Sengupta that the assumption NP has small circuits collapses PH to S2becomes the strongest version to date of the Karp-Lipton Theorem. We also discuss the problem of finding irrefutable proofs for S2in ZPPNP.

We consider the complexity of join problems, focusing on equijoins, spatial-overlap joins, and set-containment joins. We use a graph pebbling model to characterize these joins combinatorially, by the length of their optimal pebbling strategies and computationally, by the complexity of discovering these strategies. Our results show that equijoins are the easiest of all joins, with optimal pebbling strategies that meet the lower bound over all join problems and that can be found in linear time. By contrast, spatial-overlap and set-containment joins are the hardest joins, with instances where optimal pebbling strategies reach the upper bound over all join problems and with the problem of discovering optimal pebbling strategies being NP-complete. For set-containment joins, we show that discovering the optimal pebbling is also MAX-SNP-Complete. As a consequence, we show that unless NP = P, there is a constant ∈o, such that this problem cannot be approximated within a factor of 1 + ∈Ο in polynomial time. Our results shed some light on the difficulty the applied community has had in finding “good” algorithms for spatial-overlap and set-containment joins.

We study the complexity of the following circuit minimization problem: given the truth table of a Boolean function f and a parameter s, decide whether f can be realized by a Boolean circuit of size at most s.We argue why this problem is unlikely to be in P (or even in P/poly) by giving a number of surprising consequences of such an assumption.We also argue that proving this problem to be NP-complete (if it is indeed true) would imply proving strong circuit lower bounds for the class DTIME(2°('~)), which appears beyond the currently known techniques.Question: Is f,~ computable by a Boolean circuit of size at most sn?

We present a deterministic polynomial-time algorithm for the A B C problem, which is the membership problem for 2-generated commutative linear semigroups over an algebraic number field. We also obtain a polynomial-time algorithm for the (easier) membership problem for 2-generated abelian linear groups. Furthermore, we provide a polynomial-sized encoding for the set of all solutions.

We survey some recent developments in the study of the complexity of lattice problems. After a discussion of some problems on lattices which can be algorithmically solved efficiently, our main focus is the recent progress on complexity results of intractability. We discuss Ajtai's worst-case/average-case connections, NP-hardness and non-NP-hardness, transference theorems between primal and dual lattices, and the Ajtai-Dwork cryptosystem.

We apply a new transference theorem from the geometry of numbers to Ajtai's connection of average-case to worst-case complexity of lattice problems. We also derive stronger bounds for the special class of lattices which possess n/sup /spl epsiv//-unique shortest lattice vectors. This class of lattices plays a significant role in Ajtai's connection of average-case to worst-case complexity of the shortest lattice vector problem, and in the Ajtai-Dwork public-key cryptosystem. Our proofs are non-constructive, based on methods from harmonic analysis. They yield currently the best Ajtai connection factors.

We prove tight hierarchy theorems for bounded error probabilistic quasi-polynomial time classes, under se"-era1 hardness assumptions.We show that if either (1) the Permanent does not have a subexponential time BP algorithm, or (2) some function in EXPTIME does not have subexponential size circuits, then for every lSa

We extend Levin's definition of average polynomial time to arbitrary time-bounds in accordance with the following general principles: (1) It essentially agrees with Levin's notion when applied to polynomial time-bounds. (2) If a language L belongs to DTIME(T(n)) for some time-bound T(n), then every distributional problem $(L,\mu)$ is T on the $\mu$-average. (3) If L does not belong to DTIME(T(n)) almost everywhere, then no distributional problem $(L,\mu)$ is T on the $\mu$-average. We present hierarchy theorems for average-case complexity, for arbitrary time-bounds, that are as tight as the well-known Hartmanis--Stearns hierarchy theorem for deterministic complexity. As a consequence, for every time-bound T(n), there are distributional problems $(L,\mu)$ that can be solved using only a slight increase in time but that cannot be solved on the $\mu$-average in time T(n).

Recently M. Ajtai showed that to approximate the shortest lattice vector in the l/sub 2/-norm within a factor (1+2(-dim/sup k/)), for a sufficiently large constant k, is NP-hard under randomized reductions. We improve this result to show that to approximate a shortest lattice vector within a factor (1+dim/sup -/spl epsiv//), for any /spl epsiv/>0, is NP-hard under randomized reductions. Our proof also works for arbitrary l/sub p/-norms, 1/spl les/p

We improve a connection of the worst-case complexity and the average-case complexity of some well-known lattice problems. This fascinating connection was first discovered by Ajtai (1995). We improve the exponent of this connection from 8 to 3.5+/spl epsiv/.

Resource-bounded measure theory is a study of complexity classes via an adaptation of the probabilistic method. The central hypothesis in this theory is the assertion that NP does not have measure zero in Exponential Time. This is a quantitative strengthening of NP/spl ne/P. We show that the analog in P of this hypothesis fails dramatically. In fact, we show that NTIME[n/sup 1/11/] has measure zero in P. These follow as consequences of our main theorem that the collection of languages accepted by constant-depth nearly exponential-size circuits has measure zero at polynomial time. In contrast, we show that the class AC/sup 0//sub 4/[/spl oplus/] of languages accepted by depth-4 polynomial-size circuits with AND, OR, NOT, and PARITY gates does not have measure zero at polynomial time. Our proof is based on techniques from circuit complexity theory and pseudorandom generators.

Building on the recent breakthrough by M. Ogihara (1995), we resolve a conjecture made by J. Hartmanis (1978) regarding the (non) existence of sparse sets complete for P under logspace many-one reductions. We show that if there exists a sparse hard set for P under logspace many-one reductions, then P=LOGSPACE. We further prove that if P has a sparse hard set under many-one reductions computable in NC/sup 1/, then P collapses to NC/sup 1/.

We prove that if strong pseudorandom number generators exist, then the class of languages that have polynomial-sized circuits (P/poly) is not measurable within exponential time, in terms of the resource-bounded measure theory of Lutz. We prove our result by showing that if P/poly has measure zero in exponential time, then there is a natural proof against P/poly, in the terminology of Razborov and Rudich (1994). We also provide a partial converse of this result.

The modular group occupies a central position in many branches of mathematical sciences. In this paper we give average polynomial-time algorithms for the unbounded and bounded membership problems for finitely generated subgroups of the modular group. The latter result affirms a conjecture of Y. Gurevich (1990).>

We present a deterministic polynomial-time algorithm for the ABC problem, which is the membership problem for 2-generated commutative linear semigroups over an algebraic number field. We also obtain a polynomial time algorithm, for the (easier) membership problem, for 2-generated abelian linear groups. Furthermore, we provide a polynomial-sized encoding for the set of all solutions.>

We investigate the Kolmogorov complexity of real numbers. Let K be the Kolmogorov complexity function; we determine the Hausdorff dimension and the topological dimension of the graph of K. Since these dimensions are different, the graph of the Kolmogorov complexity function of the real line forms a fractal in the sense of Mandelbrot. We also solve an open problem of Razborov using our exact bound on the topological dimension.

This paper considers Boolean formulae and their simulations by bounded width branching programs. It is shown that every balanced Boolean formula of size s can be simulated by a constant width (width 5) branching program of length $s^{1.811 \ldots } $. A lower bound for the translational cost from formulae to permutation branching programs is also presented.

Many parallel computationsare tree structured; as the computation proceeds, new processes are recursively created while others die out.Algorithms for maintaining dynamically evolving trees on fine-grain parallel architectures must have minimal overhead and must distribute processes evenly among processorsat run-time.A simple randomized strategy for maintaining dynamically evolving binary trees on hypercube networks is presented.The algorithm is distributed and does not require any global information.The algorithm guarantees that every pair of nodes adjacent in the tree are within distance O(loglog N)in an N-processor hypercube.Furthermore, if M is the number of active nodes in the tree at any instant, then, with ovenvhelming probability, no hypercube processors assigned more than 0(1 + (M\N))active nodes.The active nodes in a tree may constitute only leaves of the tree, or all nodes.As a corollary, with high probability, the load is evenly distributed throughout a computation whose running time is polynomial in N, the number of processors.The results can be generalized to bounded-degree trees.Our techniques justify the use of simple algorithms to efficiently parallelize any tree-based computation such as divide-andconquer, backtrack, functional expression evaluation, and to efficiently maintain dynamic data structures such as quad-trees that arise in scientific applications.A novel technique-tree surge~-is introduced to deal with dependencies inherent in trees.Together with tree surgery, the study of random walks is used to analyze the algorithm.

Hyperbolic groups are a rich class of groups frequently encountered in mathematical research, particularly in topology. It has been the focus of intense study by many combinatorial group theorists and topologists recently. We present some computational results for infinite groups, especially for hyperbolic groups. It is shown that the word problem for hyperbolic groups is solvable in NC2. This is the first NC algorithm for a class of groups in combinatorial group theory. We also consider the isomorphism problem of randomly generated groups using a novel technique: the Alexander polynomial from knot theory. These randomly generated groups are almost always hyperbolic groups.

In Valiant's theory of arithmetic complexity, the following question occupies a central position: Given an integer n, what is the minimal m such that the permanent of an n × n matrix is the projection of the determinant of an m × m matrix? More generally, for affine linear transformations, we ask the similar question: what is the minimal m such that the permanent of an n × n matrix is the determinant of an m × m matrix via affine linear transformation? This paper gives the lower bound m ⩾ ⌊ 2 · n ⌋, for affine linear transformations. The result is an improvement of earlier results by von zur Gathen, Babai, and Seress. It also generalizes a classical theorem of Marcus and Minc.

The problem of how many extra bits of 'help' a constant depth circuit needs in order to compute m functions is considered. Each help bit can be an arbitrary Boolean function. An exponential lower bound on the size of the circuit computing m parity functions in the presence of m-1 help bits is proved. The proof is carried out using the algebraic machinery of A. Razborov (1987) and R. Smolensky (1987). A by-product of the proof is that the same bound holds for circuits with mod/sub p/ gates for a fixed prime p>2. The lower bound implies a random oracle separation for PH and PSPACE, which is optimal in a technical sense.>

It is shown that Omega (n) variables are needed for first-order logic with counting to identify graphs on n vertices. This settles a long-standing open problem. The lower bound remains true over a set of graphs of color class size 4. This contrasts sharply with the fact that three variables suffice to identify all graphs of color class size 3, and two variables suffice to identify almost all graphs. The lower bound is optimal up to multiplication by a constant because n variables obviously suffice to identify graphs on n vertices.>

Boolean circuits and their simulations by bounded-width branching programs are considered. It is shown that every NC/sup 1/ circuit of size s can be simulated by a constant-width branching program of length s/sup 1.811. . ./. Some related group-theoretic results are presented.>

An n -variable Boolean formula may have anywhere from 0 to 2 n satisfying assignments. Can a polynomial-time machine, given such a formula, reduce this exponential number of possibilities to a small number of possibilities? We call such a machine an enumerator and prove that if there is a good polynomial-time enumerator for #P (i.e., one where for every Boolean formula f , the small set has at most O (| f | 1− ε ) numbers), then P = NP = P # P and probabilistic polynomial time equals polynomial time. Furthermore, we show that #P polynomial-time Turing reduces to enumerating #P.

We consider how much error a fixed depth Boolean circuit must make in computing the parity function. We show that with an exponential bound of the form exp(nλ) on the size of the circuits, they make a 50% error on all possible inputs, asymptotically and uniformly. As a consequence, we show that a random oracle set A separates PSPACE from the entire polynomial-time hierarchy with probability one.

The Boolean Hierarchy I: Structural Properties [J. Cai et al., SIAM J. Comput ., 17 (1988), pp. 1232–252] explores the structure of the boolean hierarchy, the closure of NP with respect to boolean operations. This paper uses the boolean hierarchy as a tool with which to extend and explain three important results in structural complexity theory. (1) Hartmanis, Immerman, and Sewelson [ Proc. 15th Annual Symposium on the Theory of Computation, 1983, pp. 382–391] showed that ${\text{E}} = {\text{NE}}$ if and only if ${\text{NP}} - {\text{P}}$ contains no sparse sets. In this paper it is shown that this reflects a behavior of the boolean hierarchy. When ${\text{E}} = {\text{NE}}$, sparse sets fall from alternate levels of the boolean hierarchy (Fig. 2(a)). Furthermore, it is shown that capturable sets (i.e., subsets of sparse NP sets) are banished from the boolean hierarchy when ${\text{E}} = {\text{NE}}:{\text{E}} = {\text{NE}}$ implies that ${\text{BH}} - {\text{P}}$ has no capturable sets. (2) Counting classes are natural candidates as complete languages for the levels of the boolean hierarchy. The authors show that in relativized worlds counting classes are not complete for the levels of the boolean hierarchy. Relatedly, the work of Blass and Gurevich [Inform, and Control, 55 (1982), pp. 80–88] is extended and it is concluded that counting classes are weak in some relativized worlds. (3) Karp and Lipton [Proc. 12th Annual Symposium on the Theory of Computation, 1980, pp. 302–309] showed that if NP has a sparse oracle (i.e., if there is a sparse set S so ${\text{NP}} \subseteq {\text{P}}^S $; equivalently, if NP has small circuits), then the polynomial hierarchy collapses to ${\text{NP}}^{{\text{NP}}} $. The authors demonstrate that this cannot be much improved. There is a relativized world in which NP has a sparse oracle, yet the boolean hierarchy is infinite. Thus no proof that relativizes can show: NP has .a sparse oracle implies that the polynomial hierarchy equals the boolean hierarchy. The results of this paper present new ideas and techniques, and put previous results about NP and ${\text{D}}^{\text{P}} $ in a richer perspective. Throughout, the emphasis is on the structure of the boolean hierarchy and its relations with more common classes.

A simple randomized algorithm is presented for maintaining dynamically evolving binary trees on hypercube networks. The algorithm guarantees that: (1) nodes adjacent in the tree are within distance O(log log N) in an N-processor hypercube, and (2) with overwhelming probability, no hypercube processor is assigned more than O(1+M/N) tree nodes, where M is the number of nodes in the tree. The algorithm is distributed and does not require any global information. This is the first load-balancing algorithm with provably good performance. The algorithm can be used to parallelize efficiently any tree-based computation. It can also be used to maintain efficiently dynamic data structures such as quadtrees. A technique called tree surgery is introduced to deal with dependencies inherent in trees. Together with tree surgery, the study of random walks is used to analyze the algorithm.>

In this paper, we study the complexity of sets formed by boolean operations (union, intersection, and complement) on NP sets. These are the sets accepted by trees of hardware with NP predicates as leaves, and together these form the boolean hierarchy. We present many results about the structure of the boolean hierarchy: separation and immunity results, natural complete languages, and structural asymmetries between complementary classes. We show that in some relativized worlds the boolean hierarchy is infinite, and that for every k there is a relativized world in which the boolean hierarchy extends exactly k levels. We prove natural languages, variations of VERTEX COVER, complete for the various levels of the boolean hierarchy. We show the following structural asymmetry: though no set in the boolean hierarchy is ${\text{D}}^{\text{P}} $-immune, there is a relativized world in which the boolean hierarchy contains ${\text{coD}}^{\text{P}} $-immune sets. Thus, this paper explores the structural properties of the boolean hierarchy. A companion paper [J. Cai et al., SIAM J. Comput. 18 (1989), to appear] uses the boolean hierarchy to extend known results on small circuits [R. Karp and R. Lipton, Proc. 12th Annual Symposium on the Theory of Computation, 1980, pp. 302–309], sparse sets in NP-P [J. Hartmanis, N. Immerman, and V. Sewelson, Proc.15th Annual Symposium on the Theory of Computation, 1983, pp. 382–391], and counting classes [A. Blass and Y. Gurevich, Inform. and Control, 55 (1982), pp. 80–88].

In their excellent paper, C. H. Papadimitriou and M. Yannakakis [J. Comput. System Sci., 28 (1982), pp. 244–259] asked whether the minimal-3-uncolorability problem is, among other Critical Problems, DP-complete. This paper gives an affirmative answer to the above question. We show that minimal-k-uncolorability is ${\text{D}}^{\text{p}} $-complete, for all fixed $k \geqq 3$. Furthermore, for $k = 3$, the reduction can be modified by using “sensitive” gadgets to resolve the planar case.

We consider how much error a fixed depth Boolean circuit has to make for computing the parity function. We show that with an exponential bound of the form $exp(n^{\lambda})$ on the size of the circuits, they make asymptotically 50% error on all possible input, uniformly. As a consequence, we show that with a random oracle set $A,Pr.(PSPACE^{A} \supseteq PH^{A} = 1$.