Some observations on holographic algorithms

DOI10.1007/S00037-017-0160-4MaRDI QIDQ1616615zbMATH OpenOpenAlexFDO

Authors Leslie G. Valiant

Publication date 7 November 2018

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-017-0160-4

zbMATH Keywords

computational complexityalgebraic complexityholographic algorithmsfinite functions

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Some observations on holographic algorithms
• scientific article; zbMATH DE number 3913673
• Planar 3DM is NP-complete
• The computational complexity of graph problems with succinct multigraph representation
• On unique graph 3-colorability and parsimonious reductions in the plane
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
• Publication:5752588
• Comparing the Expressibility of Languages Formed Using NP-Complete Operators

Cites work

• scientific article; zbMATH DE number 3848625 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1443271 (Why is no real title available?)
• scientific article; zbMATH DE number 3257409 (Why is no real title available?)
• Base collapse of holographic algorithms
• Basis collapse for holographic algorithms over all domain sizes
• Computational complexity of counting problems on 3-regular planar graphs
• Computing and Combinatorics
• Expressiveness of matchgates.
• Holographic Algorithms
• Matchgates revisited
• On Approximately Counting Colorings of Small Degree Graphs
• On feedback vertex sets and nonseparating independent sets in cubic graphs
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• On the theory of matchgate computations
• On unique graph 3-colorability and parsimonious reductions in the plane
• Planar Formulae and Their Uses
• Reducibility among combinatorial problems
• Some Results on Matchgates and Holographic Algorithms
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Planar Counting Problems
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The complexity of computing the permanent
• The complexity of counting in sparse, regular, and planar graphs
• The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
• Vertex and edge covers with clustering properties: Complexity and algorithms

Cited in

(10)

• Automata, Languages and Programming
• Some Results on Matchgates and Holographic Algorithms
• Some observations on holographic algorithms
• Holographic algorithms on domains of general size
• Bipartite 3-regular counting problems with mixed signs
• Bipartite 3-regular counting problems with mixed signs
• Holographic algorithms: the power of dimensionality resolved
• Holographic algorithms: from art to science
• Holographic Algorithms
• FKT is not universal -- a planar holant dichotomy for symmetric constraints

This page was built for publication: Some observations on holographic algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1616615)