This course will cover two subjects in complexity that have particularly come to the fore in recent years:
Despite the best efforts of researchers for over 50 years since the P vs NP question was formulated, the best algorithms we have for SAT and other NP-complete problems are still exponential in the worst case and barely improve on brute force. If these are representative of the correct level of complexity, which seems a reasonable stronger conjecture than P ≠ NP, our usual ways of proving relationships between NP problems need to be rethought, both from a theoretical and practical point of view, and radically new relationships between problems emerge, a subject termed "fine-grain complexity". This yields surprising connections that have produced a web of problem-solving relationships well beyond the usual resource-focused complexity classes, for example, showing how improving existing polynomial-time algorithms for well-known problems is tied to improving exponential-time algorithms for SAT.
A number of longstanding problems in computational complexity have been resolved in the last decade by showing how simple forms of function composition let us convert hardness results proven in weak models of computation into hardness results for more powerful models of computation, a methodology that has been termed "lifting". We discuss lifting techniques and the some of the longstanding problems resolved using them. We then focus on a number of open problems and approaches to resolving them.