REVIEW 4 cited by
Completeness classes in algebraic complexity theory
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Completeness classes in algebraic complexity theory
read the original abstract
The purpose of this overview is to explain the enormous impact of Les Valiant's eponymous short conference contribution from 1979 on the development of algebraic complexity.
Forward citations
Cited by 4 Pith papers
-
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.
-
Quantum determinants in polynomial time
The q-Cayley determinant of q-right-quantum matrices equals a Valiant-style clow determinant and is computable by a polynomial-size algebraic branching program.
-
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 i...
-
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.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.