Eric Allender's research focuses on computational complexity theory, the aim of which is to prove that certain problems are essentially impossible to compute. One practical application of this is found in shopping online: the systems that supposedly make online shopping secure rely on unproven complexity-theoretic assumptions. In fact, proving (or disproving) these assumptions form some of the most important unsolved questions in mathematics and computer science. Instead of searching for clever programs to solve problems, a complexity theoretician tries to prove that there is no clever program.

Over the decades, this theory has been intimately connected to other fundamental questions such as: What is randomness? What is a proof? Can computers learn?