ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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

lim⁡n→∞Qn[fn(Y)=q]=lim⁡n→∞Pn[fn(Y)=p]=1.\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 ∥Ln≤D(n)∥L2(Qn)\|L_n^{\leq D(n)}\|_{L^2(\mathbb{Q}_n)} remains bounded as n→∞n\to\infty whenever D(n)≤t(n)⋅polylog⁡(n)D(n)\leq t(n)\cdot\operatorname{polylog}(n), then there is no sequence of functions fnf_n computable in time nt(n)n^{t(n)} that strongly distinguishes Pn\mathbb{P}_n and Qn\mathbb{Q}_n. This conjecture formalizes the heuristic that degree-DD polynomials are as powerful as algorithms with runtime roughly nΘ~(D)n^{\widetilde{\Theta}(D)}, and is a central basis for using low-degree likelihood-ratio bounds to predict computational hardness.

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.