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 naturally in alge- braic circuit lower bounds, geometric complexity theory, and algebraic proof complexity. For ideals generated by a single element, 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 ideals generated by just 2 elements. For a few examples of specific ideals of interest coming from circuit lower bounds or proof complexity, some lower bounds on polynomials in these ideals are known using 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 complexity land- scape of polynomials in ideals.