Self-correcting polynomial programs

摘要

In this paper, we introduce a new self-correction algorithm that requires less queries than the simple majority vote. We also introduce new random self-reducibility formulas.