Algorithms and Complexity for Functions on General Domains

Erich Novak

REVIEW 2 major objections 4 minor 49 references

Algorithms and Complexity for Functions on General Domains

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For Lipschitz approximation, numerical integration, and Sobolev L2-approximation on arbitrary bounded domains, the optimal worst-case error depends on the domain only through its volume, and explicit bounds hold for every n.

desk verdict Solid survey with a few new uniform bounds; central volume-only asymptotics hold, but the proof of (7) has a packing gap that needs fixing. read the letter →

arxiv 1908.05943 v2 pith:GY5HOUZS submitted 2019-08-16 math.NA cs.CCcs.NA

Erich Novak This is my paper · ORCID

classification math.NAcs.CCcs.NA MSC 65Y2041A4665D30

keywords information-basedcomplexityoptimalrecoverycoveringnumbersasymptoticconstantLipschitzfunctionsSobolevembeddingscurseofdimensionalityJordanmeasurabledomains

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks whether the optimal worst-case error for approximating or integrating functions can be understood for arbitrary bounded domains, not just cubes, tori, or spheres. It establishes that for Lipschitz functions in the uniform norm, for numerical integration of the same class, and for $L_2$-approximation of Sobolev functions with arbitrary linear information, the asymptotic constant of the optimal error depends on the domain only through its $d$-dimensional volume—provided the domain is Jordan measurable with an interior point, meaning its boundary carries no volume. Shape and boundary values drop out of the leading term, leaving a constant fixed by the volume and the norm's unit ball. The paper also proves explicit bounds valid for every $n$ and every normalized domain, with uniform lower bounds that are sharp, and shows these finite-$n$ bounds sit close to the asymptotic constants. The upshot is that domain geometry is asymptotically irrelevant for several benchmark problems and that dimension-dependent lower bounds such as the curse of dimensionality can be proven for general domains.

What carries the argument

The carrying object is the covering radius of the domain with respect to the norm's unit ball. Proposition 1 identifies the optimal $L_\infty$ error with the modulus of continuity of the covering radius, $e_n = \omega(c_n)$, so covering-number asymptotics translate directly into error asymptotics; classical results on covering $\mathbb{R}^d$, together with the bound $1 \leq \Theta_B \leq d \log d + d \log \log d + 5d$, supply the volume-normalized constant. For integration, a comparison of the integration radius with the $L_\infty$ radius of the same $n$-point information mapping contributes the factor $d/(d+1)$. For Sobolev spaces with arbitrary linear information, the machinery switches to eigenvalue asymptotics of the Dirichlet and Neumann Laplacians: the approximation numbers of the Sobolev embedding are governed by the same Weyl term that makes eigenvalue counts depend on volume alone, and eigenvalue bounds make the finite-$n$ estimates explicit. The uniform lower bounds throughout come from a volume estimate: $n$ balls of radius $\varepsilon$ used to cover a domain have total volume at most $n$ times the volume of one ball, and a domain consisting of $n$ disjoint equal balls attains equality.

What would settle it

For a fixed volume, compare the optimal $L_\infty$ error at large $n$ on two bounded Jordan measurable domains of equal volume whose boundaries have very different roughness—for instance, a Euclidean ball and a domain of the same volume with a highly oscillatory boundary of measure zero. If the ratio of their errors does not tend to 1 as $n$ grows, Theorem 1's volume-only constant is false. A sharper numerical check: compute the finite-$n$ error on a domain consisting of $n+1$ equal balls versus a single connected domain of the same total volume; the paper's uniform lower bound is attained by the disjoint balls, so a connected domain with strictly smaller error at the same $n$ would reveal finite-$n$ shape dependence, though not a contradiction of the asymptotic statement.

Watch

Extended reading notes

Core claim

