Learning the Coefficients: A Presentable Version of Border Complexity and Applications to Circuit Factoring

The border, or the approximative, model of algebraic computation (VP) is quite popular due to the Geometric Complexity Theory (GCT) approach to P ≠ NP conjecture, and its complex analytic origins. On the flip side, the definition of the border is inherently existential in the field constants that the model employs. In particular, a poly-size border circuit 𝐶 (𝜀, 𝒙) cannot be compactly presented in reality, as the limit parameter 𝜀 may require exponential precision. In this work we resolve this issue by giving a constructive, or a presentable, version of border circuits and state its applications.

We make border presentable by restricting the circuit 𝐶 to use only those constants, in the function field F 𝑞 (𝜀), that it can generate by the ring operations on 𝜀 ∪ F 𝑞 , and their division, within polysize circuit. This model is more expressive than VP as it affords exponential-degree in 𝜀; and analogous to the usual border, we define new border classes called VP 𝜀 and VNP 𝜀 . We prove that both these (now called presentable border) classes lie in VNP. Such a 'debordering' result is not known for the classical border classes VP and respectively for VNP. We pose VP 𝜀 = VP as a new conjecture to study the border.

The heart of our technique is a newly formulated exponential interpolation over a finite field, to bound the Boolean complexity of the coefficients before deducing the algebraic complexity. It attacks two factorization problems which were open before. We make progress on (Conj.8.3 in Bürgisser 2000, FOCS 2001) and solve (Conj.2.1 in Bürgisser 2000; Chou,Kumar,Solomon CCC 2018) over all finite fields:

(1) Each poly-degree irreducible factor, with multiplicity coprime to field characteristic, of a poly-size circuit (of possibly exponential-degree), is in VNP. (2) For all finite fields, and all factors, VNP is closed under factoring. Consequently, factors of VP are always in VNP. The prime characteristic cases were open before due to the inseparability obstruction (i.e. when the multiplicity is not coprime to 𝑞).