On the Power of Self-Testers and Self-Correctors (Special Section on Cryptography and Information Security)

スポンサーリンク

概要

• 論文の詳細を見る

• Checkers, self-testers, and self-correctors for a function f are powerful tools in designing programs that compute f. However, the relationships among them have not been known well. In this paper, we first show that (1) if oneway permutations exist, then there exists a language L that has a checker but does not have a self-corrector. We then introduce a novel notion of "self-improvers" that transform a faulty program into a less faulty program, and show that (2) if a function f has a self-tester/corrector pair, then f has a self-improver. As the applications of self-improvers, we finally show that (3) if a function f has a self-tester/corrector pair, then f has a flexible self-tester and (4) if a function f has a self-tester/corrector pair, then f has a self-improver that transforms a faulty program into an almost correct program.

• 社団法人電子情報通信学会の論文
• 1997-01-25

著者

• Mori Hiroyoshi

  Interdisciplinary Graduate School Of Science And Engineering Tokyo Institute Of Technology:ntt Commu

• Itoh Toshiya

  Interdisciplinary Graduate School Of Science And Engineering Tokyo Institute Of Technology

関連論文

• Checkers for Adaptive Programs
• 12) VCGs IN PATIENTS WITH OLD MYOCARDIAL INFARCTION SHOWING INDEFINITE ECG FINDINGS: COMPARISON WITH CAG, LVG AND SCG
• Alternative Necessary and Sufficient Conditions for Collision Intractable Hashing
• A Note on AM Languages Outside NP ⋃ co-NP (Special Section on Cryptography and Information Security)
• Demonstrating Possession without Revealing Factors (Special Section on Cryptography and Information Security)
• On the Power of Self-Testers and Self-Correctors (Special Section on Cryptography and Information Security)
• On the Knowledge Tightness of Zero-Knowledge Proofs (Special Section on Cryptography and Information Security)
• Efficient Private Information Retrieval (Special Section on Cryptography and Information Security)
• On the Oracle Entropy and the Average Case Oracle Measure of Knowledge Complexity (Special Section on Cryptography and Information Security)
• On the Knowledge Complexity of Arthur-Merlin Games (Special Section on Cryptography and Information Security)

スポンサーリンク