Proves an Ω(n^{ω/2}) lower bound on counting edge-weighted perfect matchings in planar graphs over algebraic circuits, matching the FKT+Yuster upper bound.
Completeness classes in algebraic complexity theory
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
verdicts
UNVERDICTED 3representative citing papers
An explicit field-independent SL2-equivariant isomorphism is given between tensor invariant spaces and plethysm spaces, extending Hermite reciprocity and related maps, plus a combinatorial proof that the Hermite map is triangular with 1s on the diagonal.
P_C ≠ NP_C in the BSS model over C implies VP^0 ≠ VNP^0 in the constant-free Valiant classes over C, with an analogous nonuniform statement.
citing papers explorer
-
Planar Perfect Matching Counting is as Hard as Determinants
Proves an Ω(n^{ω/2}) lower bound on counting edge-weighted perfect matchings in planar graphs over algebraic circuits, matching the FKT+Yuster upper bound.
-
Field-independent Kronecker-plethysm isomorphisms
An explicit field-independent SL2-equivariant isomorphism is given between tensor invariant spaces and plethysm spaces, extending Hermite reciprocity and related maps, plus a combinatorial proof that the Hermite map is triangular with 1s on the diagonal.
-
Intractability of Hilbert's Nullstellensatz implies algebraic hardness of permanent
P_C ≠ NP_C in the BSS model over C implies VP^0 ≠ VNP^0 in the constant-free Valiant classes over C, with an analogous nonuniform statement.