The central discovery is a set of theorems with a common message. Theorem 1 states that for a bounded Jordan measurable set $D_d \subset \mathbb{R}^d$ with an interior point, the optimal $L_\infty$ error for functions with $|f(x)-f(y)| \leq \|x-y\|_B$ satisfies $e_n \approx \Theta_B^{1/d} (\lambda_d(D_d)/\lambda_d(B))^{1/d} n^{-1/d}$, where $\Theta_B$ is the covering constant of $\mathbb{R}^d$ with respect to the unit ball $B$ and $1 \leq \Theta_B \leq d \log d + d \log \log d + 5d$. It also states the uniform lower bound $\inf_{D_d} e_n \lambda_d(D_d)^{-1/d} = \lambda_d(B)^{-1/d} n^{-1/d}$, sharp for a domain made of $n$ equal balls. Theorem 2 gives the integration analogue, with constant $\xi_B$ between $d/(d+1)$ and $\frac{d}{d+1} \Theta_B^{1/d}$ and a sharp uniform lower bound of the same volume-only type. Theorem 4 extends volume-only asymptotics to $L_2$-approximation in Sobolev spaces: the limit of $e_n n^{r/d} \lambda(D_d)^{-r/d}$ exists, equals $C_{r,d}$, and is the same for $H^r(D_d)$ and the zero-boundary subspace $H^r_0(D_d)$. The paper adds explicit finite-$n$ bounds that are only slightly weaker than the conjectured uniform versions.

Load-bearing premise

The volume-only constants and the explicit uniform bounds rest on assuming the domain is Jordan measurable with an interior point, so that the volume of the inner strip near the boundary is negligible; on domains with fractal or otherwise badly behaved boundaries, the asymptotic constants may depend on shape and the uniform bounds can fail.

Editorial extensions

If this is right

For Lipschitz and Hölder classes on any bounded Jordan measurable domain of volume $V$, asymptotically optimal sampling points need no detailed knowledge of shape: the leading error is set by $V^{1/d} n^{-1/d}$, and shape or boundary values affect only lower-order terms.
When the volume is normalized to that of the unit ball, optimal sample points beat a regular grid by a factor of about 2 in the leading constant for the Euclidean norm; equivalently, reaching a target error with a grid costs more than $2^d$ times as many function evaluations as optimal points.
The explicit uniform lower bounds imply the curse of dimension on general normalized domains: for Lipschitz classes scaled by $d^{-1/p}$, reaching error $\varepsilon$ costs at least $(c_p/\varepsilon)^d$ function evaluations, whether for approximation or integration.
For Sobolev $H^r$ $L_2$-approximation with arbitrary linear information, the asymptotic constant is independent of both domain shape and Dirichlet/Neumann boundary conditions, so spectral asymptotics transfer directly to information-based complexity.
The finite-$n$ bounds, which for the boundary-vanishing $L_\infty$ case are within a factor 2 of the asymptotic constant, make these estimates usable in the small-$n$ regime where asymptotic formulas alone do not apply.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial: If volume-only asymptotics hold for all Jordan measurable domains, the extremal domain for the lower bounds—a disjoint union of $n$ equal balls—can serve as a worst-case test set: an algorithm that performs well there should perform at least as well on any domain of the same volume, at least in the leading term.
Editorial: The same reasoning suggests a testable extension to domains that are not Jordan measurable: if a boundary has positive $d$-dimensional measure, or its thin-neighborhood volume does not vanish as the neighborhood width shrinks, the inner-strip volume is not negligible and error constants should acquire shape dependence; measuring this would isolate exactly where the Jordan assumption bit
Editorial: Because $\Theta_B^{1/d}$ tends to 1 as $d$ grows, the volume-only constant is nearly norm-independent in high dimension; one could probe whether the explicit finite-$n$ bounds also converge to a common limit, making the small-$n$ behavior more universal than the asymptotics alone suggest.
Editorial: The open conjecture for $C^2$ classes could be tested numerically on non-cube domains: if a domain with a long thin tentacle admits a fooling function with smaller error than the conjectured $n^{-2/d}$ bound, the volume-only principle would fail for that class; if not, the bound likely holds for all bounded open sets.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

