Verification protocols with sub-linear communication for polynomial matrix operations
From MaRDI portal
Publication:1994891
DOI10.1016/J.JSC.2020.06.006zbMATH Open1474.68465arXiv1807.01272OpenAlexW2994940199MaRDI QIDQ1994891FDOQ1994891
Authors: David Lucas, Vincent Neiger, Clément Pernet, Daniel S. Roche, Johan Rosenkilde 
Publication date: 18 February 2021
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
Abstract: We design and analyze new protocols to verify the correctness of various computations on matrices over the ring F[x] of univariate polynomials over a field F. For the sake of efficiency, and because many of the properties we verify are specific to matrices over a principal ideal domain, we cannot simply rely on previously-developed linear algebra protocols for matrices over a field. Our protocols are interactive, often randomized, and feature a constant number of rounds of communication between the Prover and Verifier. We seek to minimize the communication cost so that the amount of data sent during the protocol is significantly smaller than the size of the result being verified, which can be useful when combining protocols or in some multi-party settings. The main tools we use are reductions to existing linear algebra verification protocols and a new protocol to verify that a given vector is in the F[x]-row space of a given matrix.
Full work available at URL: https://arxiv.org/abs/1807.01272
Recommendations
- Polynomial time interactive proofs for linear algebra with exponential matrix dimensions and scalars given by polynomial time circuits
- Prover efficient public verification of dense or sparse/structured matrix-vector multiplication
- Essentially optimal interactive certificates in linear algebra
- Time-optimal interactive proofs for circuit evaluation
- Secure Linear Algebra Using Linearly Recurrent Sequences
Symbolic computation and algebraic computation (68W30) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Communication complexity, information complexity (68Q11)
Cites Work
- Powers of tensors and fast matrix multiplication
- Title not available (Why is that?)
- 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
- Polynomial evaluation and interpolation on special sets of points
- How To Prove Yourself: Practical Solutions to Identification and Signature Problems
- Title not available (Why is that?)
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Title not available (Why is that?)
- Matrix multiplication via arithmetic progressions
- Fast computation of Hermite normal forms of random integer matrices
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Modern computer algebra
- The Knowledge Complexity of Interactive Proof Systems
- High-order lifting and integrality certification
- Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients
- Normal forms for general polynomial matrices
- A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants
- Title not available (Why is that?)
- Title not available (Why is that?)
- Certified dense linear system solving
- Triangular \(x\)-basis decompositions and derandomization of linear algebra algorithms over \(K[x]\)
- Fraction-free computation of matrix rational interpolants and matrix GCDs
- A general module theoretic framework for vector M-Padé and matrix rational interpolation
- Title not available (Why is that?)
- Invariant Description of Linear, Time-Invariant Controllable Systems
- Computing the rank profile matrix
- Title not available (Why is that?)
- Rank-profile revealing Gaussian elimination and the CUP matrix decomposition
- Proof-of-work certificates that can be efficiently computed in the cloud (invited talk)
- Unimodular completion of polynomial matrices
- Computing column bases of polynomial matrices
- Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix
- Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix
- Essentially optimal interactive certificates in linear algebra
- 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
Uses Software
This page was built for publication: Verification protocols with sub-linear communication for polynomial matrix operations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1994891)
