Standard

Complexity of distributions and average-case hardness. / Itsykson, Dmitry; Knop, Alexander; Sokolov, Dmitry.

27th International Symposium on Algorithms and Computation, ISAAC 2016. ред. / Seok-Hee Hong. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. стр. 38.1-38.12 (Leibniz International Proceedings in Informatics, LIPIcs; Том 64).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференцииРецензирование

Harvard

Itsykson, D, Knop, A & Sokolov, D 2016, Complexity of distributions and average-case hardness. в S-H Hong (ред.), 27th International Symposium on Algorithms and Computation, ISAAC 2016. Leibniz International Proceedings in Informatics, LIPIcs, Том. 64, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, стр. 38.1-38.12, 27th International Symposium on Algorithms and Computation, ISAAC 2016, Sydney, Австралия, 12/12/16. https://doi.org/10.4230/LIPIcs.ISAAC.2016.38

APA

Itsykson, D., Knop, A., & Sokolov, D. (2016). Complexity of distributions and average-case hardness. в S-H. Hong (Ред.), 27th International Symposium on Algorithms and Computation, ISAAC 2016 (стр. 38.1-38.12). (Leibniz International Proceedings in Informatics, LIPIcs; Том 64). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ISAAC.2016.38

Vancouver

Itsykson D, Knop A, Sokolov D. Complexity of distributions and average-case hardness. в Hong S-H, Редактор, 27th International Symposium on Algorithms and Computation, ISAAC 2016. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2016. стр. 38.1-38.12. (Leibniz International Proceedings in Informatics, LIPIcs). https://doi.org/10.4230/LIPIcs.ISAAC.2016.38

Author

Itsykson, Dmitry ; Knop, Alexander ; Sokolov, Dmitry. / Complexity of distributions and average-case hardness. 27th International Symposium on Algorithms and Computation, ISAAC 2016. Редактор / Seok-Hee Hong. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. стр. 38.1-38.12 (Leibniz International Proceedings in Informatics, LIPIcs).

BibTeX

@inproceedings{34e84989c9fa481f95ed401fdb39a30a,
title = "Complexity of distributions and average-case hardness",
abstract = "We address the following question in the average-case 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 nlogb n steps and a linear-time algorithm A such that for every ensemble of distribution F that samplable in nloga n steps, A correctly decides L on all inputs from {0, 1}n except for 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 exist a language L, an ensemble of polynomial-time computable distributions D, and a linear-time algorithm A such that for every computable in na steps ensemble of distributions F, A correctly decides L on all inputs from {0, 1}n except for 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.",
keywords = "Average-case complexity, Diagonalization, Hierarchy theorem, Sampling distributions",
author = "Dmitry Itsykson and Alexander Knop and Dmitry Sokolov",
year = "2016",
month = dec,
day = "1",
doi = "10.4230/LIPIcs.ISAAC.2016.38",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "38.1--38.12",
editor = "Seok-Hee Hong",
booktitle = "27th International Symposium on Algorithms and Computation, ISAAC 2016",
address = "Germany",
note = "27th International Symposium on Algorithms and Computation, ISAAC 2016 ; Conference date: 12-12-2016 Through 14-12-2016",

}

RIS

TY - GEN

T1 - Complexity of distributions and average-case hardness

AU - Itsykson, Dmitry

AU - Knop, Alexander

AU - Sokolov, Dmitry

PY - 2016/12/1

Y1 - 2016/12/1

N2 - We address the following question in the average-case 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 nlogb n steps and a linear-time algorithm A such that for every ensemble of distribution F that samplable in nloga n steps, A correctly decides L on all inputs from {0, 1}n except for 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 exist a language L, an ensemble of polynomial-time computable distributions D, and a linear-time algorithm A such that for every computable in na steps ensemble of distributions F, A correctly decides L on all inputs from {0, 1}n except for 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.

AB - We address the following question in the average-case 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 nlogb n steps and a linear-time algorithm A such that for every ensemble of distribution F that samplable in nloga n steps, A correctly decides L on all inputs from {0, 1}n except for 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 exist a language L, an ensemble of polynomial-time computable distributions D, and a linear-time algorithm A such that for every computable in na steps ensemble of distributions F, A correctly decides L on all inputs from {0, 1}n except for 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.

KW - Average-case complexity

KW - Diagonalization

KW - Hierarchy theorem

KW - Sampling distributions

UR - http://www.scopus.com/inward/record.url?scp=85010790010&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ISAAC.2016.38

DO - 10.4230/LIPIcs.ISAAC.2016.38

M3 - Conference contribution

AN - SCOPUS:85010790010

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 38.1-38.12

BT - 27th International Symposium on Algorithms and Computation, ISAAC 2016

A2 - Hong, Seok-Hee

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 27th International Symposium on Algorithms and Computation, ISAAC 2016

Y2 - 12 December 2016 through 14 December 2016

ER -

ID: 49785539