Algorithms Seminar

Polynomial Time Interactive Proofs For Linear Algebra with Exponential Matrix Dimensions

Speaker:Erich Kaltofen
Date: Thursday, September 21, 2017
Time: 12:00pm - 1:00pm
Location: D344 LSRC, Duke


We present an interactive probabilistic proof protocol that certifies in (log N)^{O(1)} arithmetic and Boolean operations for the verifier the determinant, for example, of an N x N matrix over a field whose entries a(i,j) are given by a single (log N)^{O(1)}-depth arithmetic circuit, which contains (log N)^{O(1)} field constants and which is polynomial time uniform, for example, which has size (log N)^{O(1)}. The prover can produce the interactive certificate within a (log N)^{O(1)} factor of the cost of computing the determinant. Our protocol is a version of the proofs for muggles protocol by Goldwasser, Kalai and Rothblum [STOC 2008, J. ACM 2015]. We can apply the protocol, e.g., to certifying the non-singularity of an N times N matrix with the i,j-th entry being (2i+2j-4)!/(i+j-2)!^2 in poly-log time in N. Joint with Jean-Guillaume Dumas, Gilles Villard, Lihgon Zhi.


Erich Kaltofen received his Ph.D. degree in Computer Science in 1982 from Rensselaer Polytechnic Institute. He was an Assistant Professor of Computer Science at the University of Toronto and an Assistant, Associate, and Professor at Rensselaer Polytechnic Institute. Since 1996 he is a Professor of Mathematics at North Carolina State University. He has held visiting positions at ENS Lyon, MIT, UPMC Paris, U. Grenoble, and U. Waterloo. Kaltofen's current interests in the symbolic computation discipline are hybrid symbolic/numeric algorithms, efficient algorithms for sparse interpolation and error correction and interactive proofs. Kaltofen has designed several algorithms for polynomial factorization including one for polynomials in straight-line representation. Kaltofen was the Chair of ACM's Special Interest Group on Symbolic & Algebraic Manipulation 1993-95. From 1985-87 he held an IBM Faculty Development Award. In 2009 Kaltofen was selected an ACM Fellow.