Polynomial Time Interactive Proofs for Linear Algebra with Exponential Matrix Dimensions and Scalars Given by Polynomial Time Circuits

DOI10.1145/3087604.3087640zbMath1457.68111OpenAlexW2738903027MaRDI QIDQ5119931

Gilles Villard, Lihong Zhi, Erich L. Kaltofen, Jean-Guillaume Dumas

Publication date: 9 September 2020

Published in: Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3087604.3087640

zbMATH Keywords

characteristic polynomialdeterminantmatrix rankmultivariate resultantcloud computingMacaulay matrixdelegated computationpolynomial system consistencyproofs for muggles

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Determinants, permanents, traces, other special matrix functions (15A15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items (1)

Elimination-based certificates for triangular equivalence and rank profiles

This page was built for publication: Polynomial Time Interactive Proofs for Linear Algebra with Exponential Matrix Dimensions and Scalars Given by Polynomial Time Circuits