SEMINAR

DEPARTMENT OF COMPUTER ENGINEERING

ABSTRACT

Some Complexity Issuues in Parallel Computing

Prof.Dr. Oscar Ibarra

Department of Computer Science

University of California, Santa Barbara

We give an overview of the computational complexity of linear and mesh-connected cellular arrays with respect to well known models of sequential and parallel computation. We discuss one-way communication versus two-way communication, serial input versus parallel input, and space-efficient simulations. In particular, we look at the parallel complexity of cellular arrays in terms of the PRAM theory and its implications, e.g., to the parallel complexity of recurrence equations and loops. We also point out some important and fundamental open problems that remain unresolved.

Next, we investigate the solvability of some reachability and safety problems concerning machines operating in parallel and cite some possible applications. Finally, we briefly discuss the complexity of the ``commutativity analysis''technique that is used in the areas of parallel computing and parallelizing compilers.

The Seminar will be on October 6, 2000, at 14:40

in EA331

OSCAR H. IBARRA

Oscar H. Ibarra received the B.S. degree in Electrical Engineering from the University of the Philippines in 1962 and the M.S. and Ph.D. degrees, also in Electrical Engineering, from the University of California, Berkeley, in 1965 and 1967, respectively. He is currently a Professor of Computer Science at the University of California, Santa Barbara, where he served as Department Chair from 1997-1999. He was previously with the faculties of UC Berkeley (1967-1969) and the University of Minnesota (1969-1990).

Dr. Ibarra's research interests include the design and analysis of algorithms, the theory of computation, computational complexity, and parallel computing. He is a Fellow of the Association for Computing Machinery (ACM), a Fellow of the Institute of Electrical and Electronics Engineers (IEEE), a Fellow of the

American Association for the Advancement of Science (AAAS), and a Fellow of he Minnesota Supercomputer Institute. He is a recipient of a John Simon

Guggenheim Fellowship.

Dr. Ibarra is the Editor-in-Chief of the International Journal of Foundations of Computer Science. He is on the editorial boards of Theoretical Computer Science, Journal of Parallel and Distributed Computing, and Journal of Computing and Information. He has also served on the editorial boards of the IEEE Transactions on Computers, IEEE Transactions on Parallel and Distributed Systems, and Journal of VLSI Signal Processing. He is on the advisory board of the IEEE Technical Committee on Parallel Processing.