Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-174 | 18th October 2015 01:37

Complexity of distributions and average-case hardness

RSS-Feed




TR15-174
Authors: Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
Publication: 5th November 2015 23:23
Downloads: 543
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