This is a solid survey of what is known about asymptotic constants and explicit uniform bounds for sampling-based approximation and integration on general domains. The central claim—that for Lipschitz functions and for Hilbert Sobolev embeddings the asymptotic constant depends on the domain only through its volume—is credible and backed by precise citations. The genuinely new items are the explicit uniform lower bounds (6) and (11), the near-optimal uniform upper bound (7), and the bound on ξ_B. They are elementary, short, and essentially correct.

The paper earns credit for being candid about what is new versus what is collected from Hlawka, Kolmogorov–Tikhomirov, Sukharev, Chernaya, and Mieth. Open problems are labeled as such. That honesty is appreciated.

The soft spot is the proof of the uniform upper bound (7) in Remark 1. The argument assumes that for a given n you can take ε with n λ(B_ε) = λ(D_d) and then find n disjoint ε-balls inside D_d forming a complete packing. That does not work for every domain and every n: a long thin rectangle with ε larger than its width contains no ball of radius ε at all. So the proof as written is invalid for those cases. The bound itself is likely true—a grid construction gives the same rate with a slightly worse constant—but the proof needs a different argument. This does not affect Theorem 1 or the asymptotic results, which rest on the classical covering asymptotics and are fine.

The reliance on covering-number asymptotics for bounded Jordan measurable sets is appropriate; the interior-point condition handles the boundary layer. I don't see a hidden assumption there.

Who should read this? People in information-based complexity who want a compact, reliable statement of volume-only constants and the state of the art for explicit bounds. It's not a landmark, but it's useful and checkable.

Recommendation: send it to peer review, and ask the author to fix the packing argument in (7). Everything else is in good shape.

Referee Report

2 major / 4 minor

Summary. The paper studies worst-case errors and complexity for approximation and integration of Lipschitz (and more general) functions on bounded subsets D_d of R^d using n function values. Its central claim is that for L-infinity approximation of Lipschitz functions, the optimal error is asymptotically Θ_B^{1/d} (λ_d(D_d)/λ_d(B))^{1/d} n^{-1/d} for every bounded Jordan measurable set with an interior point, so the asymptotic constant depends on the domain only through its volume; Theorem 1 states this and adds an explicit uniform lower bound (6). Theorem 2 states an analogous asymptotic formula for integration with constant ξ_B, together with a uniform lower bound (11) and an upper bound on ξ_B. The paper also surveys higher-smoothness results and Sobolev approximations under general linear information, mainly following Mieth, and lists open problems. The advertised new contributions are the explicit uniform bounds (6), (7), and (11) and the comparison constant for ξ_B; the asymptotic formulas are attributed to Hlawka, Kolmogorov-Tikhomirov, Sukharev, Chernaya, Gruber, and Mieth.

Significance. If the uniform-bound proofs are made fully rigorous, this is a useful contribution: it gives elementary volume-based lower bounds valid for all n and all bounded Jordan measurable domains, records the volume-only dependence of asymptotic constants, and collects recent results in a unified framework. The lower-bound arguments for (6) and the lower half of (11) are clean and correct, and the explicit bounds are relevant for tractability and for practical finite-n error estimates. The main asymptotic theorems are independently established and are not in question. However, two advertised upper-bound claims rest on proofs that are incomplete or incorrect, so the paper needs revision before the new results can be relied upon.

major comments (2)

