Algorithms and Theory Group @ University of Maryland

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.

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', 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.

• Approximation Algorithms: Samir Khuller, 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: 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 UMD College of Life Sciences 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.

• 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: 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.