Search

This paper focuses on the approximation of continuous functions on the unit sphere by spherical polynomials of degree n via hyperinterpolation. Hyperinterpolation of degree n is a discrete approximation of the L 2 -orthogonal projection of the same degree with its Fourier coefficients evaluated by a positive-weight quadrature rule that exactly integrates all spherical polynomials of degree at most 2 n. This paper aims to bypass this quadrature exactness assumption by replacing it with the Marcinkiewicz–Zygmund property proposed in a previous paper. Consequently, hyperinterpolation can be constructed by a positive-weight quadrature rule (not necessarily with quadrature exactness). This scheme is referred to as unfettered hyperinterpolation. This paper provides a reasonable error estimate for unfettered hyperinterpolation. The error estimate generally consists of two terms: a term representing the error estimate of the original hyperinterpolation of full quadrature exactness and another introduced as compensation for the loss of exactness degrees. A guide to controlling the newly introduced term in practice is provided. In particular, if the quadrature points form a quasi-Monte Carlo (QMC) design, then there is a refined error estimate. Numerical experiments verify the error estimates and the practical guide. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we investigate optimal linear approximations (n -approximation numbers) of the embeddings from the Sobolev spaces H r (r > 0) for various equivalent norms and the Gevrey type spaces G α , β (α , β > 0) on the sphere S d and on the ball B d , where the approximation error is measured in the L 2 -norm. We obtain preasymptotics, asymptotics, and strong equivalences of the above approximation numbers as a function in n and the dimension d. We emphasize that all equivalence constants in the above preasymptotics and asymptotics are independent of the dimension d and n. As a consequence we obtain that for the absolute error criterion the approximation problems I d : H r → L 2 are weakly tractable if and only if r > 1 , not uniformly weakly tractable, and do not suffer from the curse of dimensionality. We also prove that for any α , β > 0 , the approximation problems I d : G α , β → L 2 are uniformly weakly tractable, not polynomially tractable, and quasi-polynomially tractable if and only if α ≥ 1. [ABSTRACT FROM AUTHOR]

In this paper we provide a characterization of the complexity class PSPACE by using a purely continuous model defined with polynomial ordinary differential equations. [ABSTRACT FROM AUTHOR]

Abstract The paper is devoted to discretization of integral norms of functions from a given collection of finite dimensional subspaces. For natural collections of subspaces of the multivariate trigonometric polynomials we construct sets of points, which are optimally (in the sense of order) good for each subspace of a collection from the point of view of the integral norm discretization. We call such sets universal. Our construction of the universal sets is based on deep results on existence of special nets, known as (t , r , d) -nets. [ABSTRACT FROM AUTHOR]

In this paper we study tractability properties of the weighted star discrepancy with general coefficients of centered regular grids with different mesh-sizes. We give exact characterizations of the weight sequences ( γ j ) j ≥ 1 such that the regular grid with different mesh-sizes achieves weak, uniform weak, quasi polynomial, polynomial or strong polynomial tractability for the γ -weighted star discrepancy. For example, a necessary and sufficient condition such that the regular grid with different mesh-sizes achieves weak tractability for the γ -weighted star discrepancy is lim j → ∞ j γ j = 0 . [ABSTRACT FROM AUTHOR]

We call shifted power a polynomial of the form ( x − a ) e . The main goal of this paper is to obtain broadly applicable criteria ensuring that the elements of a finite family F of shifted powers are linearly independent or, failing that, to give a lower bound on the dimension of the space of polynomials spanned by F . In particular, we give simple criteria ensuring that the dimension of the span of F is at least c . | F | for some absolute constant c < 1 . We also propose conjectures implying the linear independence of the elements of F . These conjectures are known to be true for the field of real numbers, but not for the field of complex numbers. The verification of these conjectures for complex polynomials directly imply new lower bounds in algebraic complexity. [ABSTRACT FROM AUTHOR]

The main result of this paper is a proof that for any integrable function f on the torus, any sequence of its orthogonal projections ( P ˜ n f ) onto periodic spline spaces with arbitrary knots Δ ˜ n and arbitrary polynomial degree converges to f almost everywhere with respect to the Lebesgue measure, provided the mesh diameter ∣ Δ ˜ n ∣ tends to zero. We also give a new and simpler proof of the fact that the operators P ˜ n are bounded on L ∞ independently of the knots Δ ˜ n . [ABSTRACT FROM AUTHOR]