[Remark 1, proof of (7)] The proof of the uniform upper bound (7) assumes that for arbitrary n one can choose ε and points x_1,...,x_n such that n disjoint balls B_ε(x_i) form a complete packing of D_d and n·λ_d(B_ε) ≤ λ_d(D_d). The volume constraint does not by itself guarantee the existence of such a packing with exactly n balls: for a long thin rectangle, the value ε=(λ_d(D_d)/(nλ_d(B)))^{1/d} can exceed the width of the rectangle, so no n disjoint balls of radius ε exist. A maximal packing may have fewer than n balls, and adding arbitrary points destroys the radius bound. The inequality (7) may well be true by a different grid or volume argument, but the present proof is incomplete and should be repaired.
[Theorem 2, proof of upper bound on xi_B] The displayed inequality r(N_n, INT) ≤ (d/(d+1)) r(N_n, APP∞) for a fixed information mapping is false for general bounded Jordan measurable domains. For a counterexample, take B as the ℓ∞-unit ball in R^2, α>1, and D_α={0<x<1, 0<y<x^α}; choose the single sample point x_1=(δ, δ^α/2) with δ>0 small. The function ρ(x)=‖x−x_1‖∞ is admissible for F_B(D_α), vanishes at x_1, and satisfies sup ρ → 1 while (∫_{D_α} ρ dλ)/λ(D_α) → 1 as δ→0 and α→∞. Thus the ratio exceeds d/(d+1)=2/3 for large α, contradicting the claimed inequality. Since the upper bound on ξ_B is advertised as a new contribution and is used in Theorem 2, the proof must be replaced or the claim qualified to a class of domains for which the inequality holds.

minor comments (4)

[Abstract and Theorems 1–2] The abstract advertises 'bounded Lipschitz domains,' while Theorems 1 and 2 assume bounded Jordan measurable sets with an interior point; the scope of the results should be stated consistently in the introduction and abstract.
[Theorem 2, proof of the lower bound (11)] The phrase 'Similarly' skips the volume-level-set argument needed to obtain the constant d/(d+1) in the lower bound for arbitrary point sets; spelling out the integration of the distance function over level sets would make the proof self-contained.
[Remark 4] The displayed formula has mismatched parentheses: it reads 'en(F 2(Dd)), APP∞, Λ std)' and should read e_n(F_2(D_d), APP∞, Λ^std) or similar.
[Theorem 1 proof] The paper states that the asymptotic formula (5) follows from Hlawka and Kolmogorov-Tikhomirov; since those classical results are often formulated for convex or more regular sets, a precise statement of the covering-number theorem used, including its validity for arbitrary bounded Jordan measurable sets with interior point, would strengthen the exposition.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central volume-only asymptotic constants are assembled from independent prior theorems and direct volume estimates, not from fitted or self-referential inputs.

full rationale

Theorem 1's asymptotic formula (5) is explicitly presented as a summary of independent results: Hlawka and Kolmogorov-Tikhomirov for covering-number asymptotics, Sukharev for the radius-of-information identity, and Rogers for the covering constant bound. Proposition 1 is attributed to Sukharev, with the author's book cited only as an additional reference. The uniform lower bound (6) is derived by a self-contained volume argument: n balls of radius epsilon have total volume at most n·lambda(B)epsilon^d, so if n lambda(B)epsilon^d is smaller than lambda(D_d), no n-point sample can achieve smaller error; sharpness is exhibited by a disjoint union of n balls, which is a construction, not an assumption of the result. Theorem 2 follows the same pattern: the asymptotic formula (10) is taken from Chernaya/Gruber, while the new uniform lower bound (11) is again a direct volume estimate, and equality is shown by disjoint balls. Theorem 4 is attributed to Mieth and ultimately to Weyl, Birman-Solomjak, Kroger, and Li-Yau; it is imported as an external result, not derived from the paper's own conclusions. The author-overlapping citations (Novak's books and joint papers) are used for background, curse-of-dimensionality remarks, or previously established lower bounds, and none of them supplies the load-bearing step that makes the asymptotic constant volume-only. There are no fitted parameters renamed as predictions, no central quantity defined in terms of the claimed conclusion, and no uniqueness claim imported from the authors' own prior work to forbid alternatives. The known weakness in the proof of the uniform upper bound (7) concerns the existence of a complete packing of exactly n disjoint epsilon-balls in an arbitrary domain; that is a proof-technical correctness issue, not a circularity. Therefore the paper's derivation chain is self-contained against external benchmarks and no circular step is present.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters or invented entities. The constants Theta_B and xi_B are defined from covering theory and known asymptotics, not fitted to data. The paper relies on standard results in covering theory, spectral asymptotics, and the extension property for Sobolev spaces, all cited in the references.

assumptions (6)

