Itsykson, Dmitry ;
Knop, Alexander ;
Sokolov, Dmitry
Complexity of Distributions and AverageCase Hardness
Abstract
We address the following question in the averagecase complexity: does there exists 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: the complexity of sampling and the complexity of computing the distribution function.
For the complexity of sampling of distribution, we establish a connection between the above question and the hierarchy theorem for sampling distribution recently studied by Thomas Watson. Using this connection we prove that for every 0 < a < b there exist a language L, an ensemble of distributions D samplable in n^{log^b n} steps and a lineartime 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 for a set that has infinitely small Fmeasure, 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 Dmeasure.
In case of complexity of computing the distribution function we prove the following tight result: for every a > 0 there exist a language L, an ensemble of polynomialtime computable distributions D, and a lineartime 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 for a set that has Fmeasure 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 Dmeasure at most 2^{n+1}.
BibTeX  Entry
@InProceedings{itsykson_et_al:LIPIcs:2016:6808,
author = {Dmitry Itsykson and Alexander Knop and Dmitry Sokolov},
title = {{Complexity of Distributions and AverageCase Hardness}},
booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages = {38:138:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770262},
ISSN = {18688969},
year = {2016},
volume = {64},
editor = {SeokHee Hong},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6808},
URN = {urn:nbn:de:0030drops68083},
doi = {10.4230/LIPIcs.ISAAC.2016.38},
annote = {Keywords: averagecase complexity, hierarchy theorem, sampling distributions, diagonalization}
}
07.12.2016
Keywords: 

averagecase complexity, hierarchy theorem, sampling distributions, diagonalization 
Seminar: 

27th International Symposium on Algorithms and Computation (ISAAC 2016)

Issue date: 

2016 
Date of publication: 

07.12.2016 