Theoretical computer science looks at fundamental questions about computation by creating formal models of computation and understanding the resources needed to solve general and specific algorithmic questions.

The theoretical computer science at Northwestern group has expertise in algorithms and computational complexity, with a particular emphasis on how they relate to economic questions.

Faculty

Lance Fortnow specializes in computational complexity and its connections to randomness, proof systems, property testing, learning theory, economics, quantum computing and biology. His major results include exhibiting the surprising power of interactive and probabilistically checkable proof systems and developing the first non-trivial time-space tradeoffs for the seminal NP-complete problem Satisfiability on random-access computers.

Fortnow is editor-in-chief of ACM Transactions on Computation Theory, serves as SIGACT vice-chair and originated the Computational Complexity Weblog.

Jason Hartline has interests in randomized, online, and approximation algorithms and their application in multi-user settings such as the Internet. This field is known as algorithmic mechanism design and lies at the intersection of the theoretical computer science topic of algorithms and the microeconomic topic of mechanism design. He employs algorithmic design and analysis techniques to traditional economics problems to arrive at an algorithmic theory of mechanism design that is more appropriate for computer science settings than the traditional economic theory. One contribution of his work develops approximation and online algorithm techniques for designing mechanisms with good worst case properties. He has also reformulated fair resource allocation as an algorithmic pricing problem. This research lays the foundation for the future of computer science as the focus shifts from single-user algorithms to multi-user and Internet algorithms where algorithm correctness relies fundamentally on economic precepts.

Hartline also has interests in data structures, functional programming languages, and machine learning theory.

Nicole Immorlica (Arriving Fall 2008) studies algorithms and economics. She especially has interests in problems with applications to market design. How can we improve the efficiencies of current markets? Predict the success of particular technologies? Effectively engineer optimal social policies? In particular, her recent work has focused on advertising markets including sponsored search auctions, matching markets such as the National Residency Matching Program, and diffusion of innovations in social networks.

Ming-Yang Kao studies the design, analysis and implementation of algorithms. His work spans a broad range of applications including bioinformatics, computational finance, electronic commerce, and nanotechnology. Kao's most recent research includes work on DNA self-assembly, variants of the traveling salesman problem, and graph labeling problems.

Kao heads the EECS Computing, Algorithms & Applications Division and is the editor-in-chief of Algorithmica.