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.
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 bases folding theorem showing that in a natural setting the support vectors can be simulated by basis of dimension 2. 1
Holographic algorithms were introduced by Valiant as a new methodology to derive polynomial time algorithms. Here information and computation are represented by exponential sums using the so-called signatures. These signatures express superpositions of perfect matchings, and are used to achieve exponential sized cancellations, and thereby exponential speedups. Most holographic algorithms so far used symmetric signatures. In this paper we use unsymmetric signatures to give some new holographic algorithms. We also prove a characterization theorem for a class of realizable un-symmetric signatures, each of which may be used to design new holographic algorithms.
The
P versus
NP problem is arguably the most important open problem in all of theoretical computer science. In recent years, geometry has arisen as one of the most promising approaches for tackling this problem, both for obtaining positive results (polynomial-time solutions to seemingly intractable computational problems) and for proving negative results (impossibility results stating that such algorithms cannot exist). This work deals with both directions. \nIn the positive direction, the theory of holographic algorithms introduced by Valiant represents a novel approach to achieving polynomial-time algorithms for seemingly intractable counting problems via a reduction to counting planar perfect matchings and a linear change of basis. The connection to geometry is that a counting problem can be solved by a holographic algorithm provided a particular system of equations associated to that problem is solvable. Two fundamental parameters in holographic algorithms are the \\emph{domain size} and the \\emph{basis size}. Roughly, the domain size is the range of colors involved in the counting problem at hand (e.g. counting graph
k-colorings is a problem over domain size
k), while the basis size
ell captures the dimensionality of the representation of those colors. A major open problem has been: for a given
k, what is the smallest
ell for which any holographic algorithm for a problem over domain size
k ``collapses to'' (can be simulated by) a holographic algorithm with basis size
ell? Cai and Lu showed in 2008 that over domain size 2, basis size 1 suffices, opening the door to an extensive line of work on the structural theory of holographic algorithms over the Boolean domain. Cai and Fu later showed for signatures of full rank that over domain sizes 3 and 4, basis sizes 1 and 2, respectively, suffice, and they conjectured that over domain size
k there is a collapse to basis size
lfloorlog2krfloor. In the first half of this work, we resolve this conjecture in the affirmative for signatures of full rank for all
k. As a simple consequence, we are able to formulate Valiant's holographic framework over all domain sizes in terms of the geometry of spinor varieties and their orbits under basis change. \nIn the negative direction, Valiant's conjecture is an algebraic analogue of
P versus
NP which states that the permanent polynomial
permm cannot be computed as a linear projection of the determinant polynomial
detn for
n=poly(m). This can be formulated as an orbit containment problem; for the sake of bringing tools from algebraic geometry to bear on Valiant's conjecture, Mulmuley and Sohoni conjectured that Valiant's conjecture still holds when one passes to the Zariski closures of the relevant orbits. Essential to understanding what changes in this relaxation is understanding the geometry of the boundary of the orbit closure of
detn. In the second half of this work, we study this problem for
n=3 and use a combinatorial approach to give a complete classification of the irreducible components on the boundary in this case. We additionally present a new infinite family of boundary components for all even
n. Beyond these results and a general overview of Mulmuley-Sohoni's program, we also provide exposition on known lower bounds for the determinantal complexity of the permanent in Valiant's and Mulmuley-Sohoni's settings, an exponential lower bound due to Landsberg and Ressayre under a more restricted model of determinantal representations, Kumar's result on the non-normality of the orbit closure of
detn, Harris and Eisenbud's classification of maximal linear subspaces of the determinantal hypersurface in dimensions 3 and 4, and Huttenhain-Lairez's independent proof of our boundary component classification by way of resolution of singularities.
We establish a 1-1 correspondence between Valiant's character theory of matchgate/matchcircuit [14] and his signature theory of planar-matchgate/matchgrid [16], thus unifying the two theories in expressibility. In [5], we had established a complete characterization of general matchgates, in terms of a set of useful Grassmann-Pl"ucker identities. With this correspondence, we give a corresponding set of identities which completely characterizes planar-matchgates and their signatures. Applying this characterization we prove some negative results for holographic algorithms. On the positive side, we also give a polynomial time algorithm for a simultaneous node-edge deletion problem, using holographic algorithms. Finally we give characterizations of symmetric signatures realizable in the Hadamard basis.
Complexity theory is built fundamentally on the notion of efficient reduction among computational problems. Classical reductions involve gadgets that map solution fragments of one problem to solution fragments of another in one-to-one, or possibly one-to-many, fashion. In this paper we propose a new kind of reduction that allows for gadgets with many-to-many correspondences, in which the individual correspondences among the solution fragments can no longer be identified. Their objective may be viewed as that of generating interference patterns among these solution fragments so as to conserve their sum. We show that such holographic reductions provide a method of translating a combinatorial problem to finite systems of polynomial equations with integer coefficients such that the number of solutions of the combinatorial problem can be counted in polynomial time if one of the systems has a solution over the complex numbers. We derive polynomial time algorithms in this way for a number of problems for which only exponential time algorithms were known before. General questions about complexity classes can also be formulated. If the method is applied to a #P-complete problem, then polynomial systems can be obtained, the solvability of which would imply P$^{{\tiny{#P}}}$ = NC2.