Let F ( x ) : = ( f i j ( x ) ) i = 1 , … , p ; j = 1 , … , q , be a ( p × q )-real polynomial matrix and let f ( x ) be the smallest singular value function of F ( x ) . In this paper, we first give the following nonsmooth version of Łojasiewicz gradient inequality for the function f with an explicit exponent: For any x ̄ ∈ R n , there exist c > 0 and ϵ > 0 such that we have for all ‖ x − x ̄ ‖ < ϵ , inf { ‖ w ‖ : w ∈ ∂ f ( x ) } ≥ c | f ( x ) − f ( x ̄ ) | 1 − τ , where ∂ f ( x ) is the limiting subdifferential of f at x , d : = max i = 1 , … , p ; j = 1 , … , q deg f i j , ℛ ( n , d ) : = d ( 3 d − 3 ) n − 1 if d ≥ 2 and ℛ ( n , d ) : = 1 if d = 1 , and τ : = 1 ℛ ( n + p , 2 d + 2 ) . Then we establish some versions of Łojasiewicz inequality for the distance function with explicit exponents, locally and globally, for the smallest singular value function f ( x ) of the matrix F ( x ) . [ABSTRACT FROM AUTHOR]

The PCP theorem has recently been shown to hold as well in the real number model of Blum, Shub, and Smale (Baartse and Meer, 2015). The proof given there structurally closely follows the proof of the original PCP theorem by Dinur (2007). In this paper we show that the theorem also can be derived using algebraic techniques similar to those employed by Arora et al. (Arora et al., 1998; Arora and Safra, 1998) in the first proof of the PCP theorem. This needs considerable additional efforts. Due to severe problems when using low degree algebraic polynomials over the reals as codewords for one of the verifiers to be constructed, we work with certain trigonometric polynomials. This entails the necessity to design new segmentation procedures in order to obtain well structured real verifiers appropriate for applying the classical technique of verifier composition. We believe that designing as well an algebraic proof for the real PCP theorem on one side leads to interesting questions in real number complexity theory and on the other sheds light on which ingredients are necessary in order to prove an important result as the PCP theorem in different computational models. [ABSTRACT FROM AUTHOR]

In this paper we give lower bounds for the representation of real univariate polynomials as sums of powers of degree 1 polynomials. We present two families of polynomials of degree d such that the number of powers that are required in such a representation must be at least of order d . This is clearly optimal up to a constant factor. Previous lower bounds for this problem were only of order Ω ( d ) , and were obtained from arguments based on Wronskian determinants and “shifted derivatives”. We obtain this improvement thanks to a new lower bound method based on Birkhoff interpolation (also known as “lacunary polynomial interpolation”). [ABSTRACT FROM AUTHOR]

Abstract: This is a follow-up paper of “Liberating the dimension for function approximation”, where we studied approximation of infinitely variate functions by algorithms that use linear information consisting of finitely many linear functionals. In this paper, we study similar approximation problems, however, now the algorithms can only use standard information consisting of finitely many function values. We assume that the cost of one function value depends on the number of active variables. We focus on polynomial tractability, and occasionally also study weak tractability. We present non-constructive and constructive results. Non-constructive results are based on known relations between linear and standard information for finitely variate functions, whereas constructive results are based on Smolyak’s construction generalized to the case of infinitely variate functions. Surprisingly, for many cases, the results for standard information are roughly the same as for linear information. [Copyright &y& Elsevier]

Abstract: Berrizbeitia and Olivieri showed in a recent paper that, for any integer , the notion of -prime to base leads to a primality test for numbers mod , that under the Extended Riemann Hypothesis (ERH) runs in polynomial time. They showed that the complexity of their test is at most the complexity of the Miller primality test (MPT), which is . They conjectured that their test is more effective than the MPT if is large. In this paper, we show that their conjecture is not true by showing that the Berrizbeitia–Olivieri primality test (BOPT) has no advantage over the MPT, either for proving primality of a prime under the ERH, or for detecting compositeness of a composite. In particular, we point out that the complexity of the BOPT depends not only on but also on and that in the worst cases (usually when is prime) for both tests, the BOPT is in general at least twice slower than the MPT, and in some cases (usually when is composite) the BOPT may be much slower. Moreover, the BOPT needs bit memories. We also give facts and numerical examples to show that, for some composites and for some , the th roots of unity do not exist, and thus outputs of the BOPT are ERH conditional, whereas the MPT always quickly and definitely (without ERH) detects compositeness for all odd composites. [Copyright &y& Elsevier]

