Going back to the magpie though, they don't have a cerebral cortex at all, yet exhibit remarkably intelligent behavior (tool usage, self-recognition). So, what's up with all the smart corvids?
I'm not an expert here, but I find this interesting enough to have done some recreational reading. What I know is that corvids and parrots have a different brain structure to mammals (they diverged about 300M years ago) but, in an example of convergent evolution, have developed areas that serve the same function as our neocortex. It's called the pallium, and has a very different organisation to our neocortex. Instead of the six layers in our neocortex they have clumps of neurons called nuclei. They also have much higher neuron density than mammals, allowing them to fit more smarts into their tiny heads :-)
It's almost as if we don't know everything and the animal brain is actually a bit more complex than a primitive multilayered perceptron neural network!
To follow up on noelwelsh's comment, you might find this review interesting: http://comparative-cognition-and-behavior-reviews.org/2009/v...
It talks about how our understanding of avian brains has changed and why they can be so smart (short answer, we're not sure yet)
Because of mass, the number of neurons, how many calories we can toss at them, and how many calories a fetus/newborn can be guaranteed.
Even if you have trainable brain, with neurons that can communicate with more percentage of the brain than a primates. You're still on a diet of hundreds of calories instead of thousands.
Looking at smaller animals cognitive abilities is newish. But does look like it will be going interesting places.
Non-expert here, but I read some research on this topic. Since avians need to keep their overall weight light, their neurons evolved in such a way as to be smaller and less complex individually than mammals. This allows them to have more neurons in a given area/volume. Also, if I remember correctly, their brains are more decentralized and have fewer specialized structures.
A few links:
https://www.sciencedaily.com/releases/2012/10/121001151953.h...
http://www.sciencedirect.com/science/article/pii/S0960982205...
http://www.pnas.org/content/113/26/7255.full