pith. sign in

arxiv: 2606.13339 · v1 · pith:HDKQVHBSnew · submitted 2026-06-11 · 🧮 math.NA · cs.NA

A Note About Algebraic (s, t)-Weak Tractability Of Linear Tensor Product Problems In The Worst-Case Setting

Zirong Liu , Heping Wang This is my paper

Pith reviewed 2026-06-27 05:58 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords algebraic weak tractabilitytensor product problemsworst-case settingsingular valueslinear functionalsinformation complexityabsolute error criterion
0
0 comments X

The pith

Algebraic (s, t)-weak tractability of linear tensor product problems holds exactly when the univariate singular values satisfy explicit decay conditions, provided the square of the largest univariate singular value exceeds one.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies linear tensor product problems in the worst-case setting where algorithms may use any finite number of continuous linear functional evaluations. It focuses on algebraic (s, t)-weak tractability under the absolute error criterion in the regime where the square of the univariate maximal singular value is greater than one. The authors derive necessary and sufficient conditions on the univariate singular values that decide whether this tractability property holds. These conditions close an open case left by prior work on the same class of problems.

Core claim

For linear tensor product problems in the worst-case setting under the absolute error criterion, algebraic (s, t)-weak tractability holds if and only if the univariate singular values obey certain explicit conditions, and this equivalence is established precisely when the square of the univariate maximal singular value exceeds one.

What carries the argument

The algebraic (s, t)-weak tractability criterion, which characterizes the growth of the information complexity as a function of the error threshold and the dimension parameter.

Load-bearing premise

The square of the univariate maximal singular value must be strictly greater than one, and the setting must be the absolute error criterion.

What would settle it

A concrete counter-example consisting of a sequence of univariate singular values with λ₁ > 1 whose associated tensor-product information complexity violates the predicted growth bound for some choice of s and t would falsify the claimed equivalence.

read the original abstract

This paper is devoted to discussing the linear tensor product problems in the worst case setting. We consider algorithms that use finitely many evaluations of arbitrary continuous linear functionals. We investigate algebraic $(s, t)$-weak tractability (ALG-$(s, t)$-WT) under the absolute error criterion in the case ${\lambda}_1 > 1$, where ${\lambda}_1$ is the square of the univariate maximal singular value. We solve the problem by giving the necessary and sufficient conditions for ALG-$(s, t)$-WT on univariate singular values and fill the gap left open.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript investigates algebraic (s, t)-weak tractability (ALG-(s, t)-WT) for linear tensor product problems in the worst-case setting, where algorithms use finitely many evaluations of arbitrary continuous linear functionals. Restricted to the regime λ₁ > 1 (with λ₁ the square of the univariate maximal singular value) and the absolute error criterion, the paper derives necessary and sufficient conditions for ALG-(s, t)-WT expressed directly in terms of the univariate singular values, claiming to close an open gap in the literature.

Significance. If the stated conditions are correctly established, the result supplies a complete, checkable characterization of ALG-(s, t)-WT within the explicitly scoped regime. This strengthens the tractability theory for tensor-product problems by reducing the multivariate question to verifiable properties of the univariate singular-value sequence, a concrete advance for information-based complexity.

minor comments (2)
  1. The abstract asserts that the conditions 'fill the gap left open' but does not cite the specific prior result or section that left the question unresolved; adding an explicit reference in the introduction would clarify the contribution.
  2. The definition of λ₁ appears only in the abstract; repeating the notation and its meaning at the start of §2 or §3 would improve readability for readers who begin with the main text.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and recommendation of minor revision. No specific major comments were listed in the report, so we have nothing further to address point by point. The manuscript stands as submitted.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper states a direct characterization: necessary and sufficient conditions for ALG-(s,t)-WT are given explicitly in terms of the univariate singular values, restricted to the regime λ1 > 1 under the absolute error criterion. This is a standard mathematical characterization result on the input data (singular values) rather than a derivation that reduces by construction to fitted quantities, self-definitions, or load-bearing self-citations. No equations or steps in the provided framing equate a claimed prediction back to its own inputs, and the analysis is scoped without invoking prior author results as uniqueness theorems. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, the paper operates inside the standard framework of linear tensor product problems in the worst-case setting with the absolute error criterion; no free parameters, ad-hoc axioms, or new entities are mentioned.

axioms (1)
  • domain assumption Linear tensor product problems are considered in the worst-case setting using finitely many evaluations of arbitrary continuous linear functionals under the absolute error criterion.
    This is the explicit setting stated in the abstract.

pith-pipeline@v0.9.1-grok · 5626 in / 1146 out tokens · 26107 ms · 2026-06-27T05:58:45.987580+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references

  1. [1]

    J. Chen, H. Wang. Average case tractability of multivariate approximation with Gaussian kernels. Journal of Approximation Theory, 2019, 239: 51-71

    2019

  2. [2]

    J. Dick, P. Kritzer, F. Pillichshammer, H. Wo´ zniakowski. Approximation of analytic functions in Korobov spaces. Journal of Complexity, 2014, 30: 2-28

    2014

  3. [3]

    J. Dick, G. Larcher, F. Pillichshammer, H. Wo´ zniakowski. Exponential conver- gence and tractability of multivariate integration for Korobov spaces. Mathe- matics of Computation, 2011, 80: 905-930

    2011

  4. [4]

    Gnewuch, H

    M. Gnewuch, H. Wo´ zniakowski. Quasi-polynomial tractability. Journal of Complexity, 2011, 27: 312-330. 11

    2011

  5. [5]

    F. J. Hickernell, P. Kritzer, H. Wo´ zniakowski. Exponential tractability of linear tensor product problems. In: D. R. Wood, J. DeGier, C. Praeger, T. Tao (eds.), MATRIX Annals. Cham: Springer, 2020

    2020

  6. [6]

    Irrgeher, P

    C. Irrgeher, P. Kritzer, F. Pillichshammer, H. Wo´ zniakowski. Tractability of multivariate approximation defined over Hilbert spaces with exponential weights. Journal of Approximation Theory, 2016, 207: 301-338

    2016

  7. [7]

    Kritzer, H

    P. Kritzer, H. Wo´ zniakowski. Simple characterizations of exponential tractabil- ity for linear multivariate problems. Journal of Complexity, 2019, 51: 110-128

    2019

  8. [8]

    Kritzer, F

    P. Kritzer, F. Pillichshammer, H. Wo´ zniakowski. Exponential tractability of linear weighted tensor product problems in the worst-case setting for arbitrary linear functionals. Journal of Complexity, 2020, 61: 101501

    2020

  9. [9]

    Novak, H

    E. Novak, H. Wo´ zniakowski.Tractability of Multivariate Problems, Volume I: Linear Information. Zurich: European Mathematical Society, 2008

    2008

  10. [10]

    Novak, H

    E. Novak, H. Wo´ zniakowski.Tractability of Multivariate Problems, Volume II: Standard Information for Functionals. Zurich: European Mathematical Soci- ety, 2010

    2010

  11. [11]

    Novak, H

    E. Novak, H. Wo´ zniakowski.Tractability of Multivariate Problems, Volume III: Standard Information for Operators. Zurich: European Mathematical Society, 2012

    2012

  12. [12]

    Papageorgiou, I

    A. Papageorgiou, I. Petras. A new criterion for tractability of multivariate problems. Journal of Complexity, 2014, 30: 604-619

    2014

  13. [13]

    Papageorgiou, I

    A. Papageorgiou, I. Petras, H. Wo´ zniakowski. (s,lnκ)-weak tractability of lin- ear problems. Journal of Complexity, 2017, 40: 1-16

    2017

  14. [14]

    Siedlecki

    P. Siedlecki. Uniform weak tractability. Journal of Complexity, 2013, 29: 438- 453

    2013

  15. [15]

    Siedlecki, M

    P. Siedlecki, M. Weimar. Notes on (s, t) weak tractability: a refined classifi- cation of problems with (sub)exponential information complexity. Journal of Approximation Theory, 2015, 200: 227-258

    2015

  16. [16]

    H. Wang. A note about EC-(s, t)-weak tractability of multivariate approxima- tion with analytic Korobov kernels. Journal of Complexity, 2019, 55: 101412

    2019

  17. [17]

    G. Xu. Exponential convergence-tractability of general linear problems in the average case setting. Journal of Complexity, 2015, 31: 617-636. School of Mathematical Sciences, Capital Normal University, Beijing 100048, China. Email address:2240501011@cnu.edu.cn School of Mathematical Sciences, Capital Normal University, Beijing 100048, China. Email address...

    2015