Complexity in ideals of polynomials: questions on algebraic complexity of circuits and proofs

Abstract

Given ideals In ⊆ F[x1, . . . xn] for each n, what can we say about the circuit complexity of polynomial families fn in those ideals, that is, such that fn ∈ In for all n? Such ideals and their cosets arise natu- rally in algebraic circuit lower bounds, geometric complexity theory, and algebraic proof complexity. For ideals generated by a single ele- ment, this is the question of relating the complexity of a polynomial to the complexity of its factors, which has a long and rich history. For general ideals, essentially nothing beyond that is known, even for ide- als generated by just 2 elements. For a few examples of specific ide- als of interest coming from circuit lower bounds or proof complex- ity, some lower bounds on polynomials in these ideals are known us- ing succinct hitting sets (Forbes–Shpilka–Volk, Theory Comput., 2019) and circuit techniques (Forbes–Shpilka–Tzameret–Wigderson, CCC 2016). In this survey, we review these connections & motivations, and raise many questions that we hope will help shed light on the com- plexity landscape of polynomials in ideals.