Algorithms and Theory Group

Department of Computer Science[1], University of Maryland, College Park[2].

Welcome to the Wiki for our group!

Research in Theory of Computation includes three parts.

1. Abstract salient features of a computational task; the outcome of abstraction is usually a mathematical model.
2. Use analytical tools to study various issues within the model.
3. Go back and relate the contributions of studies within the model to the motivating computational task.

The motivation may arise from a specific application, a whole application area, or from more foundational considerations. The former cases lead to designing and analyzing algorithms useful for the understanding of the motivating application. In the latter case, perhaps more similar to traditional areas of Mathematics, practical applicability may sometimes emerge as a by-product.

For students with an interest in the theory of computation, the University of Maryland provides a unique opportunity. The faculty has a very strong reputation in a several theory areas for students who wish to pursue research in these areas. For students with a strong theoretical bent and desire to apply theory to new application areas, the faculty has several forward looking research projects and studies.

Main Research Areas:

• Applied Algorithmics: Joseph Ja'Ja', Mohammad Hajiaghayi, Samir Khuller, David Mount, Mihai Pop, Aravind Srinivasan, Uzi Vishkin
  Applying rigorously developed theory to practical problems arising in, e.g., networks, graphics, image processing, architecture, and social networks and epidemiology. Research at UMD in this area is often undertaken in collaboration with faculty in application areas. A sample of issues covered includes: how to schedule data upload in high-volume Web servers, nearest-neighbor searching, fast interpolation for ray-tracing, scheduling multimedia delivery from replicated sources, and exploiting the massive parallelism in upcoming parallel architectures.
  
  
• Algorithmic Game Theory: Mohammad Hajiaghayi, Aravind Srinivasan,
  Mechanism Design in particular Algorithmic Game Theory, which can be viewed as "incentive-aware algorithm design", has become an increasingly important part of (theoretical) computer science in recent years. Recent results show a strong relation between computer science (esp. networking) and economics (esp. game theory), and techniques from each seem well-poised to help with key problems of the other. Our main goal in this area is to study these connections which produce powerful mechanisms for adaptive and networked environments and several other applied areas, and improve the experience of users of the Web and the Internet. To this end, we do research in several topics such as algorithmic mechanism design; auctions (efficient, revenue-maximizing, sponsored search, etc.); congestion and potential games; cost sharing; existence, computation, and learning of equilibria; game theory in the Internet; network games; price of anarchy; selfish routing, etc.
  
  
• Approximation Algorithms: Samir Khuller, Mohammad Hajiaghayi, Aravind Srinivasan, Uzi Vishkin
  Approximation algorithms is the branch of algorithms dealing with the design of polynomial time algorithms that produce solutions that are close to optimal. This is of special interest for intractable problems for which no polynomial algorithms are known that produce optimal solutions. Techniques used are from a variety of areas: greedy algorithms, linear programming, randomized algorithms, non-linear programming, dynamic programming etc.
  
  
• Bioinformatics and Computational Biology: Carl Kingsford, Mihai Pop
  Bioinformatics and Computational Biology involve the application of algorithmic theory to solving biological problems, in particular those problems arising from the modern shift of biological research towards high-throughput experimental techniques. As an example, determining the DNA sequence of organisms could not be possible without sophisticated algorithms used to assemble together the many small fragments generated by sequencing machines. Computational Biology at University of Maryland is conducted in close collaboration with biologists from the life-science departments and from other institutions.
  
  
• Coding Theory: Alexander Barg
  Coding theory is motivated by the problem of information transmission over noisy communication channels. It has developed into an area of applied mathematics with strong ties to theoretical computer science. Among the areas with links to CS are: list decoding of algebraic codes, local testability and local decodability and proofs of the different versions of the PCP theorem, codes and algorithms on graphs, almost orthogonal codes and weakly biased arrays, universal hash functions, quantum information processing, and others.
  
  