Abstract: Many papers study polynomial tractability for multivariate problems. Let be the minimal number of information evaluations needed to reduce the initial error by a factor of for a multivariate problem defined on a space of -variate functions. Here, the initial error is the minimal error that can be achieved without sampling the function. Polynomial tractability means that is bounded by a polynomial in and and this holds for all . In this paper we study generalized tractability by verifying when can be bounded by a power of for all , where can be a proper subset of . Here is a tractability function, which is non-decreasing in both variables and grows slower than exponentially to infinity. In this article we consider the set for some and . We study linear tensor product problems for which we can compute arbitrary linear functionals as information evaluations. We present necessary and sufficient conditions on such that generalized tractability holds for linear tensor product problems. We show a number of examples for which polynomial tractability does not hold but generalized tractability does. [Copyright &y& Elsevier]

We improve the algorithms of Lauder-Wan [11] and Harvey [8] to compute the zeta function of a system of m polynomial equations in n variables, over the q element finite field F q , for large m. The dependence on m in the original algorithms was exponential in m. Our main result is a reduction of the dependence on m from exponential to polynomial. As an application, we speed up a doubly exponential algorithm from a recent software verification paper [3] (on universal equivalence of programs over finite fields) to singly exponential time. One key new ingredient is an effective, finite field version of the classical Kronecker theorem which (set-theoretically) reduces the number of defining equations for a polynomial system over F q when q is suitably large. [ABSTRACT FROM AUTHOR]

In 1941, Claude Shannon introduced the General Purpose Analog Computer (GPAC) as a mathematical model of Differential Analysers, that is to say as a model of continuous-time analog (mechanical, and later on electronic) machines of that time. Following Shannon’s arguments, functions generated by the GPAC must satisfy a polynomial differential algebraic equation (DAE). As it is known that some computable functions like Euler’s Γ ( x ) = ∫ 0 ∞ t x − 1 e − t d t or Riemann’s Zeta function ζ ( x ) = ∑ k = 0 ∞ 1 k x do not satisfy any polynomial DAE, this argument has often been used to demonstrate in the past that the GPAC is less powerful than digital computation. It was proved in Bournez et al. (2007), that if a more modern notion of computation is considered, i.e. in particular if computability is not restricted to real-time generation of functions, the GPAC is actually equivalent to Turing machines. Our purpose is first to discuss the robustness of the notion of computation involved in Bournez et al. (2007), by establishing that many natural variants of the notion of computation from this paper lead to the same computability result. Second, to go from these computability results towards considerations about (time) complexity: we explore several natural variants for measuring time/space complexity of a computation. Quite surprisingly, whereas defining a robust time complexity for general continuous time systems is a well known open problem, we prove that all variants are actually equivalent even at the complexity level. As a consequence, it seems that a robust and well defined notion of time complexity exists for the GPAC, or equivalently for computations by polynomial ordinary differential equations. Another side effect of our proof is also that we show in some way that polynomial ordinary differential equations can actually be used as a kind of programming model, and that there is a rather nice and robust notion of ordinary differential equation (ODE) programming. [ABSTRACT FROM AUTHOR]

We study approximation properties of sequences of centered random elements X d , d ∈ N , with values in separable Hilbert spaces. We focus on sequences of tensor product-type random elements, which have covariance operators of corresponding tensor product form. The average case approximation complexity n X d ( ε ) is defined as the minimal number of evaluations of arbitrary linear functionals that is needed to approximate X d with relative 2 -average error not exceeding a given threshold ε ∈ ( 0 , 1 ) . The growth of n X d ( ε ) as a function of ε − 1 and d determines whether a sequence of corresponding approximation problems for X d , d ∈ N , is tractable or not. Different types of tractability were studied in the paper by Lifshits et al. (J. Complexity, 2012), where for each type the necessary and sufficient conditions were found in terms of the eigenvalues of the marginal covariance operators. We revise the criterion of quasi-polynomial tractability and provide a simplified version. We illustrate our result by applying it to random elements corresponding to tensor products of squared exponential kernels. We also extend a recent result of Xu (2014) concerning weighted Korobov kernels. [ABSTRACT FROM AUTHOR]

We establish the Central Limit Theorem, as the degree goes to infinity, for the normalized volume of the zero set of a rectangular Kostlan–Shub–Smale random polynomial system. This paper is a continuation of Central Limit Theorem for the number of real roots of Kostlan–Shub–Smale random polynomial systems by the same authors in which the case of square systems was considered. Our main tools are Kac-Rice formula and an expansion of the volume of the level set into the Itô-Wiener Chaos. [ABSTRACT FROM AUTHOR]

Periodic sequences over finite fields have been used as key streams in private-key cryptosystems since the 1950s. Such periodic sequences should have a series of cryptographic properties in order to resist many attack methods. The binary generalized cyclotomic periodic sequences, constructed by the cyclotomic classes over finite fields, have good pseudo-random properties and correlation properties. In this paper, the linear complexity and minimal polynomials of some generalized cyclotomic sequences over GF( q ) have been determined where q = p m and p is an odd prime. Results show that these sequences have high linear complexity over GF( q ) for a large part of odd prime power q , which means they can resist the linear attack method. [ABSTRACT FROM AUTHOR]

