Dr. Arthur Werschulz Professor Department of Computer & Information Sciences 815-D Lowenstein 113 W60th St., New York NY 10023 Email: agw(at)cis.fordham.edu Phone: 212-636-6325 Dr. Werschulz's Homepage

Bio

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.

He has been on the editorial board of the Journal of Complexity since 1996. In addition, he maintains tha 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.

Research

Information-based complexity (IBC) studies the computational complexity of problems whose information is partial and/or contaminated, as well as priced. By using arguments at the information level, we can find lower bounds on the error and cost of algorithms for solving that problem.

Dr. Werschulz has been doing research in IBC for over twenty years. His main area of concentration has been the complexity of linear partial differential equations (mainly elliptic problems, but with some work in non-elliptic problems) and linear integral equations (Fredholm problems of the first and second kind). Much of his work on elliptic PDE and on Fredholm problems of the second kind has dealt with determining conditions that are necessary and sufficient for finite element methods to be optimal-complexity methods. His work on Fredholm problems of the first kind has dealt with both the worst case and average case settings.

His current emphasis is on the following areas.

1. Vanquishing the curse of dimension. The worst case complexity of many problems defined over standard spaces is exponential in the dimension. This means that no matter how clever we are, the problem is intractable if we insist on a worst case assurance and standard input spaces. If we want to render these problems tractable, we must either use a different setting to measure cost and error (such as the average case or randomized settings), or we must use non-standard input spaces. Moreover, new models of computation, such as the quantum model, may hold promise.
2. Problems with hidden nonlinearities. Many mathematical problems can be expressed as the solution of a linear operator equation. Complexity theory for linear problems is highly well-developed. However, such problems typically have hidden nonlinearities (typically arising through the coefficients of the linear operator or the domain over which the problem is to be solved). What can we say about the complexity of such problems when these hidden nonlinearities are taken into account?

Selected Publications

• Arthur G. Werschulz (2007). "Complexity and tractability of the heat equation", Journal of Complexity, 23:553-559

• Arthur G. Werschulz and Henryk Wozniakowski (2007). "Tractability of quasilinear problems. I: General Results", Journal of Approximation Theory, 145:266-285

• Arthur G. Werschulz (2007). "Tractability of quasilinear problems. II: Second-order elliptic problems", Mathematics of Computation, 76:745-746

• Arthur G. Werschulz and Henryk Wozniakowski (2004). "Surface approximation is sometimes easier than surface integration", Constructive Approximation, 20(2):267-302

• Arthur G. Werschulz (2003). "Where does smoothness count the most for Fredholm equations of the second kind with noisy information?", Journal of Complexity, 19(4):758-798

• Arthur G. Werschulz (2002). "An overview of information-based complexity", 2002 International Conference on Complex Systems, Nashua, NH.  [txt]

• Arthur G. Werschulz and Henryk Wozniakowski (2002). "What is the complexity of volume calculation?", Journal of Complexity, 18(2):660-678

• Arthur G. Werschulz and Henryk Wozniakowski (2001). "What is the complexity of surface integration?", Journal of Complexity, 17(2):442-46

• Joseph F. Traub and Arthur G. Werschulz (1998). "Complexity and Information". Cambridge University Press.