The determinantal-complexity lower-bound conjecture for the constructed family
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.
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
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.