Abstract | ||
---|---|---|
A certifying algorithm is an algorithm that produces with each output, a certificate or witness (easy-to-verify proof) that the particular output has not been compromised by a bug. A user of a certifying program
P (= the implementation of a certifying algorithm) inputs x, receives an output y and a certificate w, and then checks, either manually or by use of a checking program, that w proves that y is a correct output for input x. In this way, he/she can be sure of the correctness of the output without having to trust P. We refer the reader to the recent survey paper [9] for a detailed discussion of certifying algorithms.
|
Year | DOI | Venue |
---|---|---|
2010 | 10.1007/978-3-642-14553-7_1 | Frontiers in Algorithmics |
Keywords | Field | DocType |
certifying algorithm | Computer science,Correctness,Algorithm,Witness,Theoretical computer science,Certificate | Conference |
Volume | ISSN | ISBN |
6213 | 0302-9743 | 3-642-14552-3 |
Citations | PageRank | References |
2 | 0.40 | 6 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Kurt Mehlhorn | 1 | 5314 | 853.36 |
Pascal Schweitzer | 2 | 214 | 16.94 |