standard math Covering-number asymptotics for bounded Jordan measurable sets (from Hlawka, Kolmogorov-Tikhomirov)
Used to obtain the asymptotic constant in Theorem 1 and Example 1; cited as [19], [20].
standard math Volume estimates for metric balls and packing (simple geometric bounds)
Used in the proofs of the uniform lower bound (6), the upper bound (7), and the integration bound (11).
domain assumption D_d is a bounded Jordan measurable set with an interior point
Invoked throughout Section 2 to guarantee lambda_d(D_epsilon) tends to lambda_d(D_d) and to apply covering-number asymptotics.
domain assumption For H^r(D_d), the domain has the extension property (e.g., bounded Lipschitz domain)
Stated in Section 4 before Theorem 4; needed for Sobolev extension and spectral asymptotics.
standard math Weyl's law for Dirichlet and Neumann Laplacian eigenvalue asymptotics
Used via Birman-Solomjak, Tulovsky, and Mieth to derive the asymptotic constant in Theorem 4; cited as [48], [3], [43], [27].
standard math Inequality r(N_n, INT) <= d/(d+1) r(N_n, APP_infinity) for Lipschitz function classes
Used in the proof of the upper bound on xi_B in Theorem 2; attributed to known arguments (Chernaya, Gruber).

how reviews work

0 comments

Cite this review

Pith. "Pith review of Algorithms and Complexity for Functions on General Domains." pith.science (2026). https://pith.science/paper/GY5HOUZS

@misc{pith2026190805943,
  author       = {Pith},
  title        = {Pith review of: Algorithms and Complexity for Functions on General Domains},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GY5HOUZS}},
  note         = {Machine review of arXiv:1908.05943}
}

abstract

Error bounds and complexity bounds in numerical analysis and information-based complexity are often proved for functions that are defined on very simple domains, such as a cube, a torus, or a sphere. We study optimal error bounds for the approximation or integration of functions defined on $D_d \subset R^d$ and only assume that $D_d$ is a bounded Lipschitz domain. Some results are even more general. We study three different concepts to measure the complexity: order of convergence, asymptotic constant, and explicit uniform bounds, i.e., bounds that hold for all $n$ (number of pieces of information) and all (normalized) domains. It is known for many problems that the order of convergence of optimal algorithms does not depend on the domain $D_d \subset R^d$. We present examples for which the following statements are true: 1) Also the asymptotic constant does not depend on the shape of $D_d$ or the imposed boundary values, it only depends on the volume of the domain. 2) There are explicit and uniform lower (or upper, respectively) bounds for the error that are only slightly smaller (or larger, respectively) than the asymptotic error bound.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

49 extracted references · 49 canonical work pages

[1]

V. F. Babenko, S. V. Borodachov and D. S. Skorokhodov, Optim al recovery of isotropic classes of twice-diﬀerentiable multivariate functions, J. Com- plexity 26, 591–607, 2010. [11]

work page 2010
[2]

Barthelmann, E

V. Barthelmann, E. Novak and K. Ritter, High dimensional polynom ial interpolation on sparse grids, Adv. Comput. Math. 12, 273–288, 2000. [14]

work page 2000
[3]

non-smooth

M. S. Birman and M. Z. Solomjak, The principal term of the spectr al asymp- totics for “non-smooth” elliptic problems, Functional Anal. Appl. 4, 265– 275, 1970. [12, 13]

work page 1970
[4]

M. S. Birman and M. Z. Solomjak, Asymptotic behavior of the spec trum of diﬀerential equations, J. Soviet Math. 12, 247–283, 1979. [12]

work page 1979
[5]

M. S. Birman and M. Z. Solomjak, Quantitative analysis in Sobolev imb ed- ding theorems and applications to spectral theory, AMS Translatio ns Series 2, 114. AMS 1980. [12]

work page 1980
[6]

E. V. Chernaya, On the optimization of weighted cubature formu lae on certain classes of continuous functions, East J. Approx. 1, 47–60, 1995. [8]

work page 1995
[7]

Cobos, T

