Base collapse of holographic algorithms

DOI10.1145/2897518.2897560MaRDI QIDQ5361880zbMATH OpenOpenAlexFDO

Authors Mingji Xia

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.01230

zbMATH Keywords

holographic reductionmatchgatePfaffian

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Abstract: A holographic algorithm solves a problem in domain of size $n$, by reducing it to counting perfect matchings in planar graphs. It may simulate a $n$-value variable by a bunch of $t$ matchgate bits, which has $2^t$ values. The transformation in the simulation can be expressed as a $nimes{2}^t$ matrix $M$, called the base of the holographic algorithm. We wonder whether more matchgate bits bring us more powerful holographic algorithms. In another word, whether we can solve the same original problem, with a collapsed base of size $nimes{2}^r$, where $r<t$. Base collapse was discovered for small domain $n=2,3,4$. For $n=3,4$, the base collapse was proved under the condition that there is a full rank generator. We prove for any $n$, the base collapse to a $rleqlfloorlognfloor$, with some similar conditions. One of them is that the original problem is defined by one symmetric function. In the proof, we utilize elementary matchgate transformations instead of matchgate identities.

Recommendations

• Basis collapse for holographic algorithms over all domain sizes
• Basis collapse in holographic algorithms
• A collapse theorem for holographic algorithms with matchgates on domain size at most 4
• Holographic algorithms on bases of rank 2

Cited in

(8)

• Some observations on holographic algorithms
• On blockwise symmetric matchgate signatures and higher domain \#CSP
• Clifford gates in the Holant framework
• 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
• Holographic algorithms on domains of general size
• Basis collapse in holographic algorithms

This page was built for publication: Base collapse of holographic algorithms

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