Conference item icon

Conference item

A complete dichotomy for complex-valued Holant^c

Abstract:

Holant problems are a family of counting problems on graphs, parametrised by sets of complex-valued functions of Boolean inputs. Holant^c denotes a subfamily of those problems, where any function set considered must contain the two unary functions pinning inputs to values 0 or 1. The complexity classification of Holant problems usually takes the form of dichotomy theorems, showing that for any set of functions in the family, the problem is either #P-hard or it can be solved in polynomial t...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's version

Actions


Access Document


Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Publisher:
Schloss Dagstuhl Publisher's website
Publication date:
2018-06-29
Acceptance date:
2018-04-16
DOI:
Pubs id:
pubs:859695
URN:
uri:bb2186a4-f74b-4d53-91ed-6161ddf1f94e
UUID:
uuid:bb2186a4-f74b-4d53-91ed-6161ddf1f94e
Local pid:
pubs:859695

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP