What introductory material is available linking complexity theory to cognitive science? Does complexity theory speak to cognitive science?
If yes, where can I find some material to explore that is suitable for undergraduate level understanding?
In particular, is there any audio contennt on this?
In general, there are two types of 'complexity' that are studied. Usually, when people talk about 'complexity', especially on the internet, they mean Santa Fe Institute style complexity. This is a vague and poorly defined concept that has struggled for a number of years without making significant progress. It uses pretty words, but has yet to deliver on any real results. I will not discuss it more in this answer.

The other type of complexity is computational complexity theory as studied by theoretical computer science. In general, this field is too mathematical and too rigorous to engage with most of cognitive science and psychology, but there are a few connections. I recommend looking at the cstheory question: What is the complexity class most closely associated with what the human mind can accomplish quickly?

In that question, the author is curious to know which complexity class most closely resembles what humans can achieve. My favourite answer discusses the Tractable Cognition thesis. For reference, see these papers:


Iris van Rooij. The Tractable Cognition thesis. Cognitive Science, 32, pp. 939-984, 2008.
Iris van Rooij. Parameters that make Cognitive Work Light. FPT News: Parameterized Complexity Newsletter, June 2009.


A specialized part of computational complexity known as computational learning theory has been particularily notable in trying to make connections to cognitive science, in particular linguists. Gold's theorem on the non-learnability of certain families of formal languages was especially relevant in the early days of the poverty of the stimulus debate. You can learn more about it in these two questions:


Applications of computational learning theory in the cognitive sciences
General mathematical frameworks of language acquisition since Gold


Keep in mind, that computational complexity is advanced material and requires a decent mathematical sophistication. However, with difficulty comes insights.