Human intelligence represents an evolutionary puzzle: what task justifies such a large and metabolically expensive brain? The social brain hypothesis argues that our intelligence evolved primarily to cope with social, rather than physical, challenges; we are smart specifically because we are social. Considerable evidence has accumulated in support of this hypothesis, but our social groups appear to be larger than our brains should be able to manage. Here we report on a research program focusing on compression heuristics, or schemata that allow larger amounts of social information to be accommodated in the same physical memory. These heuristics, including triadic closure, kinship relations, and affective balance, help bridge the gap between brain and behavior and explain the high level of problem-solving intelligence present in Homo sapiens.