← All problems

The low-degree polynomial conjecture on computational indistinguishability

2 years old · documented by

Let Pn\mathbb{P}_n and Qn\mathbb{Q}_n denote a sequence of probability measures with sample space Rnk\mathbb{R}^{n^k}, where k=O(1)k=O(1). Suppose that every polynomial ff of degree O(log⁡n)O(\log n) satisfying

EQnf2=1\mathbb{E}_{\mathbb{Q}_n} f^2=1

is bounded under Pn\mathbb{P}_n with high probability as n→∞n\to\infty, and that some further regularity conditions hold. Low-degree polynomial conjecture. There is no polynomial-time test distinguishing Pn\mathbb{P}_n from Qn\mathbb{Q}_n with both type I and type II errors tending to 00 as n→∞n\to\infty. 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
  1. 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.