F. Cobos, T. K¨ uhn and W. Sickel, Optimal approximation of multiva riate periodic Sobolev functions in the sup-norm, J. Functional Analysis 270, 4196–4212, 2016. [3] 14

work page 2016
[8]

Dahlke, E

S. Dahlke, E. Novak and W. Sickel, Optimal approximation of elliptic p rob- lems by linear and nonlinear mappings I. J. Complexity 22, 29–49, 2006. [2]

work page 2006

Show all 49 references

[9]

Fejes T´ oth, Packing and covering, in: Handbook of Discrete and Com- putational Geometry, J

G. Fejes T´ oth, Packing and covering, in: Handbook of Discrete and Com- putational Geometry, J. E. Goodman, J. O’Rourke, C.D. T´ oth (ed s.), 3rd edition, CRC Press, pp. 27–66, 2018. [7]

2018
[10]

P. M. Gruber, Optimum quantization and its applications, Adv. Ma th. 186, 456–497, 2004. [8]

2004
[11]

Heinrich, Randomized approximation of Sobolev embeddings II , J

S. Heinrich, Randomized approximation of Sobolev embeddings II , J. Com- plexity , 25, 455–472, 2009. [2]

2009
[12]

Heinrich, Randomized approximation of Sobolev embeddings II I, J

S. Heinrich, Randomized approximation of Sobolev embeddings II I, J. Com- plexity 25, 473–507, 2009. [2]

2009
[13]

Heinrich, On the complexity of computing the Lq norm, J

S. Heinrich, On the complexity of computing the Lq norm, J. Complexity , 49, 1–26, 2018. [2]

2018
[14]

Hinrichs, E

A. Hinrichs, E. Novak and M. Ullrich, On weak tractability of the Cle nshaw- Curtis Smolyak algorithm, J. Approx. Th. 183, 31–44, 2014. [14]

2014
[15]

Hinrichs, E

A. Hinrichs, E. Novak, M. Ullrich and H. Wo´ zniakowski, The curse of di- mensionality for numerical integration of smooth functions, Math. Comp. 83 (290), 2853–2863, 2014. [11]

2014
[16]

Hinrichs, E

A. Hinrichs, E. Novak, M. Ullrich and H. Wo´ zniakowski, The curse of di- mensionality for numerical integration of smooth functions II, J. C omplexity 30, 117–143, 2014. [9, 11]

2014
[17]

Hinrichs, E

A. Hinrichs, E. Novak, M. Ullrich and H. Wo´ zniakowski, Product r ules are optimal for numerical integration in classical smoothness spaces, J. Com- plexity 38, 39–49, 2017. [9, 11]

2017
[18]

Hinrichs, J

A. Hinrichs, J. Prochno and M. Ullrich, The curse of dimensionality for numerical integration on general domains, J. Complexity 50, 25–42, 2019. [11]

2019
[19]

Hlawka, Ausf¨ ullung und ¨Uberdeckung konvexer K¨ orper durch konvexe K¨ orper, Monatsh

E. Hlawka, Ausf¨ ullung und ¨Uberdeckung konvexer K¨ orper durch konvexe K¨ orper, Monatsh. Math.53, 81–131, 1949. [5]

1949
[20]

A. N. Kolmogorov and V. M. Tikhomirov, ε-entropy and ε-capacity of sets in functional spaces, Amer. Math. Soc. Transl. 17, 277–364, 1959. [5]

1959
[21]

Krieg, Tensor power sequences and the approximation of te nsor product operators, J

D. Krieg, Tensor power sequences and the approximation of te nsor product operators, J. Complexity 44, 30–51, 2018. [3]

2018
[22]

Krieg, Uniform recovery of high-dimensional C r-functions, J

D. Krieg, Uniform recovery of high-dimensional C r-functions, J. Complexity 50, 116–126, 2019. [10] 15

2019
[23]

Kr¨ oger, Upper bounds for the Neumann eigenvalues on a bounded domain in Euclidean space, J

P. Kr¨ oger, Upper bounds for the Neumann eigenvalues on a bounded domain in Euclidean space, J. Funct. Anal. 106, 353–357, 1992. [13]

