On blockwise symmetric matchgate signatures and higher domain \#CSP

DOI10.1016/J.IC.2018.09.012MaRDI QIDQ1633804zbMATH OpenOpenAlexFDO

Authors Zhiguo Fu, Fengqin Yang, Minghao Yin

Publication date 21 December 2018

Published in Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

matchgate\#CSPblockwise symmetryholographic transformation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Abstract: For any $ngeq3$ and $qgeq3$, we prove that the {sc Equality} function $({=}_n)$ on $n$ variables over a domain of size $q$ cannot be realized by matchgates under holographic transformations. This is a consequence of our theorem on the structure of blockwise symmetric matchgate signatures. %due to the rank of the matrix form of the blockwise symmetric standard signatures, %where $({=}_n)$ is an equality signature on domain $0,1,cdots,q-1$. This has the implication that the standard holographic algorithms based on matchgates, a methodology known to be universal for #CSP over the Boolean domain, cannot produce P-time algorithms for planar #CSP over any higher domain $qgeq3$.

Recommendations

• On blockwise symmetric signatures for matchgates
• On Block-Wise Symmetric Signatures for Matchgates
• Efficient constructions of signcryption schemes and signcryption composability
• More efficient structure-preserving signatures -- or: bypassing the type-III lower bounds
• Efficient signatures on randomizable ciphertexts
• More efficient (almost) tightly secure structure-preserving signatures
• Cramer-Damgård signatures revisited: Efficient flat-tree signatures based on factoring
• Public Key Cryptography - PKC 2005
• Partially structure-preserving signatures: lower bounds, constructions and more

Cites work

• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• A collapse theorem for holographic algorithms with matchgates on domain size at most 4
• A complete dichotomy rises from the capture of vanishing signatures
• A dichotomy for real weighted Holant problems
• Base collapse of holographic algorithms
• Basis collapse for holographic algorithms over all domain sizes
• Dimer problem in statistical mechanics-an exact result
• Expressiveness of matchgates.
• Holant problems and counting CSP
• Holographic Algorithms
• Holographic algorithm with matchgates is universal for planar \#CSP over Boolean domain
• Holographic algorithms with matchgates capture precisely tractable planar \#CSP
• Holographic algorithms without matchgates
• Holographic algorithms: from art to science
• Holographic algorithms: the power of dimensionality resolved
• Matchgates revisited
• On blockwise symmetric signatures for matchgates
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Some observations on holographic algorithms
• The Complexity of Enumeration and Reliability Problems
• The complexity of computing the permanent
• The complexity of symmetric Boolean parity Holant problems
• The complexity of weighted Boolean \#CSP modulo \(k\)
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice

Cited in

(5)

• Restricted Holant dichotomy on domains 3 and 4
• Holographic algorithms on domains of general size
• Restricted Holant dichotomy on domain sizes 3 and 4
• Energy management strategy based on convex optimization for fuel cell/battery/ultracapacitor hybrid vehicle
• The complexity of counting planar graph homomorphisms of domain size 3

This page was built for publication: On blockwise symmetric matchgate signatures and higher domain \#CSP

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