CIS Department Talk – December 10, 2008
The Department of Computer and Information Science Present
|Speaker:||Dr. Arthur G. Werschulz
|Topic:|| An Overview of Information-Based Complexity
|Date:||December 10, 2008, 2:30PM-4:00PM|
|Place:||LL Room 1019, FMH 543 |
Computational complexity theory deals with determining the minimal amount of resources needed to solve computational problems, as well as finding optimal algorithms for their solution. Information-based complexity (IBC) is that branch of complexity theory studying problems whose information is partial, possibly noisy, and priced. (Such problems occur in numerous application areas, such as science, engineering, economics, and mathematical finance.) Since we can only know certain information about a problem instance, rather than the full problem instance itself, there is a powerful information-based adversary principle that allows us to systematically find lower bounds on the problem complexity. We illustrate the basic ideas of IBC by integration, a standard model problem.
We then discuss multivariate problems of high dimension; problems involving hundreds (or even thousands) of variables are not uncommon. The standard formulations of such problems suffer from the curse of dimensionality: their inherent complexity grows exponentially with the dimension. Since non-polynomial growth generally means that a problem is intractable, we would like to find different formulations of these problems whose complexity is polynomial. We will report on various attempts to vanquish the curse of dimensionality.
Dr. Arthur G. Werschulz is a Professor of Computer Science at Fordham University, where he has been since 1982. He also has had a research appointment in the Computer Science Department of Columbia University since 1982, where he is currently an Adjunct Senior Research Scientist. Prior to this, he was on the faculty of the University of Maryland Baltimore County from 1976 to 1982. His undergraduate (B.S., Mathematics) and graduate (M.S. and Ph.D., Mathematics) degrees were earned at Carnegie-Mellon University.
He has been on the editorial board of the Journal of Complexity since 1996. In addition, he maintains the Information-Based Complexity (IBC) Website, which includes a searchable database of the IBC literature.
Dr. Werschulz's research in IBC has received international recognition. He has been frequently invited to speak at international conferences and workshops. He has been the recipient of two prestigious awards:
* The 1999 Best Paper Award of the Journal of Complexity, and
* The 2003 Prize for Achievement in Information-Based Complexity.
For more information, contact Ms. Danielle Aprea (718) 817-4480