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 


Abstract
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 nonsingularity of an N times N matrix with the i,jth entry being (2i+2j4)!/(i+j2)!^2 in polylog time in N.
Joint with JeanGuillaume Dumas, Gilles Villard, Lihgon Zhi.
Biography
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 straightline representation.
Kaltofen was the Chair of ACM's Special Interest Group on Symbolic & Algebraic Manipulation 199395. From 198587 he held an IBM Faculty Development Award. In 2009 Kaltofen was selected an ACM Fellow.