How Complex Is Complexity? Or What’s a ‘Meta’ for?

The fundamental open questions in complexity theory have resisted our best efforts for more than half a century. But is there any reason to believe that it is fundamentally difficult to show that certain problems are hard to compute? In other words, what is the computational complexity of computational complexity? In his Richard M. Karp Distinguished Lecture this month, Eric Allender (Rutgers University) explored the core themes of the Spring 2023 research program on Meta-Complexity.