On blockwise symmetric matchgate signatures and higher domain \#CSP

DOI10.1016/J.IC.2018.09.012zbMATH Open1408.68074arXiv1707.00373OpenAlexW2963920790MaRDI QIDQ1633804FDOQ1633804

Authors: Zhiguo Fu, Fengqin Yang, Minghao Yin 

Publication date: 21 December 2018

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

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$.

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

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

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)

Cites Work

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

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)