I love the demoscene a lot, especially those small 4K exefiles. They don't have any dependencies except for the files already found in windows and they exhibit the awesome power of programming: 3D graphics + sound, all in 4K.
How is this possible? What's the language they are using? What are the tools of trade, best practices and important websites?
In the meantime I have found a great website dealing with 4K coding:
compression algorithms obviously feature heavily, as do short mechanisms for indexing large amounts of data and a deep knowledge of the available libraries on the target system. (That stuff can just be linked in.)
If I were you, I'd start by reverse-engineering your favourite 4k demos; perhaps starting with ones from 7-10 years ago, and working forwards to follow the state of the art as it progresses. Analysing your compiler's output is a good place to start, too, though they tend to optimize for speed rather than for space.
Techniques for embedded programming may also be helpful, given the constraints they operate under regularly.
Inigo Quilez has some examples of 1K and 4K intros. You can learn a lot from them. Check out his other articles too.
The article on Tiny PE by Alexander Sotirov is interesting too.
Might not be quite what you're looking for, but in the same spirit: There are several Java 4k contests. The objective being to create a Java demo or even game (!) that completely fits into a single JAR of max 4096 bytes.
See e.g.
http://www.mojang.com/notch/j4k/l4kd/
or
http://javaunlimited.net/contests/java4k.php
One might argue that Java makes it much easier (since you can use the whole runtime), but it's still impressive (and you are cross-platform and don't need to learn assembler ;)).
