We determine the exact order of ε-complexity of the numerical integration problem for the anisotropic class Wr∞ (I d ) and Hr∞ (I d ) with respect to the worst case randomized methods and the average case deterministic methods. We prove this result by developing a decomposition technique of Borel measure on unit cube of d-dimensional Euclidean space. Moreover by the imbedding relationship between function classes we extend our results to the classes of functions W^ p (I d ) and H^ p (I d ). By the way we highlight some typical results and stress the importance of some open problems related to the complexity of numerical integration.

Let B := (B, || · ||b) be a Banach space and H := (H, || · ||h) a dense subspace of B. We are interested in the rate at which the distance of a given x∈ B from the ball of radius t in H tends to zero as t →1. This problem has numerous applications and its recent importance in the Cucker Smale theory of learning renewed our interest in this subject. We study two aspects of this problem. First, we obtain general results on the relation between the CS-functional and the Peetre K-functional. Secondly, we estimate it in the concrete case of Besov spaces by using functions of exponential type.

The main goal of this paper is to understand which properties of a basis are important for certain direct and inverse theorems in nonlinear approximation. We study greedy approximation with regard to bases with different properties. We consider bases that are tensor products of univariate greedy bases. Some results known for unconditional bases are extended to the case of quasi-greedy bases.

We study restricted Monte Carlo integration for anisotropic Hölder–Nikolskii classes. The results show that with clog2n random bits we have the same optimal order for the nth minimal Monte Carlo integration error as with arbitrary random numbers. We also study the computation of integration on anisotropic Sobolev classes in the quantum setting and present the optimal bound of nth minimal query error. The results show that the error bound of quantum algorithms is much smaller than that of deterministic and randomized algorithms.

In this paper we investigate the probabilistic linear (n, δ)-widths and paverage linear n-widths of the Sobolev space Wr 2 equipped with the Gaussian measure μ in the L∞-norm, and determine the asymptotic equalities λn,δ(Wr 2,μ, L∞) =开方( ln(n/δ)/ nr+(s−1)/2 , λ(a) n (Wr 2,μ, L∞)p=开方ln n/ nr+(s−1)/2 , 0 < p < ∞.