{"id":"4dc8359c-d35e-4633-9180-23f9f31d010c","arxiv_id":"2505.17751","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Under SETH, approximating integrals, Poisson solutions, or matrix-vector products for neural network inputs requires runtime at least accuracy^{-1+o(1)}.","lead":"This paper proves that, assuming the widely believed Strong Exponential Time Hypothesis, no fast high-accuracy algorithms exist for integrating neural networks, solving Poisson equations with neural network sources, or multiplying neural-network-encoded matrices. The obstruction holds even when the algorithm receives every network weight, so the difficulty is intrinsic to the representation.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.2's printed error tolerance is exponentially larger than the satisfiable/unsatisfiable gap: the proof asserts an L1 norm of q^d δ^{-n}, but the actual construction gives q^d δ^n, so the PDE lower bound as stated is invalid without correcting this sign.","rationale":"The reader's verdict of CONDITIONAL is appropriate. The quadrature results in Section 3 are carefully constructed and the SETH reduction is sound modulo the reader's noted assumptions. However, the printed Theorem 4.2 contains a sign inconsistency that is not merely cosmetic: the proof asserts an L1 lower bound that exceeds the total mass of a [0,1]-valued function, and the theorem's tolerance is on the wrong side of the separation. The same exponent inconsistency appears in Theorem 5.2. These are concrete, checkable defects that must be corrected by changing δ^{-n} to δ^n (and adjusting the matrix tolerance to the separation computed in the proof). Because the corrections appear to be local and do not undermine the central reduction idea, this does not change the reader's CONDITIONAL verdict; it does mean the paper as submitted should not be relied upon for the PDE and matrix-vector claims as currently stated.","tokens_in":32966,"tokens_out":29752,"duration_ms":273539,"concrete_test":"Recompute the L1 norm in the proof of Theorem 4.2 using the actual construction: set f(x)=F_α((x-(1-q)/2)/q) with 0≤F_α≤1 and F_α=1 on a set of measure δ^n. The change of variables gives ∫_{Ω0} f dx = q^d ∫_{[0,1]^d} F_α(y) dy, hence q^d δ^n ≤ ∥f∥_{L1(Ω0)} ≤ q^d. If this calculation is correct, replace every δ^{-n} in Theorem 4.2 and its proof by δ^n and re-check the final runtime exponent. The test is decisive: with the printed δ^{-n} tolerance, exhibit δ=0.4 and n large and observe that the tolerance exceeds the satisfiable integral upper bound q^d, making a correct decision impossible; after the replacement, the threshold δ^n/2 separates 0 from at least V q^d δ^n.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing defect is an internal inconsistency in the Poisson lower bound. In Theorem 4.2 the algorithm must approximate u_Φ with error below a constant times δ^{-n}. In the proof, for a satisfiable α the source is f(x)=F_α((x-(1-q)/2)/q), where 0≤F_α≤1 and F_α=1 on a set of Lebesgue measure δ^n in [0,1]^d. Therefore ∫_{Ω0} f dx = q^d ∫_{[0,1]^d} F_α(y) dy lies between q^d δ^n and q^d. The proof asserts ∥f∥_{L1(Ω0)} ≥ q^d δ^{-n}, which is impossible for a [0,1]-valued integrand. Lemma 4.1 gives u ≥ V∥f∥_{L1}, so the actual separation between the satisfiable case (u ≈ V q^d δ^n) and the unsatisfiable case (u=0) is of order δ^n, not δ^{-n}. An allowed error of order δ^{-n} is exponentially larger than this gap, so the test 'A(Φ)>threshold' in the proof cannot separate the two cases. The theorem therefore does not establish the claimed lower bound as printed. The same phenomenon occurs in Theorem 5.2, whose displayed tolerance 2^{-(1/2-1+e_sk-δ)n/2} is exponentially larger than the separation 2^{-(3/2-e_sk+δ)n} computed in the proof. Both need the tolerance and the proof's separation factors made consistent before the corresponding hardness claims can be relied upon.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":33311,"tokens_out":9510,"duration_ms":106758,"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":[{"comment":"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.","section":"Theorem 4.2 (Section 4)"},{"comment":"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.","section":"Theorem 5.2 (Section 5)"}],"minor_comments":[{"comment":"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.","section":"Proposition 3.4"},{"comment":"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.","section":"Theorem 5.2"},{"comment":"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.","section":"Remark after Theorem 4.2"},{"comment":"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.","section":"Corollary 4.3"}],"recommendation":"major_revision","confidential_remarks":"The paper is a good fit for a numerical analysis or computational mathematics venue, and the quadrature half of the paper is carefully argued. The main obstacle is that two of the three central theorems, Theorem 4.2 and Theorem 5.2, contain a tolerance-versus-separation mismatch that invalidates those proofs as printed. This looks fixable by correcting the stated tolerances and re-deriving the corollaries, but the correction is load-bearing rather than cosmetic, so the authors should be asked to revise before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper has a genuinely good idea and mostly careful reductions, but two of the three central theorems are stated with error tolerances that are exponentially too large, and the proofs as printed do not go through. I'd send a corrected version to a serious referee, but not this version as is.\n\nWhat's new: Grohs and Voigtlaender showed there is no higher-order quadrature for neural network integrands based only on point evaluations. This paper closes the loophole where the algorithm is allowed to read all weights, and extends the hardness to Poisson right-hand sides and matrix-vector products. The reduction machinery is well thought out: the CNF-to-network construction, the orthant-visiting curve, and the sparsification setup are all handled with care. The sharpness section, with fast quadrature for one-layer networks and the QMC experiments, is a real plus and shows the authors are thinking about the whole picture.\n\nWhere it falls down: the proof of Theorem 4.2 asserts ||f||_{L1(Ω0)} ≥ q^d δ^{-n}. That is impossible: f is a [0,1]-valued function, so its L1 norm on Ω0 is at most q^d, and the actual separation for a satisfiable formula is on the order of q^d δ^n. The stated error tolerance δ^{-n} is exponentially larger than the gap, so the decision threshold in the proof cannot separate satisfiable from unsatisfiable instances. The same problem appears in Theorem 5.2: the printed tolerance 2^{-(1/2-1+e_sk-δ)n/2} is exponentially larger than the separation 2^{-(3/2-e_sk+δ)n} that the proof actually computes. These are not harmless typos — the theorems as stated claim lower bounds the proofs do not establish. The likely fix is to replace δ^{-n} with δ^n and set the tolerance to half the true separation; if that works, the qualitative 'no higher-order' conclusions survive. But I don't want to referee a version with the signs flipped.\n\nMinor points: Proposition 3.4's Q_α really does have measure δ^n on the cube, because the domain clips the L∞ ball at the corner; the worry about (2δ)^n is wrong. Theorem 4.2 divides by d−2 without excluding d=2. Lemma 5.1 writes S#_k(2n) where it likely means S#_k(n). These are cosmetic next to the main issue. The numerical experiments are clearly labeled as evidence, not proof, so they don't affect the core claims.\n\nBottom line: the central reduction strategy is sound and the paper is a real contribution to the theory-to-practice gap literature. But two of the three main theorems are currently wrong as printed. My recommendation: ask the authors to fix the exponent errors and resubmit; the corrected version deserves serious refereeing.","headline":"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.","tokens_in":33842,"tokens_out":8907,"would_cite":true,"duration_ms":67983,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65D30","65Y20","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["neural network quadrature","SETH","lower bounds","Poisson equation","matrix-vector product","quasi-Monte Carlo","ReLU networks","high-dimensional integration"],"falsifier":"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.","tokens_in":32745,"feed_emoji":"🧮","tokens_out":10639,"duration_ms":74584,"temperature":0.7,"pith_summary":"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.","feed_headline":"Under SETH, neural-network math is stuck at first order","feed_subtitle":"Even with full weights in hand, integrals, Poisson solves, and matrix-vector products on network inputs all hit the same speed limit.","key_machinery":"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}$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces the Strong Exponential Time Hypothesis, the conjecture that drives all the lower bounds.","marker":"[5]"},{"why":"Supplies the sparsification lemma that reduces SETH to formulas with a linear number of clauses, used in Lemma 2.2 and in every reduction.","marker":"[30]"},{"why":"Prior result showing no higher-order quadrature from point evaluations alone; this paper extends the impossibility to algorithms with full weight access.","marker":"[25]"},{"why":"Tseytin transformation, used to convert arbitrary Boolean formulas into CNF with linear length for the network encoding.","marker":"[49]"},{"why":"Schauder interior regularity estimates that frame the Poisson problem setting in Section 4.","marker":"[19]"},{"why":"Weak maximum principle for $H^1$ functions, used in Lemma 4.1 to lower-bound the Green's function on an interior subdomain.","marker":"[48]"},{"why":"Borwein integrals, which give the explicit fast one-layer quadrature method on the hypercube in Section 6.5.","marker":"[4]"},{"why":"Provides the explicit hyperplane-section volume of the cube used in the fast one-layer hypercube quadrature formula.","marker":"[2]"}],"fun_headline_variants":["SETH rules out fast higher-order NN math algorithms","Even with full weights, NN integrals, Poisson, matvec stay first-order","Zero-function check is the bottleneck for NN computation speed","No higher-order speedups for NN math under SETH, even with weights","Three NN tasks hit first-order wall under SETH"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["SETH rules out fast higher-order NN math algorithms","Even with full weights, NN integrals, Poisson, matvec stay first-order","Zero-function check is the bottleneck for NN computation speed","No higher-order speedups for NN math under SETH, even with weights","Three NN tasks hit first-order wall under SETH"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000332,"raw_usage":{"total_tokens":1857,"prompt_tokens":964,"completion_tokens":893,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":580,"completion_tokens_details":{"reasoning_tokens":807}},"tokens_in":580,"tokens_out":893,"duration_ms":10548,"temperature":1.0,"reasoning_tokens":807,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:41:54.188868+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"The complexity of satisfiability of small depth circuits","cited_arxiv_id":null,"evidence_quote":"Introduces the Strong Exponential Time Hypothesis, the conjecture that drives all the lower bounds."},{"cited_title":"Which Problems Have Strongly Exponential Complex- ity?","cited_arxiv_id":null,"evidence_quote":"Supplies the sparsification lemma that reduces SETH to formulas with a linear number of clauses, used in Lemma 2.2 and in every reduction."},{"cited_title":"Proof of the theory-to-practice gap in deep learning via sampling complexity bounds for neural network approximation spaces","cited_arxiv_id":null,"evidence_quote":"Prior result showing no higher-order quadrature from point evaluations alone; this paper extends the impossibility to algorithms with full weight access."},{"cited_title":"On the Complexity of Derivation in Propositional Calculus","cited_arxiv_id":null,"evidence_quote":"Tseytin transformation, used to convert arbitrary Boolean formulas into CNF with linear length for the network encoding."},{"cited_title":"Gilbarg and N","cited_arxiv_id":null,"evidence_quote":"Schauder interior regularity estimates that frame the Poisson problem setting in Section 4."},{"cited_title":"Le probl` eme de Dirichlet pour les ´ equations elliptiques du second ordre ` a coefficients discontinus","cited_arxiv_id":null,"evidence_quote":"Weak maximum principle for $H^1$ functions, used in Lemma 4.1 to lower-bound the Green's function on an interior subdomain."},{"cited_title":"Some remarkable properties of sinc and related integrals","cited_arxiv_id":null,"evidence_quote":"Borwein integrals, which give the explicit fast one-layer quadrature method on the hypercube in Section 6.5."},{"cited_title":"Volumes of sections of cubes and related problems","cited_arxiv_id":null,"evidence_quote":"Provides the explicit hyperplane-section volume of the cube used in the fast one-layer hypercube quadrature formula."}],"review_version":1}