The determinantal-complexity lower-bound conjecture for the constructed family
Let be a sufficiently small constant, let be the nearest odd integer to , choose disjoint odd-size subsets with , choose a random regular non-bipartite graph on nodes of degree , and let be the face of obtained by setting the odd-size constraints corresponding to these subsets to equalities. Define .
Constructed-family determinantal lower-bound conjecture. If is small enough, then, with high probability, cannot be expressed as a symbolic determinant of size at most , for a sufficiently small positive constant .
The family is approximable by symbolic determinants of size 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
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.