1992
[24]

K¨ uhn, W

T. K¨ uhn, W. Sickel and T. Ullrich, Approximation numbers of Sob olev embeddings – Sharp constants and tractability, J. Complexity 30, 95–116,
[25]

K¨ uhn, W

T. K¨ uhn, W. Sickel and T. Ullrich, Approximation of mixed order S obolev functions on the d-torus: asymptotics, preasymptotics, and d-dependence, Constr. Approx. 42, 353–398, 2015. [3]

2015
[26]

Li and S.-T

P. Li and S.-T. Yau, On the Schr¨ odinger equation and the eigen value prob- lem, Comm. Math. Phys. 88, 309–318, 1983. [13]

1983
[27]

Mieth, Sharp estimates for approximation numbers of non-p eriodic Sobolev embeddings, J

T. Mieth, Sharp estimates for approximation numbers of non-p eriodic Sobolev embeddings, J. Complexity, to appear. [2, 3, 12, 13]
[28]

F. J. Narcowich, J. D. Ward and H. Wendland, Sobolev bounds on func- tions with scattered zeros, with applications to radial basis functio n surface ﬁtting, Math. Comp. 74, 743–763, 2004. [2, 10, 12]

2004
[29]

Novak, Deterministic and Stochastic Error Bounds in Numerical Ana ly- sis, LNiM 1349, Springer Verlag, Berlin, 1988

E. Novak, Deterministic and Stochastic Error Bounds in Numerical Ana ly- sis, LNiM 1349, Springer Verlag, Berlin, 1988. [4]

1988
[30]

Novak and H

E. Novak and H. Triebel, Function spaces in Lipschitz domains and optimal rates of convergence for sampling, Constr. Approx. 23, 325–350, 2006. [2, 10, 12]

2006
[31]

Novak and H

E. Novak and H. Wo´ zniakowski, Tractability of Multivariate Problems , Vol- ume 1, Linear Information, European Math. Soc., Z¨ urich, 2008. [2 , 3]

2008
[32]

Novak and H

E. Novak and H. Wo´ zniakowski, Tractability of Multivariate Problems , Vol- ume II: Standard Information for Functionals, European Math. S oc. Publ. House, Z¨ urich, 2010. [3]

2010
[33]

Novak and H

E. Novak and H. Wo´ zniakowski, Approximation of inﬁnitely diﬀere ntiable multivariate functions is intractable, J. Complexity 25, 398–404, 2009. [3, 14]

2009
[34]

Novak and H

E. Novak and H. Wo´ zniakowski, Tractability of Multivariate Problems , Vol- ume III: Standard Information for Operators, European Math. Soc. Publ. House, Z¨ urich, 2012. [3]

2012
[35]

C. A. Rogers, A note on coverings, Mathematika 4, 1–6, 1957. [5]

1957
[36]

L. G. Rogers. Degree independent Sobolev extension on locally u niform domains. J. Funct. Anal. 235, 619–665, 2006. [13]

2006
[37]

W. A. Strauss, Partial Diﬀerential Equations, John Wiley and So ns, 2008. [12] 16

2008
[38]

A. G. Sukharev, Optimal method of constructing best uniform approxima- tions for functions of a certain class, USSR Comput. Math. Math. P hys. 18(2), 21–31, 1978. [4, 5]

1978
[39]

A. G. Sukharev, Optimal numerical integration formulas for so me classes of functions, Sov. Math. Dokl. 20, 472–475, 1979. [9]

1979
[40]

Triebel, Wavelet para-bases and sampling numbers in function spaces on domains, J

H. Triebel, Wavelet para-bases and sampling numbers in function spaces on domains, J. Complexity 23, 468–497, 2007. [2]

2007
[41]

Triebel, Function Spaces and Wavelets on Domains , European Mathe- matical Society (EMS), Z¨ urich, 2008

H. Triebel, Function Spaces and Wavelets on Domains , European Mathe- matical Society (EMS), Z¨ urich, 2008. [2]

2008
[42]

