Kronecker products and iterated matrix multiplication
We observe that the Kronecker product of tensors is the operation that converts the determinant polynomial into Cayley's first hyperdeterminant. We apply the Kronecker product to iterated matrix multiplication, which results in the hypercomputant, a VNP-complete and VW[1]-complete polynomial whose hardness we prove via the equivariance of the Kronecker product. The construction works over arbitrary commutative semirings and also for the tensor algebra and the exterior algebra. For the tensor algebra this gives a version of "noncommutative VNP", and for polynomials over the nonnegative real…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.08363
curl -X POST /api/v1/records/arxiv/2606.08363/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.08363/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'