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

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=n1ak=\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.

Sources & referencesView supporting material

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.