3 problems

Let $k>r$ be constants, let $Q$ be any distribution over $k$-clauses with $N$ variables and complexity $r$, and let $0<\eta<1$. Define the noisy planted distribution by … where…

Computational indistinguishability conjecture. While the two versions are statistically distinguishable, it is impossible to distinguish them in polynomial time with non-trivial er…

The pRFCW and pSK models have matching lower and upper bounds in the relevant high-temperature, large-clique regime. Minimax-rate conjecture. The minimax optimal rate for the plant…