Pith. sign in

REVIEW 2 major objections 4 minor 54 references

Computational Math with Neural Networks is Hard

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that, under the Strong Exponential Time Hypothesis, three basic numerical tasks—quadrature, solving Poisson's equation, and matrix-vector multiplication—are all stuck at first-order accuracy when the input is a neural…

desk verdict Good idea, careful reductions, but two of the three main theorems have exponentially wrong error tolerances — fixable, but as printed they don't prove what they claim. read the letter →

arxiv 2505.17751 v1 pith:YIEDIWXB submitted 2025-05-23 math.NA cs.NA

Michael Feischl , Fabian Zehetgruber This is my paper
classification math.NAcs.NA MSC 65D3065Y2068Q17
keywords neuralnetworkquadratureSETHlowerboundsPoissonequationmatrix-vectorproductquasi-MonteCarloReLUnetworkshigh-dimensionalintegration
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper claims that three basic numerical tasks—integrating a function encoded by a neural network, solving Poisson's equation when the source term is a neural network, and multiplying a matrix encoded by a neural network by a vector—cannot be done by any higher-order algorithm if the Strong Exponential Time Hypothesis (SETH) is true. This holds even when the algorithm is handed the full network representation, weights included, and for very simple feed-forward ReLU networks with three hidden layers, bounded weights, bounded output, and sparse connections. The reason is that deciding whether such a network realizes the zero function is already hard, and each of the three problems is non-local enough that an accurate solver would let you decide the satisfiability of Boolean formulas. If the claim is right, the common practice of using neural-network surrogates inside quadrature, PDE solvers, or matrix arithmetic carries a fundamental speed limit that has nothing to do with how well the networks approximate.

What carries the argument

The load-bearing construction is a map from a sparse $k$-CNF formula $\alpha$ to a ReLU network $\Phi_\alpha$ (Lemma 2.3) whose realization is a $[0,1]$-valued function on the hypercube: it is identically zero when $\alpha$ is unsatisfiable, and it is $1$ on a cube of volume $\delta^n$ around any satisfying assignment (Proposition 3.4). A quadrature rule with error below $\delta^n/2$ therefore decides $k$SAT, because the integral is either $0$ or at least $\delta^n$ (Lemmas 3.1 and 3.2). The same gap is transported to fixed dimension by an orthant-visiting curve $f_d$ built from ReLU networks (Lemma 3.11), and to the Poisson problem by a positivity estimate for the Green's function (Lemma 4.1) that turns a nonzero source into a pointwise signal at a fixed interior point. For matrix-vector products, a random-sampling argument (Lemma 5.1) restricts to formulas with few satisfying assignments and normalizes by the spectral norm so that a network-encoded matrix either is zero or has a detectable large image under $M\mathbf{1}$.

What would settle it

Run the paper's own reduction: take a sparse $k$-SAT formula from the Tseytin encoding, build $\Phi_\alpha$ from Lemma 2.3, and apply any candidate fast quadrature rule with error tolerance $\delta^n/2$. If the rule separates every satisfiable from every unsatisfiable instance in time $2^{tn}$ with $t<\widetilde{e}_{s_k}$, the reduction has a hidden flaw or SETH fails; conversely, a subexponential algorithm for sparse $k$SAT would directly refute Assumption 2.1.

Watch

Extended reading notes

Core claim

Under SETH, the paper establishes that no higher-order algorithm exists for three canonical tasks when the input object is encoded by a neural network, even if the algorithm receives the complete weight-and-bias representation. For quadrature on $[0,1]^d$, Theorem 3.7 and Corollary 3.8 say that any algorithm reaching accuracy $\varepsilon$ needs runtime at least $C^{-1}\varepsilon^{-1+\xi}$ for every $\xi>0$, on networks of width and depth $O(|\log_2 \varepsilon|)$; Corollary 3.13 gives the same bound in fixed dimension, and Corollaries 3.17 and 3.21 extend it to $p$-balls and general bounded domains. Corollary 4.3 transfers the bound to Poisson's equation with a neural-network source term, both pointwise and in $L^2$. Theorem 5.2 and the remark after it give the analogue for matrix-vector products with $N\times N$ matrices encoded by a network: for tolerance $\varepsilon \ge 1/\sqrt{N}$, the product cannot be computed significantly faster than $\varepsilon^{-4}$, while the paper also proves the results are sharp by giving fast quadrature for one-hidden-layer networks.

