Concepedia

Short PCPPs verifiable in polylogarithmic time with O(1) queries

Thilo Mie

Annals of Mathematics and Artificial Intelligence · 2009 · 32 citations · 12 references

DOI

Concepts

References

12

Proof verification and the hardness of approximation problems

Sanjeev Arora, Carsten Lund, Rajeev Motwani et al. · Journal of the ACM · 1998 · 1.4K citations · Full text

, , +14

Probabilistic checking of proofs

Sanjeev Arora · Journal of the ACM · 1998 · 1.2K citations · Full text

, , +14

Proof verification and hardness of approximation problems

Sanjeev Arora, Carsten Lund, R. Motwani et al. · 1992 · 744 citations

, , +16

Checking computations in polylogarithmic time

László Babai, Lance Fortnow, Leonid A. Levin et al. · 1991 · 620 citations · Full text

, , +6

Interactive proofs and the hardness of approximating cliques

Uriel Feige, Shafi Goldwasser, László Lovász et al. · Journal of the ACM · 1996 · 524 citations · Full text

, , +16