Does Increased Regularity Lower Complexity?
Intuitively, the more regular a problem, the easier it should be to solve. Examples drawn from ordinary and partial differential equations, as well as from approximation, support the intuition. Traub and Wozniakowski conjectured that this is always the case. In this paper, we study linear problems. We prove a weak form of the conjecture, and show that this weak form cannot be strengthened. To do this, we consider what happens to the optimal error when regularity is increased. If regularity is measured by a Sobolev norm, increasing the regularity improves the optimal error, which allows us to establish the conjecture in the normed case. On the other hand, if regularity is measured by a Sobolev semi-norm, it is no longer true that increasing the regularity improves the optimal error. However, a "shifted" version of this statement holds, which enables us to establish the conjecture in the semi-normed case.
- cucs-038-82.pdf application/pdf 1.73 MB Download File
More About This Work
- Academic Units
- Computer Science
- Department of Computer Science, Columbia University
- Columbia University Computer Science Technical Reports, CUCS-038-82
- Published Here
- October 26, 2011