Some observations on holographic algorithms

DOI10.1007/s00037-017-0160-4zbMath1419.68211OpenAlexW2753198711MaRDI QIDQ1616615

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

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

Related Items (4)

Holographic algorithms on domains of general size ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ FKT is not universal -- a planar holant dichotomy for symmetric constraints

Cites Work

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

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