Dr. Arthur Werschulz
Associate Chair for Undergraduate Studies (LC)
Department of Computer & Information Sciences
113 W60th St., New York NY 10023
Dr. Werschulz's Homepage
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 the
(IBC) Website, which includes a searchable database of the IBC
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
- the 1999 Best Paper Award of the Journal of Complexity, and
- the 2003 Prize for Achievement in Information-Based Complexity.
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.
- 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.
- 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?
Arthur G. Werschulz (2009). "The complexity of Fredholm equations of the second kind: noisy information about everything", Journal of Integral Equations and Applications, 21(1):553-559
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.