How does a denoiser work? Recently I tried blender+cycles with denoiser turned on, and it's just awesome. I can use much fewer samples to get a better image. I became curious how does a denoiser work internally. I guess it's definitely not a simple image blur.

From my observation, a tile gets denoised only when the surrounding 3x3 tiles all gets rendered. This seems a little bit weird to me though. How can a neighbor tile provides any useful information to denoise the current tile?

I'm sure different denoisers have various implementations. It would be good though if someone can tell me how does a denoiser work in general, or point me to relevant literature.
I am a beginner at blender but found your question amusing enough to want to find out. According to this source, Blender has just adopted Intel's Open Image Denoiser. 

From what I understand (experienced users correct me if I am wrong): It analyses the samples at the pixel level in relation to one another defined by the radius setting. Then using a monte carlo trained deep learning library it identifies noise problem areas and reduces the number of samples to simplify the path traced samples that have acted unrealistically with their random bounces.