Grainger College of Engineering Seminars & Speakers

Abstract:   Algebraic complexity theory asks how hard it is to compute polynomials over a field. Rather than asking an absolute version of this question, one can ask a relative version of this question: if f(x) is easy to compute then are factors or summands of f(x) easy to compute (Grochow, Bulletin of EATCS 131, 2020)? Andrews and Forbes (STOC 2022) studied this relative question in the setting of the determinantal ideals generated by the r x r minors of n x m matrices. They showed that given such a polynomial in this ideal, one can use it as an oracle to approximately compute the t x t determinant, whereby approximate computation we refer to the model of border computation. This left the natural open question: can one obtain the same result without requiring approximations? In this work, we deborder the result of Andrews and Forbes. Our results are established using a new application of the isolation lemma, combined with a careful analysis of straightening-law expansions of polynomials in determinantal ideals. Analogous results are also found for the pfaffian ideals.