Load-bearing premise

The lower bounds all rest on the Strong Exponential Time Hypothesis, which says $k$SAT cannot be solved in $2^{(1-\epsilon)n}$ time for any $\epsilon>0$ as $k$ grows; if that conjecture is false, the conclusions disappear.

Editorial extensions

If this is right

  • Any quadrature algorithm that accepts network integrands—adaptive or not, with or without weight access—cannot beat error proportional to $1/t$ in $t$ operations, once the network has three or more hidden layers.
  • Variational PDE solvers and PINN-type methods that reduce to quadrature inherit this barrier, and pointwise or $L^2$ approximation of the Poisson solution map with network sources is itself bounded by $\varepsilon^{-1+\xi}$.
  • For matrices encoded by neural networks, matrix-vector multiplication with tolerance $\varepsilon \ge 1/\sqrt{N}$ cannot be done significantly faster than $\varepsilon^{-4}$, so the network encoding does not provide the fast arithmetic that tensor formats offer.
  • The barrier is sharp: one-hidden-layer ReLU networks admit explicit or exponentially convergent quadrature on the ball and hypercube, so the three-hidden-layer condition is essential for the lower bound.
  • Numerical experiments with Sobol points show order-one convergence on adversarial-style integrands and close-to-order-one convergence on random and trained networks, matching the lower bound in practice.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The mechanism suggests the true dividing line is locality: tasks whose output depends on the whole input function, such as integrals and elliptic solves, inherit zero-testing hardness, while local operations such as point evaluation or translating a transport equation do not; this predicts that a wider family of non-local PDE solution maps is hard in the same sense.
  • Because the networks in the reduction have bounded weights, bounded realization, and sparse connectivity, standard cures such as weight clipping or sparsity promotion cannot restore efficiency; the paper's open question of finding an expressive but tractable subclass likely needs structural restrictions, not size restrictions.
  • A concrete test of the mechanism on small formulas is to build $\Phi_\alpha$ for modest $n$ and run any claimed fast integrator: the gap between unsatisfiable (integral $0$) and satisfiable (integral at least $\delta^n$) should be preserved, and failure of that gap would indicate the reduction's constants, not SETH, are the practical bottleneck.
  • The observed order-one convergence of quasi-Monte Carlo on piecewise-linear network integrands suggests that existing QMC theory for piecewise-smooth functions could be extended to explain the sharpness phenomenon rigorously.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies the computational complexity of elementary numerical tasks when the input is a neural network representation. Under the Strong Exponential Time Hypothesis (SETH), the authors claim that no higher-order algorithms exist for quadrature of neural-network integrands, for solving the Poisson equation with a neural-network source term, and for matrix-vector products with neural-network encoded matrices, even when the algorithm has full access to the network weights. The proof strategy reduces kSAT satisfiability to the numerical task by constructing a network whose realization is either identically zero or is at least one on a small set, depending on satisfiability. The paper also gives fast quadrature algorithms for one-layer networks and presents numerical evidence that quasi-Monte Carlo methods achieve roughly first-order convergence in the number of points.

Significance. If the central claims are correct, the paper establishes strong conditional negative results: natural computational-mathematics tasks with neural-network inputs admit no algorithms with convergence order better than one, despite full weight access, for networks of logarithmic size and width. The reduction framework is explicit and clean, the SETH assumption is stated transparently, and the constructions give concrete classes of hard networks. The numerical experiments are independent of the lower-bound proofs and provide useful supporting evidence. However, as submitted, two of the three flagship theorems, Theorem 4.2 and Theorem 5.2, contain a mismatch between the error tolerance and the satisfiable/unsatisfiable separation that invalidates their proofs as printed. The quadrature results in Section 3 appear structurally sound, aside from a harmless measure typo.

