Local holographic transformations: tractability and hardness
2023-04-27
(Press-News.org)
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 CSPd 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 #CSPd 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.
END
ELSE PRESS RELEASES FROM THIS DATE:
2023-04-27
IVF procedures can be improved by combining genetic and clinical data to predict the number of eggs retrieved in patients undergoing ovarian stimulation.
####
Article URL: https://journals.plos.org/ploscompbiol/article?id=10.1371/journal.pcbi.1011020
Article Title: Personalized prediction of the secondary oocytes number after ovarian stimulation: A machine learning model based on clinical and genetic data
Author Countries: Poland
Funding: The research was co-financed by the European Regional Development Fund under the ...
2023-04-27
Results from the NRG Oncology RTOG 0631 clinical trial comparing stereotactic vs. conventional radiotherapy for localized vertebral metastases of the spine did not meet its primary endpoint. Data from the study suggests that radiosurgery was not considered superior in terms of pain responses at 3 months following treatment, and even displayed worse pain response, than the conventional external beam radiotherapy (cEBRT). These results were recently published in the JAMA Oncology.
cEBRT is currently the standard of care for treating ...
2023-04-27
A study supported by the National Institutes of Health found that people who experienced acute kidney injury (AKI) during a hospitalization, including those admitted with AKI or who developed AKI in the hospital, were more likely to revisit the hospital or die shortly after discharge, compared to people hospitalized without AKI. AKI is a sudden loss of kidney function that usually lasts for a short time. The research, funded by NIH’s National Institute of Diabetes and Digestive and Kidney Diseases (NIDDK), was ...
2023-04-27
Inflammation is a complex biological process that can eradicate pathogens and promotes repair of damaged tissues. However, deregulation of the immune system can lead to uncontrolled inflammation and produce lesions instead. Inflammation is also involved in cancer. The molecular mechanisms underlying inflammation are not fully understood, and so developing new drugs represents a significant challenge.
As far back as 2020, Dr. Raphaël Rodriguez, CNRS research director and head of the Chemical Biology team at Institut Curie (Equipe ...
2023-04-27
A research team led by Prof. HYEON Taeghwan at the Center for Nanoparticle Research within the Institute for Basic Science (IBS) in Seoul, South Korea has developed a new photocatalytic platform for the mass production of hydrogen. The group’s study on the photocatalytic platform led to the development of a floatable photocatalytic matrix, which allows efficient hydrogen evolution reaction with clear advantages over conventional hydrogen production platforms such as film or panel types.
The importance of alternative energy has recently increased due to global challenges such as environmental ...
2023-04-27
FOR IMMEDIATE RELEASE
Researchers at Johns Hopkins University School of Medicine say they have evidence from a new study in rats that spinal cord stimulation (SCS) may be useful in reducing chronic pain in people undergoing active treatment with a common anti-cancer drug.
The study found that the use of SCS measurably reduced pain response in rats that were implanted with human lung cancer tissue — without compromising effectiveness of treatment with paclitaxel, a drug used to treat a variety of cancers.
The study, published April 11 in Neuromodulation: Technology at the Neural ...
2023-04-27
Norway, like other Nordic countries, widely utilised non-mandatory advice during the COVID-19 pandemic in the attempt to reduce social contacts among people and occasionally turned to obligatory measures, specifically during peaks in transmission. In comparison with stricter interventions, non-mandatory measures are usually less invasive and costly and have been recommended in previous pandemics, including influenza.
Mobile phone data provides mobility metrics
In their research article published in Eurosurveillance today, Kamineni et al. compare the impact on mobility when previously non-mandatory ...
2023-04-27
WASHINGTON — New and advanced types of nuclear reactors could play an important role in helping the U.S. meet its long-term climate goals, but a range of technical, regulatory, economic, and societal challenges must first be overcome, says a new report from the National Academies of Sciences, Engineering, and Medicine. Development, testing, and widespread deployment of these reactors could take several decades. The report makes recommendations for the U.S. Department of Energy, the Nuclear Regulatory Commission, other federal and state agencies, and private industry to lay the groundwork required for advanced reactors to become a viable part of the U.S. energy system.
Currently, ...
2023-04-27
A plant-based compound purified from the traditional Chinese herb, Astragalus, has the potential to improve the outcome of heart attack patients, new research has revealed.
Experts at Newcastle University, UK, have found that the product, known as TA-65®, significantly reduces inflammation and, unlike current cardiovascular treatments, does not negatively impact immunity.
A study, published in GeroScience, showed that when TA-65® was given to older patients for over a year after their heart attack, it specifically increased lymphocytes, improving immunity ...
2023-04-27
TORONTO, April 27, 2023 – Families of those with serious mental health issues feel stigmatized and alone, say York University researchers in a new study.
“We are avoided. When we told our family, they shut us out, I am so hurt, and so angry” – 62-year-old mom with an adult son with serious mental illness, as described to York researchers.
It’s well known that those who have serious mental illnesses such as schizophrenia face a great deal of stigma in society, but what has been less understood is the concept of “stigma by ...
LAST 30 PRESS RELEASES:
[Press-News.org] Local holographic transformations: tractability and hardness
