We study the L p -discrepancy of random point sets in high dimensions, with emphasis on small values of p . Although the classical L p -discrepancy suffers from the curse of dimensionality for all p ∈ ( 1 , ∞ ) , the gap between known upper and lower bounds remains substantial, in particular for small p ≥ 1 . To clarify this picture, we review the existing results for i.i.d. uniformly distributed points and derive new upper bounds for generalized L p -discrepancies, obtained by allowing non-uniform sampling densities and corresponding non-negative quadrature weights. Using the probabilistic method, we show that random points drawn from optimally chosen product densities lead to significantly improved upper bounds. For p = 2 these bounds are explicit and optimal; for general p ∈ [ 1 , ∞ ) we obtain sharp asymptotic estimates. The improvement can be interpreted as a form of importance sampling for the underlying Sobolev space F d , q . Our results also reveal that, even with optimal densities, the curse of dimensionality persists for random points when p ≥ 1 , and it becomes most pronounced for small p . This suggests that the curse should also hold for the classical L 1 -discrepancy for deterministic point sets.

We prove lower bounds on the worst-case error of numerical integration in tensor product spaces. The information complexity is the minimal number N of function evaluations that is necessary such that the N -th minimal error is less than a factor ε times the initial error, i.e., the error for N = 0 , where ε belongs to ( 0 , 1 ) . We are interested to which extent the information complexity depends on the number d of variables of the integrands. If the information complexity grows exponentially fast in d , then the integration problem is said to suffer from the curse of dimensionality. Under the assumption of the existence of a worst-case function for the uni-variate problem, we present two methods for providing lower bounds on the information complexity. The first method is based on a suitable decomposition of the worst-case function and can be seen as a generalization of the method of decomposable reproducing kernels. The second method, although only applicable for positive quadrature rules, does not require a suitable decomposition of the worst-case function. Rather, it is based on a spline approximation of the worst-case function and can be used for analytic functions. Several applications of both methods are presented.

The Lp-discrepancy is a quantitative measure for the irregularity of distribution of an N-element point set in the d-dimensional unit-cube, which is closely related to the worst-case error of quasi-Monte Carlo algorithms for numerical integration. It's inverse for dimension d and error threshold ε∈(0,1) is the minimal number of points in [0,1)d such that the minimal normalized Lp-discrepancy is less or equal ε. It is well known, that the inverse of L2-discrepancy grows exponentially fast with the dimension d, i.e., we have the curse of dimensionality, whereas the inverse of L∞-discrepancy depends exactly linearly on d. The behavior of inverse of Lp-discrepancy for general p∉{2,∞} has been an open problem for many years. In this paper we show that the Lp-discrepancy suffers from the curse of dimensionality for all p in (1,2] which are of the form p=2ℓ/(2ℓ−1) with ℓ∈N. This result follows from a more general result that we show for the worst-case error of numerical integration in an anchored Sobolev space with anchor 0 of once differentiable functions in each variable whose first derivative has finite Lq-norm, where q is an even positive integer satisfying 1/p+1/q=1.

Function values are, in some sense, “almost as good” as general linear information for L2-approximation (optimal recovery, data assimilation) of functions from a reproducing kernel Hilbert space. This was recently proved by new upper bounds on the sampling numbers under the assumption that the singular values of the embedding of this Hilbert space into L2 are square-summable. Here we mainly prove new lower bounds. In particular we prove that the sampling numbers behave worse than the approximation numbers for Sobolev spaces with small smoothness. Hence there can be a logarithmic gap also in the case where the singular numbers of the embedding are square-summable. We first prove new lower bounds for the integration problem, again for rather classical Sobolev spaces of periodic univariate functions.

This paper deals with the worst case setting for approximating multivariate tensor product linear operators defined over Hilbert spaces. Approximations are obtained by using a number of linear functionals from a given class of information. We consider the three classes of information: the class of all linear functionals, the Fourier class of inner products with respect to given orthonormal elements, and the standard class of function values. We wish to determine which problems are tractable and which are strongly tractable. The complete analysis is provided for approximating operators of rank two or more. The problem of approximating linear functionals is fully analyzed in the first two classes of information. For the third class of standard information we show that the possibilities are very rich. We prove that tractability of linear functionals depends on the given space of functions. For some spaces all nontrivial normed linear functionals are intractable, whereas for other spaces all linear functionals are tractable. In “typical” function spaces, some linear functionals are tractable and some others are not.

The topological complexity of zero-finding is studied using a BSS machine over the reals with an information node. The topological complexity depends on the class of functions, the class of arithmetic operations, and on the error criterion. For the root error criterion the following results are established. If only Hölder operations are permitted as arithmetic operations then the topological complexity is roughly −log2ϵ and bisection is optimal. This holds even for the small class of linear functions. On the other hand, for the class of all increasing functions, if we allow the sign function or division, together with log and exp, then the topological complexity drops to zero. For the residual error criterion, results can be totally different than for the root error criterion. For example, the topological complexity can be zero for the residual error criterion, and roughly −log2ϵ for the root error criterion.

In this paper we bound the infimum of the ratio of adaptive to nonadaptive information for linear problems in Banach spaces. This result resolves the conjecture on adaption, showing that adaption can help for linear problems. Letting α denote the above infimum, and α2 the same infimum over all linear problems with Hilbert space range, we show that 12 ⩽ α ≤ √8665 and α2 ≤ α2 ≤ √0.8665. Analogous results are presented for classes of problems with Lp and finite-dimensional range spaces. Additionally it is shown that continuous information can yield smaller error (radius of information) than linear information in a Banach space setting. This resolves an open question of B. Kacewicz and G. W. Wasilkowski, who showed that this cannot occur in Hilbert space settings.