major comments (2)
  1. [Theorem 4.2 (Section 4)] The proof asserts that for a satisfiable formula the constructed source satisfies ||f||_{L1(Omega0)} >= q^d delta^{-n}. This is impossible because 0 <= F_alpha <= 1 and the domain Omega0 has volume q^d, so the integral lies between q^d delta^n and q^d. Lemma 4.1 therefore gives u_Phi(x) of order V ||f||_{L1}, which in the satisfiable case is of order delta^n, not delta^{-n}. Since the stated error tolerance in Theorem 4.2 is of order delta^{-n}, it is exponentially larger than the separation between the satisfiable case and the zero solution in the unsatisfiable case. The proposed test comparing A(Phi) with half of the claimed lower bound cannot separate the two cases. The theorem and its Corollary 4.3 do not follow as stated; a consistent tolerance of order delta^n is needed, and the corollary must be re-derived with that corrected threshold.
  2. [Theorem 5.2 (Section 5)] The proof computes the satisfiable/unsatisfiable separation as |y| / (||M_Phi||_2 |1|) >= 2^{-(3/2 - e_s_k + delta)n}, but the theorem's displayed error tolerance is 2^{-(1/2 - 1 + e_s_k - delta)n/2}. In the SETH-relevant regime e_s_k close to 1, the separation is exponentially smaller than the allowed error; for example, with e_s_k = 1 and delta = 0.1, the separation is about 2^{-0.6n} while the tolerance is 2^{-0.2n}. Consequently the decision procedure based on comparing A(Phi) with half the separation cannot work, and the claimed lower bound is not established. The exponent in the tolerance appears to contain a sign error and must be corrected to a value below half of the actual separation.
minor comments (4)
  1. [Proposition 3.4] Proposition 3.4 states |Q_alpha| = delta^n for Q_alpha = {x in [0,1]^d : max_{i=1..n} |z_i - x_i| <= delta}. Since each of the n coordinates has interval length 2 delta, the true measure is (2 delta)^n. This is not harmful because delta^n is a valid lower bound, but the equality should be corrected to an inequality or to the exact measure.
  2. [Theorem 5.2] The symbol delta is overloaded: it denotes both the width parameter from Proposition 3.4, which is required to satisfy 0 < delta < 1/2, and the positive gap parameter from Lemma 5.1, which must be below e_s_k. These are different roles and should use separate symbols to avoid ambiguity in the statement and proof.
  3. [Remark after Theorem 4.2] The L2-error display in the remark appears to contain a typo: the factor (2r/(e pi))^{d/2} should presumably read (2/(e pi))^{d/2} as in the theorem.
  4. [Corollary 4.3] Corollary 4.3 refers to a 'quadrature algorithm' although the task is approximation of the solution of a Poisson equation; this should be rephrased as an approximation algorithm for the PDE.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the lower bounds are reductions from the external SETH assumption; the sole self-citation is non-load-bearing.

full rationale

The paper's central claims are conditional lower bounds obtained by reduction from k-SAT under SETH. The derivation chain is: CNF formula -> neural network realization RΦα (Lemma 2.3) -> numerical task (quadrature, Poisson solve, matrix-vector product) -> decision algorithm for satisfiability -> contradiction with SETH. Each error tolerance is derived from an explicit measure/separation quantity, e.g. ν = δ^n in Proposition 3.4, and the algorithms are converted into SAT decision procedures by comparing the approximation to a threshold; nothing is fitted to the quantity being predicted, and no parameter is calibrated from the numerical experiments in Section 6. The only self-citation is [14] in Section 1, which merely points to a training-related approach and is not used in any theorem proof. The paper also contains honest limitations, such as the Section 4 remark that the arguments do not transfer to more complex PDEs and the Section 6.4 statement that a theoretical explanation of the QMC observations is missing; these are not circular. The internally flagged sign inconsistencies in the error tolerances of Theorems 4.2 and 5.2 are correctness concerns rather than circularity, since the reductions would remain reductions if those estimates were corrected. The derivation is self-contained relative to external, machine-independent complexity assumptions, so the circularity burden is very low; the score reflects only the presence of one minor, non-load-bearing self-citation.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central claim rests on the external SETH assumption and on standard results in complexity theory, network composition, and PDE theory. The only hand-chosen parameters are delta and rho, both construction parameters with hardness holding for all allowed values. No new physical or mathematical entities are introduced.

free parameters (3)
  • delta = 0 < delta < 1/2, chosen close to 1/2 in corollaries
    Controls the transition width of the ReLU gate r and the volume delta^n of the satisfiable witness set. The hardness results hold for every delta in (0,1/2), so it is not tuned to fit data.
  • rho = 1
    Bias constant in the formula encoding (2.4); fixed to 1, and any value producing the needed gap would work.
  • C_k (sparsification constant) = constant from the sparsification lemma
    Appears as eC_k in the clause-count bound of S~_k(n); taken from Impagliazzo, Paturi, and Zane [30], not chosen by the authors.
