Some Results on Average-Case Hardness Within the Polynomial Hierarchy

DOI10.1007/11944836_19zbMath1177.68096OpenAlexW1501939853MaRDI QIDQ5385985

A. Pavan, Rahul Santhanam, N. V. Vinodchandran

Publication date: 17 April 2008

Published in: FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://www.pure.ed.ac.uk/ws/files/17974469/Pavan_Santhanam_ET_AL_2006_Some_Results_on_Average_Case_Hardness_within_the_Polynomial_Hierarchy.pdf

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

Unnamed Item ⋮ The 1-Versus-2 Queries Problem Revisited ⋮ The 1-versus-2 queries problem revisited ⋮ Unnamed Item ⋮ PAC-learning gains of Turing machines over circuits and neural networks

This page was built for publication: Some Results on Average-Case Hardness Within the Polynomial Hierarchy