ECCC-Report TR15-174https://eccc.weizmann.ac.il/report/2015/174Comments and Revisions published for TR15-174en-usThu, 05 Nov 2015 23:23:39 +0200
Paper TR15-174
| Complexity of distributions and average-case hardness |
Dmitry Itsykson,
Alexander Knop,
Dmitry Sokolov
https://eccc.weizmann.ac.il/report/2015/174We 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}$.Thu, 05 Nov 2015 23:23:39 +0200https://eccc.weizmann.ac.il/report/2015/174