CSE Distinguished Lecture Seminar with Amihood Amir

Primary tabs

CSE Seminar

By: Amihood Amir

Bar Ilan University and Johns Hopkins University


Title: Hamming Centerstring Problems

Abstract: The Smallest Enclosing Ball problem is a classical computational geometry problem. Its input is a set of points in space and the output is the center and radius of the smallest ball that bounds all input points.   If the space is length-n strings over alphabet Σ and the distance function is the Hamming distance, the problem becomes the center-string or consensus string problem.  We will survey some of the results of the consensus string problem and consider a generalization: Motivated by clustering strings, one needs to consider a partition into a number of sets, each with a distinct center-string. We define two natural versions of the consensus problem for c center-strings. We analyze the hardness and fixed parameter tractability of these problems and provide approximation algorithms.

Bio: Amihood Amir received his Ph.D. in 1983 at Bar-Ilan University. He did his post-doc at MIT, and was on the faculty at Tufts, University of Maryland at College Park, and Georgia Tech, before joining Bar-Ilan University in 1994. Today he is a professor of Computer Science at Bar-Ilan University and a Research Professor at Johns Hopkins University. Amir had been head of the Bar-Ilan Responsa Project, Chairman of the Department of Computer Science and dean of the College of Exact Sciences at Bar-Ilan University.  Amihood Amir is the author of over a hundred research papers, and recipient of grants from the NSF, ISF, BSF, the Israel Ministry of Science, and the Israel Ministry of Industry and Commerce. In addition, he was a co-PI on bi-national grants with the UK, Italy, France and Finland. Amir serves on the editorial board of Information and Computation, and served on the program committee of dozens of major Computer Science conferences.  Amir has won a departmental teaching excellence award at the University of Maryland, and research awards at UMCP and Georgia Tech. He has chaired the Computer Science Advisory Committee of the Israel Ministry of Education, and was a panel member on various panels of the NSF, Israel Ministry of Science, and the Israel Institute for Higher Education.  Amihood Amir's Ph.D. thesis was in logic of programs, particularly temporal logics. He later did some work in Complexity theory - sub-recursive classes of functions and the concept of "cheatability" in hard sets. Since the late 1980's Amir's research has been in Algorithms design and analysis, in particular Pattern Matching Algorithms. In the later area he has been instrumental in developing the multidimensional pattern matching area, compressed matching, and, recently, asynchronous matching. In this context he has also done work in algorithms for Computational Biology. Amir has also worked in the past in Scheduling algorithms, VLSI algorithms, and Data Mining algorithms.


  • Workflow Status: Published
  • Created By: Nina Norris
  • Created: 09/03/2014
  • Modified By: Fletcher Moore
  • Modified: 04/13/2017


No keywords were submitted.