Arthur Werschulz

Dr. Arthur G. Werschulz is a Professor Emeritus of Computer Science at Fordham University, where he was from 1982 - 2020. 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 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.

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?

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.