The Factor Conjecture for arithmetic circuit complexity
The Factor Conjecture for arithmetic circuit complexity
Let be a field of characteristic zero, let , and let be a factor of . Write for the size of the smallest arithmetic circuit computing from the variables and arbitrary constants in .
Factor Conjecture. One has
This is a central question in algebraic complexity theory. It is known for approximate complexity, and the source explains that a possible failure in the exact setting could only arise when occurs with exponentially large multiplicity.
Sources & referencesView supporting material
Primary source
Peter Bürgisser and Gorav Jindal, “On the Hardness of PosSLP”, arXiv:2307.08008 (2023).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.