assumptions (5)
  • domain assumption Strong Exponential Time Hypothesis (Assumption 2.1), including lim_k s_k = 1
    The paper's main external hypothesis. All runtime lower bounds are conditional on SETH.
  • standard math Sparsification lemma (Impagliazzo, Paturi, Zane, Theorem 1)
    Used in Lemma 2.2 to restrict to formulas with linearly many clauses and to define S~_k(n).
  • standard math Tseytin transformation converts any Boolean formula to equisatisfiable CNF with linear blowup
    Invoked in the remark after the SAT definitions to justify restricting to CNF formulas.
  • standard math Green's function representation and weak maximum principle for the Poisson problem
    Used in Lemma 4.1 to prove the pointwise lower bound on the solution u_Phi on the interior subdomain Omega0.
  • domain assumption Probabilistic Turing machine / RAM with random numbers as the computational model
    Section 2.2 and Lemma 5.1 require access to random sampling; the matrix-vector lower bound is stated for randomized models.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Computational Math with Neural Networks is Hard." pith.science (2026). https://pith.science/paper/YIEDIWXB

@misc{pith2026250517751,
  author       = {Pith},
  title        = {Pith review of: Computational Math with Neural Networks is Hard},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YIEDIWXB}},
  note         = {Machine review of arXiv:2505.17751}
}
read the original abstract

We show that under some widely believed assumptions, there are no higher-order algorithms for basic tasks in computational mathematics such as: Computing integrals with neural network integrands, computing solutions of a Poisson equation with neural network source term, and computing the matrix-vector product with a neural network encoded matrix. We show that this is already true for very simple feed-forward networks with at least three hidden layers, bounded weights, bounded realization, and sparse connectivity, even if the algorithms are allowed to access the weights of the network. The fundamental idea behind these results is that it is already very hard to check whether a given neural network represents the zero function. The non-locality of the problems above allow us to reduce the approximation setting to deciding whether the input is zero or not. We demonstrate sharpness of our results by providing fast quadrature algorithms for one-layer networks and giving numerical evidence that quasi-Monte Carlo methods achieve the best possible order of convergence for quadrature with neural networks.

Figures

Figures reproduced from arXiv: 2505.17751 by the authors.

Figure 1
Figure 1. The connectivity graph of Φα from Lemma 2.3 for formulas α of the form (γ1x1 ∨ γ2x2 ∨ γ3x3) ∧ (γ4x2 ∨ γ5x4) with γi ∈ {id, ¬}. 3.2. Quadrature on the hypercube. Given n, d ∈ N and a neural network Φ ∈ N (d, w, L, θ) we would like to find algorithms A such that A(Φ) approximates the integral Z [0,1]d (3.3) RΦ(x1, . . . , xd) dx up to accuracy δ n for some 0 < δ < 1/2. We will show that there is a limit to the efficie… view at source ↗
Figure 2
Figure 2. Left: Quadrature error for quasi-Monte Carlo quadrature with Sobol points for randomly initialized networks with input dimension five, three to nine hidden layers, and width 100 as well as for a network with input dimension 784, three hidden layers and width 784 trained on the MNIST dataset. The dashed line represents O(1/t). Right: Visualization of the linear pieces of the realization RΦ of the networks, where same… view at source ↗
Figure 3
Figure 3. Left: Quadrature error for quasi-Monte Carlo quadrature with Sobol points for the integrand f from (6.1). The dashed line represents O(1/t). Right: Example visualization of f in 2D. 6.5.1. The unit ball. Let Ω denote the d dimensional unit ball Ω = Bd equipped with the normalized Lebesgue measure µ. For this case, the quadrature problem can be solved explicitly. A change of variables that rotates the coordinate syst… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

