QuasiPolynomial Tractability
 Title:

QuasiPolynomial Tractability
 Author(s):

Gnewuch, Michael
Wozniakowski, Henryk
 Date:

2010
 Type:

Technical reports
 Department:

Computer Science
 Persistent URL:

http://hdl.handle.net/10022/AC:P:10503
 Series:

Columbia University Computer Science Technical Reports
 Part Number:

CUCS00610
 Publisher:

Department of Computer Science, Columbia University
 Publisher Location:

New York
 Abstract:

Tractability of multivariate problems has become nowadays a popular research subject. Polynomial tractability means that the solution of a dvariate problem can be solved to within $\varepsilon$ with polynomial cost in $\varepsilon^{1}$ and d. Unfortunately, many multivariate problems are not polynomially tractable. This holds for all nontrivial 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'' nonexponential function $T:[1,\infty)\times [1,\infty)\to[1,\infty)$ for which we have Ttractability 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 $T(\varepsilon^{1},d)$. Under natural assumptions, it turns out that this function is $T^{qpol}(x,y):=\exp((1+\ln\,x)(1+\ln y))$ for all $x,y\in[1,\infty)$. The function $T^{qpol}$ goes to infinity faster than any polynomial although not ``much'' faster, and that is why we refer to $T^{qpol}$tractability as quasipolynomial tractability. The main purpose of this paper is to promote quasipolynomial 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 quasipolynomial tractability in these two settings and for the two classes of algorithms.
 Subject(s):

Computer science
 Item views
 341
 Metadata:

text  xml
 Suggested Citation:

Michael Gnewuch, Henryk Wozniakowski,
2010,
QuasiPolynomial Tractability, Columbia University Academic Commons,
http://hdl.handle.net/10022/AC:P:10503.