Algorithms and Theory

The dominant research theme in our group is algorithm design, studied from several diverse viewpoints: combinatorial optimization; approximation, online, randomized and parallel algorithms; graph algorithms; and algorithmic game theory. A second theme is computational complexity theory, with an emphasis on studying new complexity classes, such as those used for establishing intractability of economic and game-theoretic solution concepts. Other areas of theory studied include computational geometry, data structures, geometric graph theory, quantum computing, spectral graph theory, theory of deep learning, cryptography, and online and matching-based market design.