Essentially optimal interactive certificates in linear algebra

DOI10.1145/2608628.2608644zbMath1325.68274arXiv1401.4567OpenAlexW3103318574MaRDI QIDQ3452388

Erich L. Kaltofen, Jean-Guillaume Dumas

Publication date: 11 November 2015

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

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

zbMATH Keywords

randomizationmatrix rankpositive semidefinitenessprobabilistic proofinteractive certificatematrix characteristic polynomial\(\Sigma\)-protocolsoutput validation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Cryptography (94A60) Data structures (68P05) Randomized algorithms (68W20) Special matrices (15B99)

Related Items (4)

Automating algorithm selection: checking for matrix properties that can simplify computations ⋮ Foreword ⋮ Verification protocols with sub-linear communication for polynomial matrix operations ⋮ Elimination-based certificates for triangular equivalence and rank profiles

Uses Software

• Jordan

Cites Work

• Unnamed Item
• Unnamed Item
• An effective implementation of symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
• Cylindrical algebraic decomposition using validated numerics
• The Jordan Curve Theorem, Formally and Informally
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Definability and decision problems in arithmetic

This page was built for publication: Essentially optimal interactive certificates in linear algebra