Complexity of Distributions and Average-Case Hardness

Authors Dmitry Itsykson, Alexander Knop, Dmitry Sokolov



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.38.pdf
  • Filesize: 473 kB
  • 12 pages

Document Identifiers

Author Details

Dmitry Itsykson
Alexander Knop
Dmitry Sokolov

Cite AsGet BibTex

Dmitry Itsykson, Alexander Knop, and Dmitry Sokolov. Complexity of Distributions and Average-Case Hardness. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 38:1-38:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ISAAC.2016.38

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 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 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 n^a 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
  • hierarchy theorem
  • sampling distributions
  • diagonalization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. László Babai, Paul Erdős, and Stanley Selkow. Random graph isomorphism. SIAM J. Comput., 9(3):628-635, 1980. Google Scholar
  2. Shai Ben-David, Benny Chor, Oded Goldreich, and Michael Luby. On the theory of average case complexity. J. Comput. Syst. Sci., 44(2):193-219, 1992. URL: http://dx.doi.org/10.1016/0022-0000(92)90019-F.
  3. Yuri Gurevich and Saharon Shelah. Expected computation time for hamiltonian path problem. SIAM J. Comput., 16(3):486-502, 1987. Google Scholar
  4. Dan Gutfreund, Ronen Shaltiel, and Amnon Ta-Shma. If NP languages are hard on the worst-case, then it is easy to find their hard instances. Computational Complexity, 16(4):412-441, 2007. URL: http://dx.doi.org/10.1007/s00037-007-0235-8.
  5. Dmitry Itsykson, Alexander Knop, and Dmitry Sokolov. Heuristic time hierarchies via hierarchies for sampling distributions. In Algorithms and Computation - 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings, pages 201-211, 2015. Google Scholar
  6. Ming Li and Paul M.B. Vitanyi. Average case complexity under the universal distribution equals worst case complexity. Information Processing Letters, 42:145-149, 1992. Google Scholar
  7. Konstantin Pervyshev. On heuristic time hierarchies. In IEEE Conference on Computational Complexity, pages 347-358, 2007. URL: http://dx.doi.org/10.1109/CCC.2007.20.
  8. E. R. van Dama and M. Muzychuk. Some implications on amorphic association schemes. Journal of Combinatorial Theory, Series A, 117:111-127, 2010. Google Scholar
  9. Thomas Watson. Time hierarchies for sampling distributions. SIAM J. Comput., 43(5):1709-1727, 2014. URL: http://dx.doi.org/10.1137/120898553.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail