Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of Complexity

A new characterization of (s,t) -weak tractability

Arthur G. Werschulz, H. Woźniakowski

Published Oct 26, 2016• 15 citations
Publisher
DOI
10.1016/j.jco.2016.10.006

Related papers

Uniform Weak Tractability of Weighted Integration

Paweł Siedlecki

Springer proceedings in mathematics & statistics•Jan 1, 2016•0 citations

Tractability of $ L_2 $-approximation and integration over weighted Korobov spaces of increasing smoothness in the worst case setting

Weiran Ding, Jiansong Li, Yumeng Jia +1 more

This paper is devoted to the study of tractability of the $ L_2 $-approximation and integration from weighted Korobov spaces of increasing smoothness in the worst-case setting. The considered algorithms use information from the class $ \Lambda^{\rm all} $, including all continuous linear functionals, and from the class $ \Lambda^{\rm std} $, including function evaluations. Necessary and sufficient conditions on the weights of the function space for strong polynomial tractability, polynomial tractability, quasi-polynomial tractability, uniform weak tractability, weak tractability and $ (\sigma, \tau) $-weak tractability, are provided. Our results give a comprehensive picture of the weight conditions for all standard notions of algebraic tractability. It may be helpful to study the tractability of nonhomogeneous tensor product spaces.

Electronic Research Archive•Jan 1, 2025•0 citations

Generalized Tractability for Linear Functionals

Michael Gnewuch, Henryk Woźniakowski

Springer eBooks•Dec 28, 2007•14 citations

Diagnosis of Weaknesses in Modern Error Correction Codes: A Physics Approach

М. Г. Степанов, Vladimir Chernyak, Michael Chertkov +1 more

One of the main obstacles to the wider use of the modern error-correction codes is that, due to the complex behavior of their decoding algorithms, no systematic method which would allow characterization of the bit-error-rate (BER) is known. This is especially true at the weak noise where many systems operate and where coding performance is difficult to estimate because of the diminishingly small number of errors. We show how the instanton method of physics allows one to solve the problem of BER analysis in the weak noise range by recasting it as a computationally tractable minimization problem.

arXiv:cond-mat/0506037•Physical Review Letters•Nov 22, 2005•79 citations

Tractability of quasilinear problems I: General results

Arthur G. Werschulz, H. Woźniakowski

Journal of Approximation Theory•Nov 2, 2006•12 citations

Universal Aspects of a Strongly Interacting Impurity in a Dilute Bose Condensate

Pietro Massignan, Nikolay Yegovtsev, Victor Gurarie

We study the properties of an impurity immersed in a weakly interacting Bose gas, i.e., of a Bose polaron. In the perturbatively tractable limit of weak impurity-boson interactions many of its properties are known to depend only on the scattering length. Here we demonstrate that for strong (unitary) impurity-boson interactions all quasiparticle properties of a heavy Bose polaron, such as its energy, its residue, its Tan's contact, and the number of bosons trapped nearby the impurity, depend on the impurity-boson potential via a single parameter characterizing its range.

arXiv:2011.00846•Physical Review Letters•Mar 26, 2021•57 citations
This paper is devoted to the study of tractability of the $ L_2 $-approximation and integration from weighted Korobov spaces of increasing smoothness in the worst-case setting. The considered algorithms use information from the class $ \Lambda^{\rm all} $, including all continuous linear functionals, and from the class $ \Lambda^{\rm std} $, including function evaluations. Necessary and sufficient conditions on the weights of the function space for strong polynomial tractability, polynomial tractability, quasi-polynomial tractability, uniform weak tractability, weak tractability and $ (\sigma, \tau) $-weak tractability, are provided. Our results give a comprehensive picture of the weight conditions for all standard notions of algebraic tractability. It may be helpful to study the tractability of nonhomogeneous tensor product spaces.
One of the main obstacles to the wider use of the modern error-correction codes is that, due to the complex behavior of their decoding algorithms, no systematic method which would allow characterization of the bit-error-rate (BER) is known. This is especially true at the weak noise where many systems operate and where coding performance is difficult to estimate because of the diminishingly small number of errors. We show how the instanton method of physics allows one to solve the problem of BER analysis in the weak noise range by recasting it as a computationally tractable minimization problem.
We study the properties of an impurity immersed in a weakly interacting Bose gas, i.e., of a Bose polaron. In the perturbatively tractable limit of weak impurity-boson interactions many of its properties are known to depend only on the scattering length. Here we demonstrate that for strong (unitary) impurity-boson interactions all quasiparticle properties of a heavy Bose polaron, such as its energy, its residue, its Tan's contact, and the number of bosons trapped nearby the impurity, depend on the impurity-boson potential via a single parameter characterizing its range.