Homogeneous Algebraic Complexity Theory and Algebraic Formulas

Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov

TL;DR

This paper introduces a new framework for studying algebraic complexity using homogeneous linear projections, offering a more natural geometric approach than traditional affine projections. The authors present novel polynomials that are complete for the class of efficiently computable algebraic formulas (VF), providing simpler tools to tackle fundamental conjectures in computational complexity.

What Problem Does This Paper Address?

The paper tackles a core problem in algebraic complexity theory: understanding the relationship between the complexity of computing the determinant and the permanent of matrices. This is a key algebraic analogue of the P vs. NP problem. Geometric Complexity Theory (GCT) offers a promising approach using algebraic geometry and representation theory, but it often relies on "padding" polynomials with linear forms, which can obscure the underlying complexity. The authors aim to develop a "padding-free" approach by using homogeneous linear projections, which are more natural from a geometric perspective. This requires defining new complexity classes and finding "complete" polynomials within these classes that are simpler than existing ones like the iterated matrix multiplication (IMM) polynomial.

Methods

The paper introduces the concept of graded p-families and homogeneous linear projections as a more natural setting for GCT without padding. This involves defining polynomials based on degree and variable counts. They then define new complexity classes like V3F and V3P based on these graded p-families and homogeneous computations. The core of their contribution lies in identifying new polynomials, specifically variants of the elementary symmetric polynomial, that are complete for these classes under homogeneous linear projections. This means that if these new polynomials can be computed efficiently, then all polynomials in the class can be too. They also leverage and adapt existing techniques like Brent's depth reduction and the Valiant-Skyum-Berkowitz-Rackoff circuit depth reduction to work within their new framework.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Homogeneous Projections are More Natural: The paper argues that homogeneous linear projections are a more geometrically natural reduction than affine linear projections, especially for GCT, as they avoid the need for polynomial padding.
  • New Complete Polynomials for VF: The authors discover new, simpler polynomials that are complete for the class VF (efficiently computable algebraic formulas) under homogeneous linear projections. This is a significant step towards understanding the complexity of VF.
  • Bridging the Gap to Simpler Problems: By finding simpler complete polynomials, the paper suggests a path to proving hardness results for classes like V3F, which are closely related to VF, potentially making the larger conjectures (like VP vs. VNP) more tractable.
  • Arity 3 Circuits are Subtle: The paper highlights the surprising subtlety involved in adapting existing circuit complexity results (like depth reduction) to an "arity 3 basis" (where product gates take three inputs), even for seemingly simple polynomials.

Key Results

The paper's main results are theoretical:

  • New VF-complete polynomials: The sum of entries of non-commutative elementary symmetric polynomials in 3x3 matrices of homogeneous linear forms is shown to be VF-complete under homogeneous linear projections. Simpler variants are also identified for subclasses of VF.
  • Connections to GCT Conjectures: The paper reformulates key GCT conjectures (like VP ≠ VNP) in terms of homogeneous linear projections and the newly found complete polynomials.
  • V3F-hardness: The parity-alternating elementary symmetric polynomial is shown to be V3F-hard under homogeneous linear border projections.
  • VF ⊆ V3P: The paper proves that the class of efficiently computable formulas (VF) is contained within the class of efficiently computable circuits over the arity 3 basis (V3P).

Limitations and Future Work

  • VF vs. V3F: The paper explicitly states that their proof does not show VF = V3F, leaving this as an open question.
  • Existence of VP/VNP-complete Graded Families: It remains an open question whether complete graded p-families exist for the classes VP and VNP under homogeneous linear projections. The authors suggest that constructing a universal circuit family for VP might be a path to explore.
  • Arity 3 Basis Subtleties: The paper hints at ongoing research into the implications of the arity 3 basis for circuit complexity, suggesting further exploration is needed.
  • Further Simplification: The authors mention finding even simpler polynomials than the ones presented, which could further simplify the GCT approach.

Summary updated

BibTeX
@inproceedings{dutta2024homogeneous,
  author = {Pranjal Dutta and Fulvio Gesmundo and Christian Ikenmeyer and Gorav Jindal and Vladimir Lysikov},
  title = {{Homogeneous Algebraic Complexity Theory and Algebraic Formulas}},
  booktitle = {ITCS},
  year = {2024},
  doi = {10.4230/lipics.itcs.2024.43},
}
Figure