Some observations on holographic algorithms

DOI10.1007/S00037-017-0160-4zbMATH Open1419.68211OpenAlexW2753198711MaRDI QIDQ1616615FDOQ1616615

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

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

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)

Cites Work

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

Cited In (11)

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

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)