CIS Department Talk – May 12, 2009

The Department of Computer and Information Science in conjunction with The BMH Informatics Research Group Present

Speaker:	Oscar H. Ibarra, Department of Computer Science, University of California
Topic:	Theory of Computation and Computational Complexity: An Overview
Date:	May 12, 2009, 5:00pm
Place:	JMH room 112

Theory of computation and complexity is a formalization of our understanding of computation (i.e., the notion of an "algorithm"). It is a field of study which investigates the existence or non-existence of algorithms for computational problems. It also aims to develop techniques for designing efficient algorithms as well as to explain why some problems are inherently difficult to solve in terms of their time and/or space requirements. We present a brief overview of the field.

Bio: Oscar H. Ibarra received the B.S. degree in Electrical Engineering from the University of the Philippines and the M.S. and Ph.D. degrees, also in Electrical Engineering, from the University of California, Berkeley. He is a Professor and past Chair of the Department of Computer Science at the University of California, Santa Barbara. Previously, he was on the faculties of UC Berkeley (1967-1969) and the University of Minnesota (1969-1990). His research interests include the design and analysis of algorithms, theory of computation, computational complexity, parallel computing, formal verification, molecular computing, membrane computing.

Ibarra was awarded a John Simon Guggenheim Memorial Foundation Fellowship in 1984. He is a Fellow of the Association for Computing Machinery (ACM), the Institute of Electrical and electronics Engineers (IEEE), and the American Association for the Advancement of Science (AAAS). In 2001, he received the IEEE Computer Society's Harry H. Goode Memorial Award.

Ibarra is the Editor-in-Chief of the International Journal of Foundations of Computer Science. He is an Editor of Theoretical Computer Science, the Journal of Parallel and Distributed Computing, Grammars: A Journal of Mathematical Research on Formal and Natural Languages, and Mathematics Applied in Science and Technology. He has also served on the editorial boards of the IEEE Transactions on Computers, the IEEE Transactions on Parallel and Distributed Systems, and the Journal of VLSI Signal Processing. He is on the advisory committee of the IEEE Technical Committee on Parallel Processing and is a member of the IFIP Working Group on Cellular Automata.

For more information, contact Ms. Danielle Aprea (718) 817-4480