The low-degree polynomial conjecture on computational indistinguishability
Let and denote a sequence of probability measures with sample space , where . Suppose that every polynomial of degree satisfying
is bounded under with high probability as , and that some further regularity conditions hold. Low-degree polynomial conjecture. There is no polynomial-time test distinguishing from with both type I and type II errors tending to as . The conjecture is a proposed computational lower-bound principle: control of all low-degree polynomials should rule out efficient tests, subject to the stated regularity conditions.
References
- Jiashun Jin, Zheng Tracy Ke, Paxton Turner and Anru R. Zhang, “Phase transition for detecting a small community in a large network”, arXiv:2303.05024 (2023).
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.