{
  "id": "1011.3680",
  "version": "v1",
  "published": "2010-11-16T13:04:40.000Z",
  "updated": "2010-11-16T13:04:40.000Z",
  "title": "The Curse of Dimensionality for Monotone and Convex Functions of Many Variables",
  "authors": [
    "Aicke Hinrichs",
    "Erich Novak",
    "Henryk Woźniakowski"
  ],
  "journal": "J.Aprrox.Theory 163 (2011) 955-965",
  "doi": "10.1016/j.jat.2011.02.009",
  "categories": [
    "math.NA"
  ],
  "abstract": "We study the integration and approximation problems for monotone and convex bounded functions that depend on $d$ variables, where $d$ can be arbitrarily large. We consider the worst case error for algorithms that use finitely many function values. We prove that these problems suffer from the curse of dimensionality. That is, one needs exponentially many (in $d$) function values to achieve an error $\\epsilon$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-11-16T13:04:40.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "convex functions",
      "dimensionality",
      "function values",
      "worst case error",
      "convex bounded functions"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1011.3680H"
    }
  }
}