Basis collapse in holographic algorithms

DOI10.1007/S00037-008-0249-XMaRDI QIDQ937202zbMATH OpenOpenAlexFDO

Authors 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

basis collapsecomputational complexityholographic algorithmsmatchgatesupport vectors

Mathematics Subject Classification ID

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

Recommendations

• Base collapse of holographic algorithms
• Basis collapse for holographic algorithms over all domain sizes
• Holographic algorithms: from art to science
• Holographic algorithms: from art to science
• A collapse theorem for holographic algorithms with matchgates on domain size at most 4

Cited in

(14)

• Holographic algorithms by Fibonacci gates
• Holographic algorithms without matchgates
• Evaluations of Tutte polynomials of regular graphs
• Counting degree-constrained subgraphs and orientations
• Holographic algorithms on bases of rank 2
• A collapse theorem for holographic algorithms with matchgates on domain size at most 4
• Basis collapse for holographic algorithms over all domain sizes
• Base collapse of holographic algorithms
• Holographic Algorithms: The Power of Dimensionality Resolved
• Holographic algorithms with matchgates capture precisely tractable planar \#CSP
• \(P\) versus \(NP\) and geometry
• Holographic algorithms on domains of general size
• Holographic algorithms: from art to science
• Counting degree-constrained orientations

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

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