Encoding invariance in average case complexity

DOI10.1007/s00224-013-9517-5zbMath1380.68233OpenAlexW2060628418MaRDI QIDQ1678756

Nikolai K. Vereshchagin

Publication date: 7 November 2017

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-013-9517-5

zbMATH Keywords

average-case complexitypolynomial-time computable distributionpolynomial-time samplable distribution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (1)

A remark on pseudo proof systems and hard instances of the satisfiability problem

Cites Work

• On the theory of average case complexity
• Average-Case Complexity
• Average Case Complete Problems
• A Pseudorandom Generator from any One-way Function

This page was built for publication: Encoding invariance in average case complexity