• Complexity Theory: William Gasarch, Jonathan Katz
  Complexity theory is concerned with how complex various functions are to compute. The usual measures of complexity are time and space, though there are others such as communication and descriptive complexity. The most important problem in complexity theory is P=?NP. One topic of research in complexity theory at The University of Maryland is looking at analogs of P=?NP in communication complexity and descriptive complexity theory and seeing if the problem is solvable there, and what insights it may offer for the real problem. This approach is also being used on other open problems in complexity theory.
  
  
• Computational Geometry: Samir Khuller, David Mount
  Computational geometry is the study of algorithms and data structures for problems whose inputs are geometric objects, for example, points, lines, spheres, polygons, and polyhedra. The field has applications to areas such as computer graphics and vision, robotics, computer-aided design, computational statistics, and computational biology. Research on computational geometry at Maryland includes work on a number of areas, including computing closest points and nearest neighbor searching and point location, computing clusters in point sets, point pattern matching, and interpolation.
  
  
• Cryptography: Jonathan Katz, Alexander Barg
  Cryptography began as a rigorous formalization of issues arising in data and computer security (encryption, authentication, etc.), but has since expanded to touch upon many other areas of theoretical computer science (the most striking example being the concept of "zero-knowledge proofs"). Research at UMD explores both the practical and the theoretical aspects of this field. A primary motivation is to understand the efficiency of cryptographic solutions by (1) improving the computational/communication complexity of existing protocols, (2) using new number-theoretic assumptions to speed up current constructions, (3) designing improved algorithms for faster computation, and (4) proving lower bounds on the best possible efficiency that can be achieved.
  
  
• Fixed-Parameter Algorithms: Mohammad Hajiaghayi
  Fixed-parameter algorithms (a.k.a. parameterized complexity) is another approach to cope with hardness of NP-complete problems. In these algorithms, we allow the running time to be exponential, but only with respect to a parameter other than the problem size, while the result must be optimal (the parameter is often small in practice). In particular, parameterized complexity uses a set of techniques such as kernelization, bounded search trees, bounded treewidth of graphs, and extremal combinatorics among others. Though until recently, approximation algorithms and fixed-parameter algorithms have been considered to be two different approaches with different methodology that have very little to do with each other, very recently several connections between the two fields were identified. We are currently investigating these connections along with traditional parameterized algorithms for NP-complete problems.
  
  
• Parallel Algorithms: Clyde Kruskal, Joseph Ja'Ja', Uzi Vishkin
  Thinking algorithmically in parallel provides an interesting ``alien intellectual culture, relative to previous algorithmic theories. Current UMD researchers have had a strong presence in this field for over two decades, as evidenced by the recent recognition of 2 parallel algorithms researchers: Clyde Kruskal and Uzi Vishkin, as Highly Cited Researchers -- Kruskal and Vishkin are 2 of a total of 15 active UMD faculty members to be recognized by ISI Thompson, publishers of the science citation index. The PRAM-On-Chip project at UMD is a direct outgrowth of our theoretical work. The project offers a concrete agenda for challenging the 1946 von-Neumann architecture, through streamlining the massive knowledge base developed by the parallel algorithms community with the roadmap for CMOS VLSI.
  
  
• Pattern Matching: Uzi Vishkin
  Strings of characters (or bits) is an elementary form for representing information. Pattern matching problems on strings have provided a fertile ground for idea-driven algorithmic research.
  
  
• Randomized Algorithms: Mohammad Hajiaghayi, Jonathan Katz, Aravind Srinivasan
  Randomized algorithms are algorithms that make random choices as they proceed, and have had a fundamental impact on many areas of computer science including distributed computing, cryptology, and networking. Research in Maryland covers all aspects of this field, including applications to network design and routing, approximation algorithms, scheduling, and distributed algorithms. On the more theoretical side, we are also interested in studying the limits to which randomization can be useful in computation.

Web Accessibility