Local holographic transformations: tractability and hardness

Counting problems arise in many different fields, e.g., statistical physics, economics and machine learning. In order to study the complexity of counting problems, several natural frameworks have been proposed. Two well studied frameworks are counting constraint satisfaction problems (#CSP) and Holant problems. For counting satisfaction problems over the Boolean domain, two explicit tractable families namely  and , are identified; any function set which is not contained in these two families is proved to be #P-hard. Furthermore, counting CSP^d is the counting constraint satisfaction problem restricted to the instances where every variable occurs a multiple of d times. The team not only generalized local affine functions to #CSP^d for general d, but also gives new tractable classes by combining local holographic transformations with global holographic transformation. Moreover, the team showed how to use local holographic transformations to prove hardness. This is of independent interests in the complexity classification of counting problems.

Recently, significant progresses have been made in the complexity classification of counting problems for three frameworks, graph homomorphisms, the counting constraint satisfaction problems and Holant problems. Holographic transformations played a key role in this project. In order to apply a holographic transformation on a particular situation, a research team led by Zhiguo FU published their new research on 27 March 2023 in Frontiers of Computer Science co-published by Higher Education Press and Springer Nature.

In the past twenty years, a series of remarkable complexity dichotomy theorems were built for counting problems. The key techniques to prove hardness were gadget constructions, interpolation and holographic transformations.

The team gives an example which is #P-hard by introducing local holographic transformations as a new tool to prove hardness. Specially, local affine functions partially reflect the difficulty in proving a Holant problem: Nice structures hide in strange supports and we have no powerful tools. Overall, there is still a long way to go to achieve a complete complexity classification for Holant problems with complex-valued and asymmetric signatures.

###

Research Article, Published: 27 March 2023

Peng YANG, Zhiguo FU. Local holographic transformations: tractability and hardness. Front. Comput. Sci., 2023, 17(2): 172401, https://doi.org/10.1007/s11704-022-1231-5

About Frontiers of Computer Science (FCS)

FCS was launched in 2007. It is published bimonthly both online and in print by HEP and Springer. Prof. Zhi-Hua Zhou from Nanjing University serves as the Editor-in-Chief. It aims to provide a forum for the publication of peer-reviewed papers to promote rapid communication and exchange between computer scientists. FCS covers all major branches of computer science, including: architecture, software, artificial intelligence, theoretical computer science, networks and communication, information systems, multimedia and graphics, information security, interdisciplinary, etc. The readers may be interested in the special columns “Perspective” and “Excellent Young Scholars Forum”.

FCS is indexed by SCI(E), EI, DBLP, Scopus, etc. The latest IF is 2.669. FCS solicits the following article types: Review, Research Article, Letter.