54 extracted references · 36 canonical work pages

  1. [1]

    Azizzadenesheli, N

    K. Azizzadenesheli, N. Kovachki, Z. Li, M. Liu-Schiaffini, J. Kossaifi, and A. Anandkumar. Neural Operators for Accelerating Scientific Simulations and Design . 2024. arXiv: 2309.15325 [cs.LG]. url: https://arxiv.org/abs/2309.15325

    arXiv 2024

  2. [2]

    Volumes of sections of cubes and related problems

    K. Ball. “Volumes of sections of cubes and related problems”. In: Geometric aspects of functional analysis (1987–88). Vol. 1376. Lecture Notes in Math. Springer, Berlin, 1989, pp. 251–260.url: https: //doi.org/10.1007/BFb0090058

    work page doi:10.1007/bfb0090058 1987

  3. [3]

    Neural networks as smooth priors for inverse problems for PDEs

    J. Berg and K. Nystr¨ om. “Neural networks as smooth priors for inverse problems for PDEs”. In: Journal of Computational Mathematics and Data Science 1 (2021), p. 100008. url: https://www. sciencedirect.com/science/article/pii/S2772415821000043

    work page 2021

  4. [4]

    Some remarkable properties of sinc and related integrals

    D. Borwein and J. M. Borwein. “Some remarkable properties of sinc and related integrals”. In: Ra- manujan J. 5.1 (2001), pp. 73–89. url: https://doi.org/10.1023/A:1011497229317

    work page doi:10.1023/a:1011497229317 2001

  5. [5]

    The complexity of satisfiability of small depth circuits

    C. Calabro, R. Impagliazzo, and R. Paturi. “The complexity of satisfiability of small depth circuits”. In: Parameterized and exact computation . Vol. 5917. Lecture Notes in Comput. Sci. Springer, Berlin, 2009, pp. 75–85. url: https://doi.org/10.1007/978-3-642-11269-0_6

    work page doi:10.1007/978-3-642-11269-0_6 2009

  6. [6]

    Solving the quantum many-body problem with artificial neural networks

    G. Carleo and M. Troyer. “Solving the quantum many-body problem with artificial neural networks”. In: Science 355.6325 (2017), pp. 602–606. eprint: https://www.science.org/doi/pdf/10.1126/ science.aag2302. url: https://www.science.org/doi/abs/10.1126/science.aag2302

    doi:10.1126/science.aag2302 2017

  7. [7]

    P. J. Davis and P. Rabinowitz. Methods of numerical integration. Corrected reprint of the second (1984) edition. Dover Publications, Inc., Mineola, NY, 2007, pp. xii+612

    work page 1984

  8. [8]

    Approximation algorithms for training one-node ReLU neural networks

    S. S. Dey, G. Wang, and Y. Xie. “Approximation algorithms for training one-node ReLU neural networks”. In: IEEE Trans. Signal Process. 68 (2020), pp. 6696–6706. url: https://doi.org/10. 1109/TSP.2020.3039360

    arXiv 2020

