Fordham University            The Jesuit University of New York

Dr. Arthur Werschulz
Associate Chair for Undergraduate Studies (LC)

Department of Computer & Information Sciences
815-D Lowenstein
113 W60th St., New York NY 10023
Email: agw(at)
Phone: 212-636-6325

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 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?

Selected Publications

  • 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.


Site  | Directories
Submit Search Request