2008/06/16 by Gábor Erdélyi, Gabor Erdelyi, Erdelyi, Gabor +6
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #F.1.3 #F.2.2 #FOS: Computer and information sciences #I.2.11 #Matrix Theory and Algorithms #Multiagent Systems (cs.MA) #Stability and Control of Uncertain Systems #cs.CC #cs.GT #cs.MA
paper · pdf · doi:10.48550/arxiv.0806.2555
arxiv created 2008/06/16 · openalex publication_date 2008/06/16 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We 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].