The Algorithms and Theory group focuses on classifying and solving complex computational problems that arise in diverse areas of computer science. Their areas of research include approximation algorithms, algorithmic game theory, circuit and communication complexity, cryptography, combinational optimization, pseudo-randomness, and learning theory.
Members of the group often work closely with the Security group and Social Networks groups, and with several faculty members who contribute to both areas, to examine issues such as distributed computing and network algorithms.
The researchers apply mathematical and computational skills to numerous practical problems. For example, work on complexity theory involves determining the computational resources required to solve highly complex algorithms; and combinatorial optimization can be used to model the pricing of stocks in financial markets, movement of goods in transportation networks and vaccine distribution policies.
Team Achievements
- Awarded National Science Foundation grant to design algorithms to more efficiently and reliably identify bugs in software and hardware systems such as cell phones, medical devices, and aviation systems
- Constructed more robust and efficient pseudo-random generators, which are the fundamental building blocks of cryptography and the key to understanding computational complexity
- Generated universal approximation algorithms that enable network optimization in a cost- and time-efficient manner
- Developed widely used ranking and search algorithms for online documents
- Created protocols that enable individual network nodes to cooperate and optimize for global objectives in adversarial environments, under current known conditions as well as future uncertain scenarios
- Developed adaptive divesrification strategies toa chieve highly robust communication including efficient procedures to compute optimal strategies and associated probabilities that adversaries will use specific strategies
- Developed an algorithm for a model explaining the emergence of scale-free networks in natural, technological, and social systems; including cell phones, the World Wide Web, and online communities
- Constructed cryptography schemes to maintain system security even when attackers obtain partial information.
