Quasi-polynomial tractability (Q544123): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: Generalized tractability for multivariate problems. I: Linear tensor product problems and linear information / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3504234 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Generalized tractability for multivariate problems. II: Linear tensor product problems, linear information, and unrestricted tractability / rank
 
Normal rank
Property / cites work
 
Property / cites work: Tractability of multivariate integration for periodic functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Quasi-Monte Carlo methods can be efficient for integration over products of spheres / rank
 
Normal rank
Property / cites work
 
Property / cites work: Worst case complexity of multivariate Feynman--Kac path integration / rank
 
Normal rank
Property / cites work
 
Property / cites work: Intractability results for integration and discrepancy / rank
 
Normal rank
Property / cites work
 
Property / cites work: Tractability of multivariate problems. Volume I: Linear information / rank
 
Normal rank
Property / cites work
 
Property / cites work: Tractability of multivariate problems. Volume II: Standard information for functionals. / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the tractability of linear tensor product problems in the worst case / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3993279 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Finite-order weights imply tractability of linear multivariate problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: The power of standard information for multivariate approximation in the randomized setting / rank
 
Normal rank
Property / cites work
 
Property / cites work: Tractability and strong tractability of linear multivariate problems / rank
 
Normal rank

Latest revision as of 04:29, 4 July 2024

scientific article
Language Label Description Also known as
English
Quasi-polynomial tractability
scientific article

    Statements

    Quasi-polynomial tractability (English)
    0 references
    0 references
    0 references
    14 June 2011
    0 references
    This paper deals with tractability of multivariate problems. Polynomial tractability means that the solution of a \(d\)-variate problem can be solved to within \(\varepsilon\) with polynomial cost in \(\varepsilon^{-1}\) and \(d\). Unfortunately, many multivariate problems (e.g., all non-trivial unweighted linear tensor product problems) are not polynomially tractable. It is natural to as for the ``smallest'' non-exponential function \(T:[1,\infty)\times[1,\infty)\to [1,\infty)\) for which the unweighted linear tensor product is \(T\)-tractable. I.e. the cost of a multivariate problem is bounded by a multiple of a power of \(T(\varepsilon^{-1},d)\). This paper considers \(T(x,y)=\exp((1+\ln x)(1+\ln y))\), and calls the corresponding \(T\)-tractability the quasi-polynomial tractability. The authors study unweigthed multivariate problems in the worst-case and randomized settings. They show relations between quasi-polynomial tractability in these two settings and for the two classes of algorithms.
    0 references
    0 references
    linear tensor product problems
    0 references
    multivariate approximation
    0 references
    worst-case setting
    0 references
    randomized setting
    0 references
    linear information
    0 references
    standard information
    0 references
    0 references