PPT Slide
Probabilistic Property testing is a new algorithmic technique which examines only constant probabilistic samples of the input and works in complexity independent of the size of the input trading off speed for accuracy. It has been applied with great success to testing NP-hard graph properties, testing algebraic and combinatorial functional properties such as linearity and monotonicity, and testing properties of classical linear algebra structures.
property testing of NP hard Graph problems such as graph coloring in constant time by Goldwasser, Goldreich and Ron
"Improved Testing Algorithms for Monotonicity", by Dodis, Goldreich, Lehman, Raskhodnikova, Ron, and Samorodnitsky, appeared in the Proceedings of RANDOM, August 1999
Apply property testing to properties such as routing and congestion on
graphs resulting from the web