Research

Research Groups > Algorithms and Theory

Javed Aslam
Javed
Aslam		 Albert-László Barabási
Albert-László
Barabási		 Agnes Chan
Agnes
Chan		 Guevara Noubir
Guevara
Noubir
Rajmohan Rajaraman
Rajmohan
Rajaraman		 Ravi Sundaram
Ravi
Sundaram		 Emanuele Viola
Emanuele
Viola

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 network security group and social networks groups, and with several faculty members contributing 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; combinatorial optimization can be used to model diverse real-world problems such as pricing of stocks in financial markets to movement of goods in transportation networks to policies for distributing vacines.

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, the fundamental building blocks of cryptography and the key to understanding computational complexity;
  • Constructed new pseudo-random generators that are more robust and efficient than previous constructions.  Pseudo-random generators are fundamental building blocks on cryptography, essential for Monte Carlo simulations, and key to our understanding of 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 strategies of adaptive diversification to achieve highly robust communication, including efficient procedures to compute optimal strategies and to compute 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.