Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR15-174 | 18th October 2015 01:37

#### Complexity of distributions and average-case hardness

TR15-174
Authors: Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
Publication: 5th November 2015 23:23
Keywords:

Abstract:

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}\$.

ISSN 1433-8092 | Imprint