Frequency of Correctness versus Average-Case Polynomial Time and Generalized Juntas
classification
💻 cs.CC
cs.GTcs.MA
keywords
correctnesspolynomialrespecttimealgorithmaverageaverage-casecorrect
read the original abstract
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].
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.