Polynomial Time Interactive Proofs for Linear Algebra with Exponential Matrix Dimensions and Scalars Given by Polynomial Time Circuits

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]. An application is the following: suppose in a system of k homogeneous polynomials of total degree <= d in the k variables y(1),..., y(k) the coefficient of the term y(1)(e1)... y(k)(ek) in the i-th polynomial is the (hypergeometric) value ((i+ e(1) + .... + e(k))!)/((i!))(e(1)!) ... (e(k)!)), where e! is the factorial of e. Then we have a probabilistic protocol that certifies (projective) solvability or inconsistency of such a system in (k log(d))(O(1)) bit complexity for the verifier, that is, in polynomial time in the number of variables k and the logarithm of the total degree, log(d).