TR15-174 Authors: Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Publication: 5th November 2015 23:23

Downloads: 1606

Keywords:

We address a natural question in average-case complexity: does there exist a language $L$ such that for all easy distributions $D$ the distributional problem $(L, D)$ is easy on the average while there exists some more hard distribution $D'$ such that $(L, D')$ is hard on the average? We consider two complexity measures of distributions: complexity of sampling and complexity of computing the distribution function. The most interesting measure is the complexity of sampling. We prove that for every $b > a > 0$ there exists a language $L$, an ensemble of distributions $D$ samplable in $n^{\log^b n}$ steps and a linear-time algorithm $A$ such that for every ensemble of distribution $F$ that samplable in $n^{\log^a n}$ steps, $A$ correctly decides $L$ on all inputs from $\{0, 1\}^n$ except of a set that has infinitely small $F$-measure, and for every algorithm $B$ there are infinitely many $n$ such that the set of all elements of $\{0, 1\}^n$ for which $B$ correctly decides $L$ has infinitely small $D$-measure.

In case of complexity of computing the distribution function we prove the following tight result: for every $a > 0$ there exists a language $L$, an ensemble of polynomial-time computable distributions $D$, and a linear-time algorithm $A$ such that for every computable in $n^a$ steps ensemble of distributions $F$, $A$ correctly decides $L$ on all inputs from $\{0, 1\}^n$ except a set that has $F$-measure at most $2^{-n / 2}$, and for every algorithm $B$ there are infinitely many $n$ such that the set of all elements of $\{0, 1\}^n$ for which $B$ correctly decides $L$ has $D$-measure at most $2^{-n + 1}$.