Frequency of Correctness versus Average-Case Polynomial Time and Generalized Juntas

Simple item page
dc.creatorErdelyi, Gabor
dc.creatorHemaspaandra, Lane A.
dc.creatorRothe, Joerg
dc.creatorSpakowski, Holger
dc.date2008-06-16
dc.date.accessioned2026-07-07T09:44:49Z
dc.date.available2026-07-07T09:44:49Z
dc.descriptionWe prove that every distributional problem solvable in polynomial time on the average with respect to the uniform distribution has a frequently self-knowingly correct polynomial-time algorithm. We also study some features of probability weight of correctness with respect to generalizations of Procaccia and Rosenschein's junta distributions [PR07b].
dc.identifierhttps://arxiv.org/abs/0806.2555
dc.identifierhttp://arxiv.org/abs/0806.2555
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/163007
dc.subjectComputational Complexity
dc.subjectComputer Science and Game Theory
dc.subjectMultiagent Systems
dc.subjectF.1.3; F.2.2; I.2.11
dc.titleFrequency of Correctness versus Average-Case Polynomial Time and Generalized Juntas
dc.typetext

Files

Collections

arXiv