Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Annual Symposium on Foundations of Computer Science

Accidental Algorthims

Leslie Gabriel Valiant

Published Oct 1, 2006• 118 citations
Publisher

Abstract

We provide evidence for the proposition that the computational complexity of individual problems, and of whole complexity classes, hinge on the existence of certain solvable polynomial systems that are unlikely to be encountered other than by systematic explorations for them. We consider a minimalist version of Cook's 3CNF problem, namely that of monotone planar 3 CNF formulae where each variable occurs twice. We show that counting the number of solutions of these modulo 2 is oplusP-complete (hence NP-hard) but counting them modulo 7 is polynomial time computable (sic). We also show a similar dichotomy for a vertex cover problem. To derive completeness results we use a new holographic technique for proving completeness results in oplusP for problems that are in P. For example, we can show in this way that oplus2CNF, the parity problem for 2CNF, is oplusP-complete. To derive efficient algorithms we use computer algebra systems to find appropriate holographic gates. In order to explore the limits of holographic techniques we define the notion of an elementary matchgrid algorithm to capture a natural but restricted use of them. We show that for the NP-complete general 3 CNF problem no such elementary matchgrid algorithm can exist. We observe, however, that it remains open for many natural #P-complete problems whether such elementary matchgrid algorithms exist, and for the general CNF problem whether non-elementary matchgrid algorithms exist

DOI
10.1109/focs.2006.7

Related papers

Holographic Algorithms

Leslie Gabriel Valiant

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.

SIAM Journal on Computing•Jan 1, 2008•229 citations

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP

Jin‐Yi Cai, Pinyan Lu, Mingji Xia

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.

arXiv:1008.0683•SIAM Journal on Computing•Jan 1, 2017•50 citations

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP

Jin‐Yi Cai, Pinyan Lu, Mingji Xia

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.

Annual Symposium on Foundations of Computer Science•Oct 1, 2010•50 citations

Geometry in Algorithms and Complexity: Holographic Algorithms and Valiant's Conjecture

Sitan Chen

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 $\\lfloor\\log_2 k\\rfloor$. 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 $\\perm_m$ cannot be computed as a linear projection of the determinant polynomial $\\det_n$ 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 $\\det_n$. 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 $\\det_n$, 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.

•Jun 21, 2016•0 citations

Holographic algorithms: from art to science

Jin‐Yi Cai, Pinyan Lu

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.

ACM Symposium on Theory of Computing (STOC)•Jun 11, 2007•69 citations

Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain

Jin‐Yi Cai, Zhiguo Fu

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

arXiv:1603.07046•SIAM Journal on Computing•Nov 5, 2019•23 citations
We provide evidence for the proposition that the computational complexity of individual problems, and of whole complexity classes, hinge on the existence of certain solvable polynomial systems that are unlikely to be encountered other than by systematic explorations for them. We consider a minimalist version of Cook's 3CNF problem, namely that of monotone planar 3 CNF formulae where each variable occurs twice. We show that counting the number of solutions of these modulo 2 is oplusP-complete (hence NP-hard) but counting them modulo 7 is polynomial time computable (sic). We also show a similar dichotomy for a vertex cover problem. To derive completeness results we use a new holographic technique for proving completeness results in oplusP for problems that are in P. For example, we can show in this way that oplus2CNF, the parity problem for 2CNF, is oplusP-complete. To derive efficient algorithms we use computer algebra systems to find appropriate holographic gates. In order to explore the limits of holographic techniques we define the notion of an elementary matchgrid algorithm to capture a natural but restricted use of them. We show that for the NP-complete general 3 CNF problem no such elementary matchgrid algorithm can exist. We observe, however, that it remains open for many natural #P-complete problems whether such elementary matchgrid algorithms exist, and for the general CNF problem whether non-elementary matchgrid algorithms exist
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.
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.
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.
The P\\PP versus NP\\NPNP 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 kkk-colorings is a problem over domain size kkk), while the basis size ell\\ellell captures the dimensionality of the representation of those colors. A major open problem has been: for a given kkk, what is the smallest ell\\ellell for which any holographic algorithm for a problem over domain size kkk ``collapses to'' (can be simulated by) a holographic algorithm with basis size ell\\ellell? 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 kkk there is a collapse to basis size lfloorlog2krfloor\\lfloor\\log_2 k\\rfloorlfloorlog2​krfloor. In the first half of this work, we resolve this conjecture in the affirmative for signatures of full rank for all kkk. 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\\PP versus NP\\NPNP which states that the permanent polynomial permm\\perm_mpermm​ cannot be computed as a linear projection of the determinant polynomial detn\\det_ndetn​ for n=poly(m)n = \\poly(m)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\\det_ndetn​. In the second half of this work, we study this problem for n=3n = 3n=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 nnn. 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\\det_ndetn​, 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 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 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).