Theory Seminar: Andrei Staicu, "Proving Algebraic Independence in Zero-Knowledge."

Abstract: A set of multivariate polynomials is algebraically independent if they exhibit no non-trivial algebraic relations; this generalizes linear independence to polynomials. Over the rationals, deciding if polynomials are algebraically independent has a fast randomized algorithm, but these techniques do not extend to finite fields. The only known algorithm over finite fields runs in polynomial space, and it is still an open question to find a more efficient (randomized) algorithm. There has, however, been progress on tightening the upper bound on the complexity of this problem. Previously, deciding algebraic independence over finite fields was shown to admit Arthur-Merlin proofs (due to Guo, Saxena, and Sinhababu). In this work, we improve this upper bound by showing that algebraic independence over finite fields has a non-interactive statistical zero-knowledge (NISZK) proof system. 

This talk is based on joint work with Michael Forbes, presented at ICALP 2026.