Triebel, Bases in Function Spaces, Sampling, Discrepancy, Numerica l Integration, European Mathematical Society (EMS), Z¨ urich, 2010

H. Triebel, Bases in Function Spaces, Sampling, Discrepancy, Numerica l Integration, European Mathematical Society (EMS), Z¨ urich, 2010. [2]

2010
[43]

Tulovsky, Distribution of eigenvalues for diﬀerential equatio ns with con- stant coeﬃcients, Functional Anal

V. Tulovsky, Distribution of eigenvalues for diﬀerential equatio ns with con- stant coeﬃcients, Functional Anal. Appl. 5, 241–245, 1972. [12]

1972
[44]

Vyb ´ ıral, Sampling numbers and function spaces, J

J. Vyb ´ ıral, Sampling numbers and function spaces, J. Complexity 23, 773– 792, 2007. [2]

2007
[45]

Vyb ´ ıral, Widths of embeddings in function spaces, J

J. Vyb ´ ıral, Widths of embeddings in function spaces, J. Complexity 22, 545–570, 2008. [2]

2008
[46]

Vyb ´ ıral, Weak and quasi-polynomial tractability of approximation of in- ﬁnitely diﬀerentiable functions, J

J. Vyb ´ ıral, Weak and quasi-polynomial tractability of approximation of in- ﬁnitely diﬀerentiable functions, J. Complexity 30, 48–55, 2014. [14]

2014
[47]

Weimar, Tractability results for weighted Banach spaces of s mooth func- tions

M. Weimar, Tractability results for weighted Banach spaces of s mooth func- tions. J. Complexity 28, 59–75, 2012. [14]

2012
[48]

Weyl, Das asymptotische Verteilungsgesetz der Eigenwerte linearer par- tieller Diﬀerentialgleichungen, Math

H. Weyl, Das asymptotische Verteilungsgesetz der Eigenwerte linearer par- tieller Diﬀerentialgleichungen, Math. Ann. 71, 441–479, 1912. [12]

1912
[49]

Guiqiao Xu, On weak tractability of the Smolyak algorithm for appr oxima- tion problems. J. Approx. Th. 192, 347–361, 2015. [14] 17

2015

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

V. F. Babenko, S. V. Borodachov and D. S. Skorokhodov, Optim al recovery of isotropic classes of twice-diﬀerentiable multivariate functions, J. Com- plexity 26, 591–607, 2010. [11]

work page 2010

[2] [2]

Barthelmann, E

V. Barthelmann, E. Novak and K. Ritter, High dimensional polynom ial interpolation on sparse grids, Adv. Comput. Math. 12, 273–288, 2000. [14]

work page 2000

[3] [3]

non-smooth

M. S. Birman and M. Z. Solomjak, The principal term of the spectr al asymp- totics for “non-smooth” elliptic problems, Functional Anal. Appl. 4, 265– 275, 1970. [12, 13]

work page 1970

[4] [4]

M. S. Birman and M. Z. Solomjak, Asymptotic behavior of the spec trum of diﬀerential equations, J. Soviet Math. 12, 247–283, 1979. [12]

work page 1979

[5] [5]

M. S. Birman and M. Z. Solomjak, Quantitative analysis in Sobolev imb ed- ding theorems and applications to spectral theory, AMS Translatio ns Series 2, 114. AMS 1980. [12]

work page 1980

[6] [6]

E. V. Chernaya, On the optimization of weighted cubature formu lae on certain classes of continuous functions, East J. Approx. 1, 47–60, 1995. [8]

work page 1995

[7] [7]

Cobos, T

F. Cobos, T. K¨ uhn and W. Sickel, Optimal approximation of multiva riate periodic Sobolev functions in the sup-norm, J. Functional Analysis 270, 4196–4212, 2016. [3] 14

work page 2016

[8] [8]

Dahlke, E

S. Dahlke, E. Novak and W. Sickel, Optimal approximation of elliptic p rob- lems by linear and nonlinear mappings I. J. Complexity 22, 29–49, 2006. [2]

work page 2006