Efficient computation of the degree of a neural ideal
Efficient computation of the degree of a neural ideal
Let and let be a code. A pseudo-monomial is an element of the canonical form of the neural ideal , 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 as binary vectors of length , determines whether every pseudo-monomial in has degree at most .
Efficiently computing the canonical form is relevant to the proposed algorithm for recognizing inductively pierced codes, since the algorithm begins by computing . 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
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.