The Factor Conjecture for arithmetic circuit complexity

Let F\mathbb{F} be a field of characteristic zero, let fF[x1,,xn]f\in\mathbb{F}[x_1,\ldots,x_n], and let gg be a factor of ff. Write L(h)L(h) for the size of the smallest arithmetic circuit computing hh from the variables and arbitrary constants in F\mathbb{F}.

Factor Conjecture. One has

L(g)poly(L(f)+deg(g)).L(g)\leq\operatorname{poly}(L(f)+\deg(g)).

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 gg 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.