The informal low degree conjecture for computational thresholds
Statement
Let be a sequence of CLVMs, giving rise to sequences of measures and on , where . Let denote the low-degree advantage, and let strong detection mean distinguishing the two measures with the corresponding strong-detection guarantee. For sufficiently nice priors and channels, Informal low degree conjecture. (i) If, for some , as , then no test computable in time polynomial in achieves strong detection between and . (ii) If, for some , as , then no test computable in time achieves strong detection between and . This conjecture formalizes the heuristic that low-degree polynomials capture the power of efficient algorithms at a given runtime budget. It is explicitly described as rough and imprecise, and known pathological counterexamples require additional clauses; nevertheless, it often gives hardness predictions consistent with other evidence.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.