Basis collapse in holographic algorithms

DOI10.1007/s00037-008-0249-xzbMath1149.68036OpenAlexW2173243501MaRDI QIDQ937202

Jin-Yi Cai, Pinyan Lu

Publication date: 20 August 2008

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-008-0249-x

zbMATH Keywords

computational complexityholographic algorithmsmatchgatebasis collapsesupport vectors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

Evaluations of Tutte polynomials of regular graphs ⋮ Counting degree-constrained subgraphs and orientations ⋮ \(P\) versus \(NP\) and geometry ⋮ Holographic algorithms by Fibonacci gates ⋮ Holographic algorithms without matchgates ⋮ Holographic algorithms: from art to science ⋮ Holographic algorithms on domains of general size ⋮ Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP

This page was built for publication: Basis collapse in holographic algorithms