Dr. Arthur Werschulz
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 and Henryk Wozniakowski (2012). "Tractability of the Fredholm problem of the second kind", Journal of Integral Equations and Applications, 24(3):413-461
Damian M. Lyons, Christina Papadakis-Kanaris, Gary M. Weiss, Arthur G. Werschulz (2012). "Fundamentals of Discrete Structures". Pearson Learning Solutions.
Arthur G. Werschulz and Henryk Wozniakowski (2009). "Tractability of the Helmholtz equation with non-homogeneous Neumann boundary conditions: Relation to L2-approximation", Journal of Complexity, 25(6):568-600
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 and Henryk Wozniakowski (2009). "Tractability of multivariate approximation over a weighted unanchored Sobolev space: Smoothness sometimes hurts", Constructive Approximation, 30:395-421
Joseph F. Traub and Arthur G. Werschulz (1998). "Complexity and Information". Cambridge University Press.