Show all 54 references
  1. [9]

    High-dimensional integration: The quasi-Monte Carlo way

    J. Dick, F. Y. Kuo, and I. H. Sloan. “High-dimensional integration: The quasi-Monte Carlo way”. In: Acta Numerica 22 (2013), pp. 133–288

    2013

  2. [10]

    Expression of Fractals Through Neural Network Functions

    N. Dym, B. Sober, and I. Daubechies. “Expression of Fractals Through Neural Network Functions”. In: IEEE Journal on Selected Areas in Information Theory 1.1 (2020), pp. 57–66

    2020

  3. [11]

    Algorithms for solving high dimensional PDEs: from nonlinear Monte Carlo to machine learning

    W. E, J. Han, and A. Jentzen. “Algorithms for solving high dimensional PDEs: from nonlinear Monte Carlo to machine learning”. In: Nonlinearity 35.1 (2022), pp. 278–310. url: https://doi.org/10. 1088/1361-6544/ac337f. 27

    2022

  4. [12]

    The Deep Ritz Method: A Deep Learning-Based Numerical Algorithm for Solving Variational Problems

    W. E and B. Yu. “The Deep Ritz Method: A Deep Learning-Based Numerical Algorithm for Solving Variational Problems”. In: Communications in Mathematics and Statistics 6.1 (Mar. 2018), pp. 1–12. url: https://doi.org/10.1007/s40304-018-0127-z

    2018 doi

  5. [13]

    The deep Ritz method: a deep learning-based numerical algorithm for solving variational problems

    W. E and B. Yu. “The deep Ritz method: a deep learning-based numerical algorithm for solving variational problems”. In: Commun. Math. Stat. 6.1 (2018), pp. 1–12. url: https://doi.org/10. 1007/s40304-018-0127-z

    2018

  6. [14]

    Feischl, A

    M. Feischl, A. Rieder, and F. Zehetgruber. Towards optimal hierarchical training of neural networks

  7. [15]

    Deep Neural Networks and Adaptive Quadrature for Solving Variational Problems

    D. Fokina, O. Iliev, and I. Oseledets. “Deep Neural Networks and Adaptive Quadrature for Solving Variational Problems”. In: Large-Scale Scientific Computing. Ed. by I. Lirkov and S. Margenov. Cham: Springer International Publishing, 2022, pp. 369–377

    2022

  8. [16]

    Hyperplane sections of the n-dimensional cube

    R. Frank and H. Riede. “Hyperplane sections of the n-dimensional cube”. In: Amer. Math. Monthly 119.10 (2012), pp. 868–872. url: https://doi.org/10.4169/amer.math.monthly.119.10.868

    2012 doi

  9. [17]

    Froese and C

    V. Froese and C. Hertrich. Training Neural Networks is NP-Hard in Fixed Dimension . 2024. arXiv: 2303.17045 [cs.CC]. url: https://arxiv.org/abs/2303.17045

    2024 arXiv

  10. [18]

    Gold-standard solutions to the Schr¨ odinger equation using deep learning: How much physics do we need?

    L. Gerard, M. Scherbela, P. Marquetand, and P. Grohs. “Gold-standard solutions to the Schr¨ odinger equation using deep learning: How much physics do we need?” In: ArXiv abs/2205.09438 (2022). url: https://api.semanticscholar.org/CorpusID:248887574

    2022 arXiv

  11. [19]

    Gilbarg and N

    D. Gilbarg and N. S. Trudinger. Elliptic partial differential equations of second order . Classics in Mathematics. Reprint of the 1998 edition. Springer-Verlag, Berlin, 2001, pp. xiv+517

    1998

  12. [20]

    Analysis of preintegration followed by quasi–Monte Carlo integration for distribution functions and densities

    A. D. Gilbert, F. Y. Kuo, and I. H. Sloan. “Analysis of preintegration followed by quasi–Monte Carlo integration for distribution functions and densities”. In: SIAM J. Numer. Anal. 61.1 (2023), pp. 135–

    2023

  13. [21]

    Tight hardness results for training depth-2 ReLU networks

    S. Goel, A. Klivans, P. Manurangsi, and D. Reichman. “Tight hardness results for training depth-2 ReLU networks”. In: 12th Innovations in Theoretical Computer Science Conference . Vol. 185. LIPIcs. Leibniz Int. Proc. Inform. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 202...

    2021

  14. [22]

    Hierarchical singular value decomposition of tensors

    L. Grasedyck. “Hierarchical singular value decomposition of tensors”. In: SIAM J. Matrix Anal. Appl. 31.4 (2009/10), pp. 2029–2054. url: https://doi.org/10.1137/090764189

    2009 doi

  15. [23]

    A proof that artificial neural networks overcome the curse of dimensionality in the numerical approximation of Black-Scholes partial differen- tial equations

    P. Grohs, F. Hornung, A. Jentzen, and P. von Wurstemberger. “A proof that artificial neural networks overcome the curse of dimensionality in the numerical approximation of Black-Scholes partial differen- tial equations”. In: Mem. Amer. Math. Soc. 284.1410 (2023), pp. v+93. url...

    2023

  16. [24]

    Grohs, S

    P. Grohs, S. Lanthaler, and M. Trautner. Theory-to-Practice Gap for Neural Networks and Neural Operators. 2025. arXiv: 2503.18219 [cs.LG]. url: https://arxiv.org/abs/2503.18219

    2025 arXiv

  17. [25]

    Proof of the theory-to-practice gap in deep learning via sampling complexity bounds for neural network approximation spaces

    P. Grohs and F. Voigtlaender. “Proof of the theory-to-practice gap in deep learning via sampling complexity bounds for neural network approximation spaces”. In: Found. Comput. Math. 24.4 (2024), pp. 1085–1143. url: https://doi.org/10.1007/s10208-023-09607-w

    2024 doi

  18. [26]

    A new scheme for the tensor representation

    W. Hackbusch and S. K¨ uhn. “A new scheme for the tensor representation”. In: J. Fourier Anal. Appl. 15.5 (2009), pp. 706–722. url: https://doi.org/10.1007/s00041-009-9094-9

    2009 doi

  19. [27]

    Solving high-dimensional eigenvalue problems using deep neural networks: A diffusion Monte Carlo like approach

    J. Han, J. Lu, and M. Zhou. “Solving high-dimensional eigenvalue problems using deep neural networks: A diffusion Monte Carlo like approach”. In: Journal of Computational Physics 423 (2020), p. 109792. url: https://www.sciencedirect.com/science/article/pii/S0021999120305660

    2020

  20. [28]

    Neural and spectral operator surrogates: unified construction and expression rate bounds

    L. Herrmann, C. Schwab, and J. Zech. “Neural and spectral operator surrogates: unified construction and expression rate bounds”. In: Adv. Comput. Math. 50.4 (2024), Paper No. 72, 43. url: https : //doi.org/10.1007/s10444-024-10171-2

    2024 doi

  21. [29]

    On the complexity of k-SAT

    R. Impagliazzo and R. Paturi. “On the complexity of k-SAT”. In: vol. 62. 2. Special issue on the Four- teenth Annual IEEE Conference on Computational Complexity (Atlanta, GA, 1999). 2001, pp. 367–

    1999

  22. [30]

    Which Problems Have Strongly Exponential Complex- ity?

    R. Impagliazzo, R. Paturi, and F. Zane. “Which Problems Have Strongly Exponential Complex- ity?” In: Journal of Computer and System Sciences 63.4 (2001), pp. 512–530. url: https://www. sciencedirect.com/science/article/pii/S002200000191774X. 28

    2001

  23. [31]

    QTT approximation of elliptic solution operators in higher dimensions

    B. N. Khoromskij and I. V. Oseledets. “QTT approximation of elliptic solution operators in higher dimensions”. In: Russian J. Numer. Anal. Math. Modelling 26.3 (2011), pp. 303–322. url: https: //doi.org/10.1515/RJNAMM.2011.017

    2011 doi

  24. [32]

    N. B. Kovachki, S. Lanthaler, and A. M. Stuart. Operator Learning: Algorithms and Analysis . 2024. arXiv: 2402.15715 [cs.LG]. url: https://arxiv.org/abs/2402.15715

    2024 arXiv

  25. [33]

    The Decision Problem for a Class of First-Order Formulas in Which all Disjunctions are Binary

    M. R. Krom. “The Decision Problem for a Class of First-Order Formulas in Which all Disjunctions are Binary”. In: Mathematical Logic Quarterly 13.1-2 (1967), pp. 15–20. eprint: https://onlinelibrary. wiley.com/doi/pdf/10.1002/malq.19670130104 . url: https://onlinelibrary.wiley....

    1967 doi

  26. [34]

    Error estimates for DeepONets: a deep learning framework in infinite dimensions

    S. Lanthaler, S. Mishra, and G. E. Karniadakis. “Error estimates for DeepONets: a deep learning framework in infinite dimensions”. In: Transactions of Mathematics and Its Applications 6.1 (Mar. 2022), tnac001. eprint: https://academic.oup.com/imatrm/article-pdf/6/1/tnac001/427...

    2022 doi

  27. [35]

    Y. Liu. Neural Networks are Integrable . 2024. arXiv: 2310.14394 [math.NA]. url: https://arxiv. org/abs/2310.14394

    2024 arXiv

  28. [36]

    Exponential ReLU neural network approximation rates for point and edge singularities

    C. Marcati, J. A. A. Opschoor, P. C. Petersen, and C. Schwab. “Exponential ReLU neural network approximation rates for point and edge singularities”. In: Found. Comput. Math. 23.3 (2023), pp. 1043–

    2023

  29. [37]

    Marcati and C

    C. Marcati and C. Schwab. Expression Rates of Neural Operators for Linear Elliptic PDEs in Polytopes. (Preprint). 2024. arXiv: 2409.17552 [math.NA]. url: https://arxiv.org/abs/2409.17552

    2024

  30. [38]

    Deep learning in high dimension: ReLU neural network expression for Bayesian PDE inversion

    J. A. A. Opschoor, C. Schwab, and J. Zech. “Deep learning in high dimension: ReLU neural network expression for Bayesian PDE inversion”. In:Optimization and control for partial differential equations— uncertainty quantification, open and closed-loop control, and shape optimiza...

    2022

  31. [39]

    Approximation of 2 d × 2d matrices using tensor decomposition

    I. V. Oseledets. “Approximation of 2 d × 2d matrices using tensor decomposition”. In: SIAM J. Matrix Anal. Appl. 31.4 (2009/10), pp. 2130–2145. url: https://doi.org/10.1137/090757861

    2009 doi

  32. [40]

    Topological properties of the set of functions generated by neural networks of fixed size

    P. Petersen, M. Raslan, and F. Voigtlaender. “Topological properties of the set of functions generated by neural networks of fixed size”. In: Found. Comput. Math. 21.2 (2021), pp. 375–444. url: https: //doi.org/10.1007/s10208-020-09461-0

    2021 doi

  33. [41]

    On the difference between Turing machine time and random-access machine time

    K. Regan. “On the difference between Turing machine time and random-access machine time”. In: Proceedings of ICCI’93: 5th International Conference on Computing and Information . 1993, pp. 36– 40

    1993

  34. [42]

    On quadrature rules for solving Partial Differential Equations using Neural Networks

    J. A. Rivera, J. M. Taylor, ´A. J. Omella, and D. Pardo. “On quadrature rules for solving Partial Differential Equations using Neural Networks”. In: Computer Methods in Applied Mechanics and En- gineering 393 (2022), p. 114710. url: https://www.sciencedirect.com/science/articl...

    2022

  35. [43]

    A probabilistic algorithm for k-SAT and constraint satisfaction problems

    T. Schoning. “A probabilistic algorithm for k-SAT and constraint satisfaction problems”. In: 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) . 1999, pp. 410–414

    1999

  36. [44]

    Deep solution operators for variational inequalities via proximal neural networks

    C. Schwab and A. Stein. “Deep solution operators for variational inequalities via proximal neural networks”. In: Res. Math. Sci. 9.3 (2022), Paper No. 36, 35. url: https://doi.org/10.1007/s40687- 022-00327-1

    2022 doi

  37. [45]

    Schwab, A

    C. Schwab, A. Stein, and J. Zech. Deep Operator Network Approximation Rates for Lipschitz Operators. (to appear in Analysis and Applications (Sing.) 2025). 2023. arXiv: 2307 . 09835 [math.NA]. url: https://arxiv.org/abs/2307.09835

    2025 arXiv

  38. [46]

    Deep learning in high dimension: neural network expression rates for analytic functions in L2(Rd, γd)

    C. Schwab and J. Zech. “Deep learning in high dimension: neural network expression rates for analytic functions in L2(Rd, γd)”. In: SIAM/ASA J. Uncertain. Quantif. 11.1 (2023), pp. 199–234. url: https: //doi.org/10.1137/21M1462738

    2023 doi

  39. [47]

    M. Sipser. Introduction to the Theory of Computation . Third. Boston, MA: Course Technology, 2013

    2013

  40. [48]

    Le probl` eme de Dirichlet pour les ´ equations elliptiques du second ordre ` a coefficients discontinus

    G. Stampacchia. “Le probl` eme de Dirichlet pour les ´ equations elliptiques du second ordre ` a coefficients discontinus”. In: Ann. Inst. Fourier (Grenoble) 15 (1965), pp. 189–258. url: http://www.numdam. org/item?id=AIF_1965__15_1_189_0. 29

    1965

  41. [49]

    On the Complexity of Derivation in Propositional Calculus

    G. S. Tseitin. “On the Complexity of Derivation in Propositional Calculus”. In: Automation of Reason- ing: 2: Classical Papers on Computational Logic 1967–1970 . Ed. by J. H. Siekmann and G. Wrightson. Berlin, Heidelberg: Springer Berlin Heidelberg, 1983, pp. 466–483. url: htt...

    1967

  42. [50]

    Weak adversarial networks for high-dimensional partial differ- ential equations

    Y. Zang, G. Bao, X. Ye, and H. Zhou. “Weak adversarial networks for high-dimensional partial differ- ential equations”. In: Journal of Computational Physics 411 (2020), p. 109409. url: https://www. sciencedirect.com/science/article/pii/S0021999120301832. 30

    2020

  43. [166]

    url: https://doi.org/10.1137/21M146658X

    doi

  44. [375]

    url: https://doi.org/10.1006/jcss.2000.1727

    2000

  45. [1127]

    url: https://doi.org/10.1007/s10208-022-09565-9

    doi

  46. [2024]

    url: https://arxiv.org/abs/2407.02242

    arXiv: 2407.02242 [math.NA]. url: https://arxiv.org/abs/2407.02242

    arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.