We show that given a quantum measurement, for an overwhelming majority of pure states, no meaningful information is produced. This is independent of the number of outcomes of the quantum measurement. Due to conservation inequalities, such random noise cannot be processed into coherent data.

more >>>

We prove a SOS degree lower bound for the planted clique problem on Erd{\"o}s-R\'enyi random graphs $G(n,1/2)$. The bound we get is degree $d=\Omega(\epsilon^2\log n/\log\log n)$ for clique size $\omega=n^{1/2-\epsilon}$, which is almost tight. This improves the result of \cite{barak2019nearly} on the ``soft'' version of the problem, where the family ... more >>>

PPSZ, for long time the fastest known algorithm for k-SAT, works by going through the variables of the input formula in random order; each variable is then set randomly to 0 or 1, unless the correct value can be inferred by an efficiently implementable rule (like small-width resolution; or being ... more >>>