Combinatorial interpretations

Abstract:
In enumerative combinatorics, one is often asked to count the number of combinatorial objects. But the inverse problem is even more interesting: given some numbers, do they have a combinatorial interpretation? I will give a broad survey of this problem, formalize the question in the language of computational complexity, and describe connections to deep results and open problems in algebraic and probabilistic combinatorics.