Verification protocols with sub-linear communication for polynomial matrix operations

DOI10.1016/j.jsc.2020.06.006zbMath1474.68465arXiv1807.01272OpenAlexW2994940199MaRDI QIDQ1994891

Daniel S. Roche, Vincent Neiger, Clément Pernet, Johan Rosenkilde, David Lucas

Publication date: 18 February 2021

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1807.01272

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Communication complexity, information complexity (68Q11)

Uses Software

• Geppetto

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Triangular \(x\)-basis decompositions and derandomization of linear algebra algorithms over \(K[x\)]
• Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients
• A general module theoretic framework for vector M-Padé and matrix rational interpolation
• Matrix multiplication via arithmetic progressions
• Fast computation of Hermite normal forms of random integer matrices
• Fast projection methods for minimal design problems in linear system theory
• On fast multiplication of polynomials over arbitrary algebras
• A probabilistic remark on algebraic program testing
• Proof-of-work certificates that can be efficiently computed in the cloud (invited talk)
• High-order lifting and integrality certification
• Polynomial evaluation and interpolation on special sets of points
• Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix
• Rank-profile revealing Gaussian elimination and the CUP matrix decomposition
• Normal forms for general polynomial matrices
• Certified dense linear system solving
• Fraction-Free Computation of Matrix Rational Interpolants and Matrix GCDs
• Computing the Rank Profile Matrix
• Modern Computer Algebra
• Computing column bases of polynomial matrices
• Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix
• Essentially optimal interactive certificates in linear algebra
• Powers of tensors and fast matrix multiplication
• Unimodular completion of polynomial matrices
• How To Prove Yourself: Practical Solutions to Identification and Signature Problems
• The Knowledge Complexity of Interactive Proof Systems
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants
• Certificates for Triangular Equivalence and Rank Profiles
• Computing Canonical Bases of Modules of Univariate Relations
• Certification of Minimal Approximant Bases
• Computing Popov and Hermite Forms of Rectangular Polynomial Matrices
• Quadratic-time certificates in linear algebra
• Invariant Description of Linear, Time-Invariant Controllable Systems

This page was built for publication: Verification protocols with sub-linear communication for polynomial matrix operations