In this paper, we present algorithms for the approximation of multivariate periodic functions by trigonometric polynomials. The approximation is based on sampling of multivariate functions on rank-1 lattices. To this end, we study the approximation of periodic functions of a certain smoothness. Our considerations include functions from periodic Sobolev spaces of generalized mixed smoothness. Recently an algorithm for the trigonometric interpolation on generalized sparse grids for this class of functions was investigated by Griebel and Hamaekers (2014). The main advantage of our method is that the algorithm is based mainly on a single one-dimensional fast Fourier transform, and that the arithmetic complexity of the algorithm depends only on the cardinality of the support of the trigonometric polynomial in the frequency domain. Therefore, we investigate trigonometric polynomials with frequencies supported on hyperbolic crosses and energy norm based hyperbolic crosses in more detail. Furthermore, we present an algorithm for sampling multivariate functions on perturbed rank-1 lattices and show the numerical stability of the suggested method. Numerical results are presented up to dimension d = 10 , which confirm the theoretical findings. [ABSTRACT FROM AUTHOR]

In this paper, we present error estimates for the approximation of multivariate periodic functions in periodic Hilbert spaces of isotropic and dominating mixed smoothness by trigonometric polynomials. The approximation is based on sampling of the multivariate functions on rank-1 lattices. We use reconstructing rank-1 lattices with generating vectors of Korobov form for the sampling and generalize the technique from Temlyakov (1986), in order to show that the aliasing error of that approximation is of the same order as the error of the approximation using the partial sum of the Fourier series. The main advantage of our method is that the computation of the Fourier coefficients of such a trigonometric polynomial, which we use as approximant, is based mainly on a one-dimensional fast Fourier transform, cf. Kämmerer et al. (2013), Kämmerer (2014). This means that the arithmetic complexity of the computation depends only on the cardinality of the support of the trigonometric polynomial in the frequency domain. Numerical results are presented up to dimension d = 10 . [ABSTRACT FROM AUTHOR]

In this paper we investigate multivariate integration in weighted unanchored Sobolev spaces of smoothness of arbitrarily high order. As quadrature points we employ higher order polynomial lattice point sets over F 2 which are randomly digitally shifted and then folded using the tent transformation. We first prove the existence of good higher order polynomial lattice rules which achieve the optimal rate of the mean square worst-case error, while reducing the required degree of modulus by half as compared to higher order polynomial lattice rules whose quadrature points are randomly digitally shifted but not folded using the tent transformation. Thus we are able to restrict the search space of generating vectors significantly. We then study the component-by-component construction as an explicit means of obtaining good higher order polynomial lattice rules. In a way analogous to Baldeaux et al. (2012), we show how to calculate the quality criterion efficiently and how to obtain the fast component-by-component construction using the fast Fourier transform. Our result generalizes the previous result shown by Cristea et al. (2007), in which the degree of smoothness is fixed at 2 and classical polynomial lattice rules are considered. [ABSTRACT FROM AUTHOR]

