The determinantal-complexity lower-bound conjecture for the constructed family

About 10 years old · traced to

Let a>0a>0 be a sufficiently small constant, let ll be the nearest odd integer to nan^a, choose disjoint odd-size subsets C1,…,Ck⊆[n]C_1,\ldots,C_k\subseteq[n] with k=⌊n1−a⌋k=\lfloor n^{1-a}\rfloor, choose a random regular non-bipartite graph GnG_n on nn nodes of degree n\sqrt n, and let QQ be the face of NPT⁡(det⁡(TG))\operatorname{NPT}(\det(T_G)) obtained by setting the odd-size constraints corresponding to these subsets to equalities. Define fn=det⁡(TG)∣Qf_n=\det(T_G)|_Q.

Constructed-family determinantal lower-bound conjecture. If a>0a>0 is small enough, then, with high probability, fnf_n cannot be expressed as a symbolic determinant of size at most n1+δn^{1+\delta}, for a sufficiently small positive constant δ\delta.

The family is approximable by symbolic determinants of size nn and has a polynomial-size symbolic determinant representation, so the conjecture would provide a strong separation between its approximative and ordinary determinantal complexity. The source does not establish this lower bound.

References

Primary source

Joshua A. Grochow, Ketan D. Mulmuley and Youming Qiao, “Boundaries of VP and VNP”, arXiv:1605.02815 (2016).

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.