Efficient computation of the degree of a neural ideal

Let d2d\ge 2 and let C2[n]\mathcal C\subseteq 2^{[n]} be a code. A pseudo-monomial is an element of the canonical form CF(JC)\operatorname{CF}(J_\mathcal C) of the neural ideal JCJ_\mathcal C, and its degree is the number of factors in the pseudo-monomial.

Efficient degree computation conjecture. There is a polynomial-time algorithm that, given the codewords of C\mathcal C as binary vectors of length nn, determines whether every pseudo-monomial in CF(JC)\operatorname{CF}(J_\mathcal C) has degree at most dd.

Efficiently computing the canonical form is relevant to the proposed algorithm for recognizing inductively pierced codes, since the algorithm begins by computing CF(JC)\operatorname{CF}(J_\mathcal C). The supplied statement asserts the algorithm's existence but gives no resolution, so its status remains open.

Sources & referencesView supporting material

Primary source

Ryan Curry, R. Amzi Jeffs, Nora Youngs and Ziyu Zhao, “Recognizing and Realizing Inductively Pierced Codes”, arXiv:2207.06266 (2022).

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.