English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Open

Presents the pdf analysis as premium feature

PDF Analysis

Insights

Presents the summarisation as premium feature

Summarisation

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Generalized counting constraint satisfaction problems include Holant problemswith planarity restrictions; polynomial-time algorithms for such problemsinclude matchgates and matchcircuits, which are based on Pfaffians. Inparticular, they use gates which are expressible in terms of a vector ofsub-Pfaffians of a skew-symmetric matrix. We introduce a new type of circuitbased instead on determinants, with seemingly different expressive power. Inthese determinantal circuits, a gate is represented by the vector of all minorsof an arbitrary matrix. Determinantal circuits permit a different class ofgates. Applications of these circuits include proofs of theorems from algebraicgraph theory including the Chung-Langlands formula for the number of rootedspanning forests of a graph and computing Tutte Polynomials of certainmatroids. They also give a strategy for simulating quantum circuits with closedtimelike curves. Monoidal category theory provides a useful language fordiscussing such counting problems, turning combinatorial restrictions intocategorical properties. We introduce the counting problem in monoidalcategories and count-preserving functors as a way to study FP subclasses ofproblems in settings which are generally #P-hard. Using this machinery we showthat, surprisingly, determinantal circuits can be simulated by Pfaffiancircuits at quadratic cost.

Generalized Counting Constraint Satisfaction Problems With Determinantal Circuits