I think it can be optimized quite a lot by not using a stock PNG decoder library, because all images are quite simple and can be generated from non-pixelated smaller sprites (many images are pre-scaled by 2x, which can be done during the postprocessing) or from a simple algorithmic code.

Right. I meant with the graphics though.

Weirdly, I think the challenge would be more difficult going to Android than adding graphics while keeping the size down.

It would not at all surprise me to see a near perfect Flappy Bird under 4k (graphics and all) as a PC .com

I'd be curious to see what the minimum size of a simple C program would be. Say something that displayed a pixel that bounced up and down as you tapped.