• with Prateek Dwivedi and Nitin Saxena
  • STOC 2024

PDF

The border, or the approximative, model of algebraic computation () is quite popular due to the Geometric Complexity Theory (GCT) approach to 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 , that it can generate by the ring operations on , and their division, within poly-size circuit. This model is more expressive than as it affords exponential-degree in ; and analogous to the usual border, we define new border classes called and . We prove that both these (now called presentable border) classes lie in . Such a ‘debordering’ result is not known for the classical border classes and respectively for . We pose 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:

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

Research overview