We study the approximation of compact linear operators defined over certain weighted tensor product Hilbert spaces. The information complexity is defined as the minimal number of arbitrary linear functionals needed to obtain an ε -approximation for the d -variate problem which is fully determined in terms of the weights and univariate singular values. Exponential tractability means that the information complexity is bounded by a certain function that depends polynomially on d and logarithmically on ε − 1. The corresponding unweighted problem was studied in Hickernell et al. (2020) with many negative results for exponential tractability. The product weights studied in the present paper change the situation. Depending on the form of polynomial dependence on d and logarithmic dependence on ε − 1 , we study exponential strong polynomial, exponential polynomial, exponential quasi-polynomial, and exponential (s , t) -weak tractability with max (s , t) ≥ 1. For all these notions of exponential tractability, we establish necessary and sufficient conditions on weights and univariate singular values for which it is indeed possible to achieve the corresponding notion of exponential tractability. The case of exponential (s , t) -weak tractability with max (s , t) < 1 is left for future study. The paper uses some general results obtained in Hickernell et al. (2020) and Kritzer and Woźniakowski (2019). [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we investigate the asymptotic behavior of the Gelfand, Kolmogorov and Weyl numbers of Sobolev embeddings in weighted function spaces of Besov and Triebel–Lizorkin type with polynomial weights. The exact estimates for the Gelfand and Kolmogorov numbers are obtained in the so-called non-limiting case and complement those previous results in the quasi-Banach setting. Also, the asymptotic order of the Weyl numbers is established by means of the basic Weyl estimates in the finite-dimensional spaces improved recently as well as flexible uses of the operator ideal technique. [Copyright &y& Elsevier]

Abstract: In this paper we study the convergence of the famous Weierstrass method for simultaneous approximation of polynomial zeros over a complete normed field. We present a new semilocal convergence theorem for the Weierstrass method under a new type of initial conditions. Our result is obtained by combining ideas of Weierstrass (1891) and Proinov (2010). A priori and a posteriori error estimates are also provided under the new initial conditions. [Copyright &y& Elsevier]

Abstract: The multivariate resultant is a fundamental tool of computational algebraic geometry. It can in particular be used to decide whether a system of homogeneous equations in variables is satisfiable (the resultant is a polynomial in the system’s coefficients which vanishes if and only if the system is satisfiable). In this paper, we investigate the complexity of computing the multivariate resultant. First, we study the complexity of testing the multivariate resultant for zero. Our main result is that this problem is -hard under deterministic reductions in any characteristic, for systems of low-degree polynomials with coefficients in the ground field (rather than in an extension). In null characteristic, we observe that this problem is in the Arthur–Merlin class if the generalized Riemann hypothesis holds true, while the best known upper bound in positive characteristic remains . Second, we study the classical algorithms to compute the resultant. They usually rely on the computation of the determinant of an exponential-size matrix, known as Macaulay matrix. We show that this matrix belongs to a class of succinctly representable matrices, for which testing the determinant for zero is proved -complete. This means that improving Canny’s upper bound requires either to look at the fine structure of the Macaulay matrix to find an ad hoc algorithm for computing its determinant, or to use altogether different techniques. [Copyright &y& Elsevier]

Abstract: In this paper, we study the decomposition of an NFSR into a cascade connection of an NFSR into an LFSR which is a kind of concatenation of an NFSR and an LFSR. It is shown that this problem can be solved based on polynomial factorization in , and a potential weakness of an NFSR that can be decomposed in such a way is further discussed. [Copyright &y& Elsevier]

Abstract: Many methods to compute the winding number of plane curves have been proposed, often with the aim of counting the number of roots of polynomials (or, more generally, zeros of analytic functions) inside some region by using the principle of argument. In this paper we propose another method, which are not based on numerical integration, but on discrete geometry. We give conditions that ensure its correct behavior, and a complexity bound based on the distance of the curve to singular cases. Besides, we provide a modification of the algorithm that detects the proximity to a singular case of the curve. If this proximity is such that the number of operations required grows over certain threshold, set by the user, the modified algorithm returns without winding number computation, but with information about the distance to singular case. When the method is applied to polynomials, this information refers to the localization of the roots placed near the curve. [Copyright &y& Elsevier]

Abstract: Tractability of multivariate problems has become a popular research subject. Polynomial tractability means that the solution of a -variate problem can be solved to within with polynomial cost in and . Unfortunately, many multivariate problems are not polynomially tractable. This holds for all non-trivial unweighted linear tensor product problems. By an unweighted problem we mean the case when all variables and groups of variables play the same role. It seems natural to ask what is the “smallest” non-exponential function for which we have -tractability of unweighted linear tensor product problems; that is, when the cost of a multivariate problem can be bounded by a multiple of a power of . Under natural assumptions, it turns out that this function is The function goes to infinity faster than any polynomial although not “much” faster, and that is why we refer to -tractability as quasi-polynomial tractability. The main purpose of this paper is to promote quasi-polynomial tractability, especially for the study of unweighted multivariate problems. We do this for the worst case and randomized settings and for algorithms using arbitrary linear functionals or only function values. We prove relations between quasi-polynomial tractability in these two settings and for the two classes of algorithms. [Copyright &y& Elsevier]

Abstract: In this paper we study planar polynomial differential systems of this form: where and , , and. A lot of properties of planar polynomial differential systems are related to irreducible Darboux polynomials of the corresponding derivation: . Darboux polynomials are usually computed with the method of undetermined coefficients. With this method we have to solve a polynomial system. We show that this approach can give rise to the computation of an exponential number of reducible Darboux polynomials. Here we show that the Lagutinskii–Pereira algorithm computes irreducible Darboux polynomials with degree smaller than , with a polynomial number, relatively to , and , binary operations. We also give a polynomial-time method to compute, if it exists, a rational first integral with bounded degree. [Copyright &y& Elsevier]

Abstract: We want to compute a worst case -approximation to the solution of the Helmholtz equation over the unit -cube , subject to Neumann boundary conditions on . We measure error in the -norm. Let denote the minimal number of evaluations of , , and needed to compute an absolute or normalized -approximation, assuming that , , and vary over balls of weighted reproducing kernel Hilbert spaces. This problem is said to be weakly tractable if grows subexponentially in and . It is said to be polynomially tractable if is polynomial in and , and strongly polynomially tractable if this polynomial is independent of . We have previously studied tractability for the homogeneous version of this problem. In this paper, we investigate the tractability of the non-homogeneous problem, with general . Using new perturbation estimates having explicit constants, we are able to relate the tractability of this problem to that of the -approximation problem. First, suppose that we use product weights, in which the role of any variable is moderated by its particular weight. We then find that if the sum of the weights is sublinearly bounded, then the problem is weakly tractable; moreover, this condition is more or less necessary. We then show that the problem is polynomially tractable if the sum of the weights is logarithmically or uniformly bounded, and we estimate the exponents of tractability for these two cases. Next, we turn to finite-order weights of fixed order , in which a -variate function can be decomposed as a sum, each term depending on at most variables. We show that the problem is always polynomially tractable for finite-order weights, and we give estimates for the exponents of tractability. Since our results so far have established nothing stronger than polynomial tractability, we look more closely at whether strong polynomial tractability is possible. We show that our problem is never strongly polynomially tractable for the absolute error criterion. Moreover, we believe that the same is true for the normalized error criterion, but we have been able to prove this lack of strong tractability only when certain conditions hold on the weights. Finally, we use the Korobov and min kernels, along with product weights, to illustrate our results. [Copyright &y& Elsevier]

Abstract: In this paper, we discuss the best approximation of functions by spherical polynomials and the approximation by Fourier partial summation operators, Vallée–Poussin operators, Cesàro operators, and Abel operators, on the Sobolev space on the sphere with a Gaussian measure, and obtain the average error estimates. We also get the asymptotic values for the average Kolmogorov and linear widths of the Sobolev space on the sphere and show that, in the average case setting, the spherical polynomial subspaces are the asymptotically optimal subspaces in the metric, and Fourier partial summation operators and Vallée–Poussin operators are the asymptotically optimal linear operators and are (modulo a constant) as good as optimal nonlinear operators in the metric. [Copyright &y& Elsevier]

In this paper, we study tractability of L 2 -approximation of one-periodic functions from weighted Korobov spaces in the worst-case setting. The considered weights are of product form. For the algorithms we allow information from the class Λ all consisting of all continuous linear functionals and from the class Λ std , which only consists of function evaluations. We provide necessary and sufficient conditions on the weights of the function space for quasi-polynomial tractability, uniform weak tractability, weak tractability and (σ , τ) -weak tractability. Together with the already known results for strong polynomial and polynomial tractability, our findings provide a complete picture of the weight conditions for all current standard notions of tractability. [ABSTRACT FROM AUTHOR]

Results on asymptotic characteristics of classes of functions with mixed smoothness are obtained in the paper. Our main interest is in estimating the Kolmogorov widths in the uniform norm of classes with small mixed smoothness. We prove the corresponding bounds for the unit balls of the trigonometric polynomials with frequencies from a hyperbolic cross. We demonstrate how our results on the Kolmogorov widths imply new upper bounds for the optimal sampling recovery in the L 2 norm of functions with small mixed smoothness. [ABSTRACT FROM AUTHOR]

The efficient evaluation of multivariate polynomials at many points is an important operation for polynomial system solving. Kedlaya and Umans have recently devised a theoretically efficient algorithm for this task when the coefficients are integers or when they lie in a finite field. In this paper, we assume that the set of points where we need to evaluate is fixed and "sufficiently generic". Under these restrictions, we present a quasi-optimal algorithm for multi-point evaluation over general fields. We also present a quasi-optimal algorithm for the opposite interpolation task. [ABSTRACT FROM AUTHOR]

This paper describes an algorithm which computes the characteristic polynomial of a matrix over a field within the same asymptotic complexity, up to constant factors, as the multiplication of two square matrices. Previously, this was only achieved by resorting to genericity assumptions or randomization techniques, while the best known complexity bound with a general deterministic algorithm was obtained by Keller-Gehrig in 1985 and involves logarithmic factors. Our algorithm computes more generally the determinant of a univariate polynomial matrix in reduced form, and relies on new subroutines for transforming shifted reduced matrices into shifted weak Popov matrices, and shifted weak Popov matrices into shifted Popov matrices. [ABSTRACT FROM AUTHOR]

Abstract: Regularized classifiers (a leading example is support vector machine) are known to be a kind of kernel-based classification methods generated from Tikhonov regularization schemes, and the polynomial kernels are the original and also probably the most important kernels used in them. In this paper, we provide an error analysis for the regularized classifiers using multivariate polynomial kernels. We introduce Bernstein–Durrmeyer polynomials, whose reproducing kernel Hilbert space norms and approximation properties in space play a key role in the analysis of regularization error. We also introduce the standard estimation of sample error, and derive explicit learning rates for these algorithms. [Copyright &y& Elsevier]

Abstract: Valiant introduced 20 years ago an algebraic complexity theory to study the complexity of polynomial families. The basic computation model used is the arithmetic circuit, which makes these classes very easy to define and open to combinatorial techniques. In this paper we gather known results and new techniques under a unifying theme, namely the restrictions imposed upon the gates of the circuit, building a hierarchy from formulas to circuits. As a consequence we get simpler proofs for known results such as the equality of the classes VNP and or the completeness of the Determinant for VQP, and new results such as a characterization of the classes VQP and VP (which we can also apply to the Boolean class LOGCFL) or a full answer to a conjecture in Bürgisser''s book [Completeness and reduction in algebraic complexity theory, Algorithms and Computation in Mathematics, vol. 7, Springer, Berlin, 2000]. We also show that for circuits of polynomial depth and unbounded size these models all have the same expressive power and can be used to characterize a uniform version of VNP. [Copyright &y& Elsevier]

Abstract: In this paper we prove the existence of digitally shifted polynomial lattice rules which achieve strong tractability results for Sobolev spaces of arbitrary high smoothness. The convergence rate is shown to be the best possible up to a given degree of smoothness of the integrand. Indeed we even show the existence of polynomial lattice rules which automatically adjust themselves to the smoothness of the integrand up to a certain given degree. Further we show that strong tractability under certain conditions on the weights can be obtained and that polynomial lattice rules exist for which the worst-case error can be bounded independently of the dimension. These results hold independent of the smoothness. [Copyright &y& Elsevier]

Abstract: Let be multivariate polynomials (with complex coefficients) in the variables . The common zero locus of these polynomials, for , determines an algebraic set. This algebraic set decomposes into a union of simpler, irreducible components. The set of polynomials imposes on each component a positive integer known as the multiplicity of the component. Multiplicity plays an important role in many practical applications. It determines roughly “how many times the component should be counted in a computation”. Unfortunately, many numerical methods have difficulty in problems where the multiplicity of a component is greater than one. The main goal of this paper is to present an algorithm for determining the multiplicity of a component of an algebraic set. The method sidesteps the numerical stability issues which have obstructed other approaches by incorporating a combined numerical-symbolic technique. [Copyright &y& Elsevier]

Abstract: In this paper, it is shown that the problem of deciding whether or not a geometric diagram in Euclidean Geometry is satisfiable is NP-hard and in PSPACE, and in fact has the same complexity as the satisfaction problem for a fragment of the existential theory of the real numbers. The related problem of finding all of the possible (satisfiable) diagrams that can result when a segment of a diagram is extended is also shown to be NP-hard. [Copyright &y& Elsevier]

In this paper, we introduce a notion of oblivious keyword search (OKS). Let W be the set of possible keywords. In the commit phase, a database supplier T commits n data. In each transfer subphase, a user U can choose a keyword w∈W adaptively and find Search(w) without revealing w to T, where Search(w) is the set of all data which includes w as a keyword.We then show two efficient protocols such that the size of the commitments is only O(nB) regardless of the size of W, where B is the size of each data. It is formally proved that U learns nothing more than search(w) and T gains no information on the keywords which U searched for. We further present a more efficient adaptive OTkn protocol than the previous one [19] as an application of our first OKS protocol. [Copyright &y& Elsevier]

Multivariate integration of high dimension s occurs in many applications. In many such applications, for example in finance, integrands can be well approximated by sums of functions of just a few variables. In this situation the superposition (or effective) dimension is small, and we can model the problem with finite-order weights, where the weights describe the relative importance of each distinct group of variables up to a given order (where the order is the number of variables in a group), and ignore all groups of variables of higher order.In this paper we consider multivariate integration for the anchored and unanchored (non-periodic) Sobolev spaces equipped with finite-order weights. Our main interest is tractability and strong tractability of QMC algorithms in the worst-case setting. That is, we want to find how the minimal number of function values needed to reduce the initial error by a factor &epsiv; depends on s and &epsiv;−1. If there is no dependence on s, and only polynomial dependence on &epsiv;−1, we have strong tractability, whereas with polynomial dependence on both s and &epsiv;−1 we have tractability.We show that for the anchored Sobolev space we have strong tractability for arbitrary finite-order weights, whereas for the unanchored Sobolev space we have tractability for all bounded finite-order weights. In both cases, the dependence on &epsiv;−1 is quadratic. We can improve the dependence on &epsiv;−1 at the expense of polynomial dependence on s. For finite-order weights, we may achieve almost linear dependence on &epsiv;−1 with a polynomial dependence on s whose degree is proportional to the order of the weights.We show that these tractability bounds can be achieved by shifted lattice rules with generators computed by the component-by-component (CBC) algorithm. The computed lattice rules depend on the weights. Similar bounds can also be achieved by well-known low discrepancy sequences such as Halton, Sobol and Niederreiter sequences which do not depend on the weights. We prove that these classical low discrepancy sequences lead to error bounds with almost linear dependence on n−1 and polynomial dependence on d. We present explicit worst-case error bounds for shifted lattice rules and for the Niederreiter sequence. Better tractability and error bounds are possible for finite-order weights, and even for general weights if they satisfy certain conditions. We present conditions on general weights that guarantee tractability and strong tractability of multivariate integration. [Copyright &y& Elsevier]

In this paper we generalize the notion of orthogonal Laurent polynomials to orthogonal rational functions. Orthogonality is considered with respect to a measure on the positive real line. From this, Gauss-type quadrature formulas are derived and multipoint Pade´ approximants for the Stieltjes transform of the measure. Convergence of both the quadrature formula and the multipoint Pade´ approximants is discussed. [Copyright &y& Elsevier]

Let Φ={φ1, …, φj} and let K be a closed basic set in Rn given by the polynomial inequalities φ1&ges;0, …, φj&ges;0. Let Σ{Φ} be the semiring generated by the φk and the squares in R[x1, …, xn]. For example, if Φ={φ1} then Σ{Φ}=σ1+σ2φ1, where σ1, σ2 are sums of squares of polynomials. Schmu¨dgen has shown that if K is compact then any polynomial strictly positive on K belongs to Σ{Φ}. This paper develops a result of Schmu¨dgen type for functions in one dimension merely nonnegative on K. For this, it is necessary to add additional hypotheses, such as the proximity of complex zeros, to compensate for the loss of strict positivity necessary for Schmu¨dgen's result. [Copyright &y& Elsevier]

Let Π n d denote the space of spherical polynomials of degree at most n on the unit sphere S d ⊂ R d + 1 that is equipped with the surface Lebesgue measure d σ normalized by ∫ S d d σ (x) = 1. This paper establishes a close connection between the asymptotic Nikolskii constant, L ∗ (d) ≔ lim n → ∞ 1 dim Π n d sup f ∈ Π n d ‖ f ‖ L ∞ (S d) ‖ f ‖ L 1 (S d) , and the following extremal problem: I α ≔ inf a k ‖ j α + 1 (t) − ∑ k = 1 ∞ a k j α ( q α + 1 , k t ∕ q α + 1 , 1 ) ‖ L ∞ (R +) with the infimum being taken over all sequences { a k } k = 1 ∞ ⊂ R such that the infinite series converges absolutely a.e. on R +. Here j α denotes the Bessel function of the first kind normalized so that j α (0) = 1 , and { q α + 1 , k } k = 1 ∞ denotes the strict increasing sequence of all positive zeros of j α + 1. We prove that for α ≥ − 0. 272 , I α = ∫ 0 q α + 1 , 1 j α + 1 (t) t 2 α + 1 d t ∫ 0 q α + 1 , 1 t 2 α + 1 d t = 1 F 2 (α + 1 ; α + 2 , α + 2 ; − q α + 1 , 1 2 4 ). As a result, we deduce that the constant L ∗ (d) goes to zero exponentially fast as d → ∞ : 0. 5 d ≤ L ∗ (d) ≤ (0. 857 ⋯) d (1 + ε d) with ε d = O (d − 2 ∕ 3). [ABSTRACT FROM AUTHOR]

In this paper we revisit the classical problem of polynomial interpolation, with a slight twist; namely, polynomial evaluations are available up to a group action of the unit circle on the complex plane. It turns out that this new setting allows for a phaseless recovery of a polynomial in a polynomial time. [ABSTRACT FROM AUTHOR]

In 2008, Kedlaya and Umans designed the first multivariate multi-point evaluation algorithm over finite fields with an asymptotic complexity that can be made arbitrarily close to linear. However, it remains a major challenge to make their algorithm efficient for practical input sizes. In this paper, we revisit and improve their algorithm, while keeping this ultimate goal in mind. In addition we sharpen the known complexity bounds for modular composition of univariate polynomials over finite fields. [ABSTRACT FROM AUTHOR]