Let t:bN→N. For “nice” sequences of distributions P_n and Q_n on spaces Omega_n, let L_n=dP_n/dQ_n denote the likelihood ratio, and let L_n^≤ D(n) be its orthogonal projection onto polynomials of degree at most D(n) under Q_n. A function f_n:Omega_n→textttp,textttq strongly distinguishes P_n from Q_n if lim_n→∞Q_n[f_n(Y)=textttq]=lim_n→∞P_n[f_n(Y)=textttp]=1. Low-degree likelihood-ratio conjecture. If |L_n^≤ D(n)|_L^2(Q_n) remains bounded as n→∞ whenever D(n)≤ t(n)·operatornamepolylog(n), then there is no sequence of functions f_n computable in time n^t(n) that strongly distinguishes P_n and Q_n. This conjecture formalizes the heuristic that degree-D polynomials are as powerful as algorithms with runtime roughly n^widetildeTheta(D), and is a central basis for using low-degree likelihood-ratio bounds to predict computational hardness.

The low-degree likelihood-ratio conjecture for computational indistinguishability

Let $t:b{N}\to\mathbb{N}$ . For “nice” sequences of distributions $\mathbb{P}_n$ and $\mathbb{Q}_n$ on spaces $\Omega_n$ , let $L_n=d\mathbb{P}_n/d\mathbb{Q}_n$ denote the likelihood ratio, and let $L_n^{\leq D(n)}$ be its orthogonal projection onto polynomials of degree at most $D(n)$ under $\mathbb{Q}_n$ . A function $f_n:\Omega_n\to\{\texttt{p},\texttt{q}\}$ strongly distinguishes $\mathbb{P}_n$ from $\mathbb{Q}_n$ if

\lim_{n\to\infty}\mathbb{Q}_n[f_n(Y)=\texttt{q}]=\lim_{n\to\infty}\mathbb{P}_n[f_n(Y)=\texttt{p}]=1.

Low-degree likelihood-ratio conjecture. If $\|L_n^{\leq D(n)}\|_{L^2(\mathbb{Q}_n)}$ remains bounded as $n\to\infty$ whenever $D(n)\leq t(n)\cdot\operatorname{polylog}(n)$ , then there is no sequence of functions $f_n$ computable in time $n^{t(n)}$ that strongly distinguishes $\mathbb{P}_n$ and $\mathbb{Q}_n$ . This conjecture formalizes the heuristic that degree- $D$ polynomials are as powerful as algorithms with runtime roughly $n^{\widetilde{\Theta}(D)}$ , and is a central basis for using low-degree likelihood-ratio bounds to predict computational hardness.

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

The low-degree likelihood-ratio conjecture for computational indistinguishability
Let $\PP_n$ and $\QQ_n$ be “nice” sequences of distributions, let $\LL_n$ be their likelihood ratio, and let $\LL_n^{\le D_n}$ denote its degree- $D_n$ projection in $L_2(\QQ_n)$ . A test $\Phi_n:\RR^{n(p+q)}\mapsto\{0,1\}$ strongly distinguishes $\PP_n$ and $\QQ_n$ if it succeeds with vanishing error in the corresponding hypothesis-testing problem. Suppose $t:\NN\mapsto\NN$ . Low-degree likelihood-ratio conjecture. If
$\|\LL_n^{\le D_n}\|_{L_2(\QQ_n)}=O(1)$
as $n\to\infty$ whenever $D_n\le t(n)\operatorname{polylog}(n)$ , then there is no time- $n^{t(n)}$ test $\Phi_n$ that strongly distinguishes $\PP_n$ and $\QQ_n$ . This conjecture formalizes the heuristic that low-degree projections of likelihood ratios capture the power of computationally efficient distinguishing tests; the source also notes that a bound at degree of order $(\log n)^{1+\varepsilon}$ would rule out polynomial-time strong distinguishers. Its resolution status is not specified in the source.
source: Nilanjana Laha and Rajarshi Mukherjee, “On Support Recovery with Sparse CCA: Information Theoretic and Computational Limits”, arXiv:2108.06463 (2022).

Sources & referencesView supporting material

Primary source

Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein and Afonso S. Bandeira, “Subexponential-Time Algorithms for Sparse PCA”, arXiv:1907.11635 (2022).

1 week ago

The low-degree likelihood-ratio conjecture for computational indistinguishability

Equivalent formulations 1

The low-degree likelihood-ratio conjecture for computational indistinguishability

Primary source

Progress summary

Solutions 0