{"id":"c314ca10-919b-4ff9-af3f-8d9f1c4dae8e","arxiv_id":"2505.22410","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Product-structured convolutions over a domain of size N can be computed in O(N^{2ω/3}) ≈ O(N^{1.582}) arithmetic operations, where ω is the matrix multiplication exponent.","lead":"This paper shows that convolutions over product domains, with a fixed coordinatewise combination rule, can be computed in about |D|^1.58 time by embedding them into fast matrix multiplication. It also reformulates known join-node algorithms in tensor-rank language and connects them to Strassen's asymptotic rank conjecture.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.1's proof as printed misaligns coordinates: U,V are built from u_{a,i,ℓ} and v_{c,k,j}, yet φ produces e_{f(a,c),f(ℓ,j),f(i,k)}, which equals the f^3-convolution only after relabeling inputs to (a,ℓ,i) and (c,j,k).","rationale":"The central claim of the paper, Theorem 2.6, depends entirely on Lemma 3.1. The reader's weakest assumption identifies the exact step I would also isolate: the unstated coordinate permutation in Lemma 3.1. In the proof as printed, U and V are formed from u_{a,i,ℓ} and v_{c,k,j}, while the final projection φ yields e_{f(a,c), f(ℓ,j), f(i,k)}; this is the f^3-convolution only after permuting the input coordinate order. This is a genuine flaw in the written proof, and since the proof of Theorem 2.6 is otherwise a direct application of Lemma 3.1, it is load-bearing for the paper's main algorithmic result. However, the flaw is clearly repairable by permuting the indices in the definitions of U and V before constructing them; arbitrary vectors u and v can be relabeled freely. I separately checked the remaining steps of the proof of Theorem 2.6: padding to n=ceil(k/3) with B=D^n works, and the matrix multiplication cost (|D|^{2n})^ω = |D|^{2ωn} dominates the O(|D|^{4n}) construction cost because 2ω>4, so the asymptotic bound is unaffected (the printed '|D|^{2n}' in the cost line appears to be a typo for '|D|^{4n}', but it does not change the conclusion). The Yates algorithm proof in Section 4 has a separate indexing typo (c_{ι(i)} rather than c_t in the second-stage recurrence), but that concerns Theorem 2.5 and the conditional asymptotic-rank consequences, not the headline Theorem 2.6. Overall, the paper needs a corrected Lemma 3.1 before the main proof is rigorous, but the underlying result appears sound; this matches the reader's CONDITIONAL verdict.","tokens_in":11922,"tokens_out":22486,"duration_ms":230658,"concrete_test":"Re-derive Lemma 3.1 with coordinates named consistently: define U_{a,b;i,j}=sum_{ℓ:f(ℓ,j)=b} u_{a,ℓ,i} and V_{i,j;c,d}=sum_{k:f(i,k)=d} v_{c,j,k}. Expand φ(U·V) and verify that the coefficient of e_{f(a,c),f(ℓ,j),f(i,k)} equals u_{a,ℓ,i} v_{c,j,k}. Then substitute (i1,i2,i3)=(a,ℓ,i) and (j1,j2,j3)=(c,j,k) and confirm the result is the f^3-convolution for every partial f and every u,v∈Q^{D^3}. If the identity holds, the central theorem survives the concern.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 2.6 rests on Lemma 3.1, and the displayed construction in Lemma 3.1 does not, as written, compute the f^3-convolution. With U_{a,b;i,j}=sum_{ℓ:f(ℓ,j)=b} u_{a,i,ℓ} and V_{i,j;c,d}=sum_{k:f(i,k)=d} v_{c,k,j}, the expansion gives φ(U·V)=sum u_{a,i,ℓ} v_{c,k,j} e_{f(a,c), f(ℓ,j), f(i,k)}. The f^3-convolution, however, has output index (f(i1,j1), f(i2,j2), f(i3,j3)). Matching the three coordinates requires taking (i1,i2,i3)=(a,ℓ,i) and (j1,j2,j3)=(c,j,k), while the coefficient shown is u_{a,i,ℓ}v_{c,k,j}, not u_{a,ℓ,i}v_{c,j,k}. Since u and v are arbitrary dense vectors, this is a genuine gap in the proof as printed. It is repairable: redefine U by summing u_{a,ℓ,i} and V by summing v_{c,j,k}, with the same sums over ℓ and k. Then the matrix product followed by φ is exactly the f^3-convolution, and the O(|D|^{2ω/3 k}) bound follows from multiplying |D|^{2n}×|D|^{2n} matrices with n≈k/3. The issue is thus a local but load-bearing coordinate permutation, not a counterexample to the theorem.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the computation of convolutions over product domains D = B^k defined by a coordinate-wise function h^k. It reformulates such convolutions as bilinear maps and rank decompositions, proves a Yates-style algorithm (Theorem 2.5), and then proves a Strassen-style embedding theorem (Theorem 2.6) showing that any product-structured convolution can be reduced to fast matrix multiplication, yielding O^*(|B|^{2ω/3·k}) ≈ O(|D|^{1.582k}) time. It further observes that the asymptotic rank conjecture would give quasi-linear O(|D|^{k+o(k)}) time for all product-type convolutions. The paper is explicitly expository, aiming to give a self-contained account for an algorithms audience and to show that low-rank tensor decompositions can replace some of the ad-hoc state-encoding tricks in treewidth DP algorithms.","tokens_in":12251,"tokens_out":9594,"duration_ms":102220,"significance":"If the proofs are correct, the paper provides a clean unifying framework for join-node convolutions in treewidth DP and improves on the best known general bounds for product-domain convolutions, matching the state of the art from algebraic complexity theory. The conditional quasi-linear time consequence is valuable and connects to active research on the asymptotic rank conjecture. The paper's strengths are its didactic framing, explicit coordinate notation, and the clear separation between the unconditional matrix-multiplication result and the conditional asymptotic-rank result. However, the main algorithmic theorem is not new—it is Strassen's embedding—and the paper's contribution is primarily expository; the central proof has a coordinate-alignment error that must be repaired.","major_comments":[{"comment":"As printed, the construction does not compute the f^3-convolution. With U_{a,b;i,j} = Σ_{ℓ:f(ℓ,j)=b} u_{a,i,ℓ} and V_{i,j;c,d} = Σ_{k:f(i,k)=d} v_{c,k,j}, the expansion gives φ(U·V) = Σ_{a,c,i,j,k,ℓ} u_{a,i,ℓ} v_{c,k,j} e_{f(a,c), f(ℓ,j), f(i,k)}. Matching this to the f^3-convolution output (f(i1,j1), f(i2,j2), f(i3,j3)) requires (i1,i2,i3) = (a,ℓ,i) and (j1,j2,j3) = (c,j,k), which yields coefficient u_{i1,i3,i2} v_{j1,j3,j2} rather than the required u_{i1,i2,i3} v_{j1,j2,j3}. The map φ therefore computes a coordinate-permuted version of the desired convolution. This is repairable: define U by summing u_{a,ℓ,i} and V by summing v_{c,j,k}. Because Theorem 2.6 is proved by applying Lemma 3.1, this correction is load-bearing and must be made explicit.","section":"Section 3, Lemma 3.1"}],"minor_comments":[{"comment":"The reduction overhead is stated as O(|D|^{2n}), but Lemma 3.1 gives O(|D|^{4n}) for building U, V, and φ. The final bound is unaffected because the matrix multiplication term O(|D|^{2ω n}) dominates for ω > 2, but the displayed equality should be corrected to O(|D|^{2ω n} + |D|^{4n}) = O(|D|^{2ω n}).","section":"Section 3, proof of Theorem 2.6"},{"comment":"The abstract writes O(|D|^{1.582}) while the theorem statement gives O(|D|^{1.582k}); the exponent k should appear in the abstract as well.","section":"Abstract and Theorem 2.6"},{"comment":"The vector f_ι is described as having dimension k−i; from the recursion it must have dimension |B|^{k−i}. Also, the sentence 'At layer k, we interpret (x_k ... x_{k−1}) as empty' contains an obvious off-by-one typo.","section":"Section 4, proof of Theorem 2.5"},{"comment":"The notation D is overloaded: earlier D = B^k is the product domain, while in Theorem 2.6 D denotes the base domain and the product is D^k. This ambiguity should be resolved, for instance by renaming the base domain to B throughout.","section":"Theorems 2.5 and 2.6"}],"recommendation":"major_revision","confidential_remarks":"The central algorithmic content of Theorem 2.6 is a known Strassen embedding, and the paper's novelty is largely expository. If the venue values self-contained survey-style contributions with a new perspective, the paper can be suitable after the coordinate-alignment error in Lemma 3.1 is fixed and the proof details are cleaned up. The authors should also verify that the proof of Theorem 2.7 is written so that the quasi-linear conclusion is transparent; as currently worded, the invocation of Theorem 2.5 on constant-sized powers is terse."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper's main theorem—O*(|D|^{2ω/3·k}) for product-structured convolutions—is correct and worth knowing, but the printed proof of Lemma 3.1 has a coordinate-alignment gap that needs fixing before the note can be trusted as written.\n\nWhat's genuinely new: the paper gives a clean, self-contained multilinear algebra framework for these convolutions, and it makes explicit that Strassen's 1988 tensor embedding yields a generic upper bound that improves the previous c^k |B|^{2k} bound of Esmer et al. The Yates algorithm proof is also a welcome concrete exposition. The paper does real expository work: an algorithms audience can follow the argument without algebraic geometry.\n\nThe soft spots are concentrated in Section 3. The stress-test note is right: as printed, the matrices U and V in Lemma 3.1 do not compute the f^3-convolution. U is built from u_{a,i,ℓ} and V from v_{c,k,j}, but the expansion gives e_{f(a,c), f(ℓ,j), f(i,k)}, which only matches the desired output index (f(i1,j1), f(i2,j2), f(i3,j3)) after a relabeling that is never stated. Repairable by swapping indices in the definitions of U and V, but it's load-bearing: the proof as written is a genuine gap, not a typo. The proof of Theorem 2.6 also misstates the overhead as O(|D|^{2n}) when it is O(|D|^{4n}); that doesn't change the asymptotics since matrix multiplication dominates, but it should be corrected. The Yates recurrence has an indexing typo and the XOR rank decomposition is missing a scalar; both are minor.\n\nOne broader overstatement: the introduction claims that optimal state semantics can be 'derived mechanically' via low-rank decompositions, but no concrete derivation is given. It's a research agenda, not a result, and the paper should say so. The asymptotic rank conjecture discussion is clearly separated, so no circularity burden.\n\nBottom line: the central claim holds up and the presentation is mostly accessible. This is a note for the parameterized-algorithms and treewidth-DP crowd; they will want to know this bound. I'd like to see a revised version with the Lemma 3.1 alignment fixed and the cost displays corrected. The paper deserves a serious referee; after those fixes I'd take it.","headline":"Correct core bound, but Lemma 3.1's proof is misaligned as printed and needs a fix before publication.","tokens_in":12810,"tokens_out":2744,"would_cite":true,"duration_ms":26886,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Product-structured convolutions reduce to fast matrix multiplication, yielding an O(N^1.582) algorithm.","keywords":["generalized convolutions","product domains","fast matrix multiplication","tensor rank","Yates' algorithm","asymptotic rank conjecture","tree decompositions","split-and-list"],"falsifier":"Compute the two sides of Lemma 3.1 for a small base domain, for example $B=\\{0,1\\}$ with $h$ the OR function and $k=3$: build $u,v\\in\\mathbb{Q}^{B^3}$ with random entries, compute $\\phi(U\\cdot V)$ exactly as the proof defines $U$ and $V$, and compare it entrywise with the naive $f^3$-convolution after reordering the output coordinates according to the definition of $\\circledast_{f^3}$. A mismatch on any entry shows the proof requires an explicit coordinate permutation; equality on all $|B|^3$ entries confirms the reduction.","tokens_in":11649,"feed_emoji":"🔢","tokens_out":12623,"duration_ms":122407,"temperature":0.7,"pith_summary":"Convolution over a product domain $B^k$, where the combining function applies a fixed partial map $h$ coordinate-wise, sits at the heart of join-node computations in treewidth-based algorithms. This paper's central claim is that such convolutions are far cheaper than the naive quadratic bound: they can be embedded into multiplication of square matrices of size $|B|^{2\\lceil k/3\\rceil}$, and with the current matrix multiplication exponent $\\omega<2.372$ this gives $O(|B|^{2\\omega/3\\cdot k}) = O(|B|^{1.582k})$ operations. That improves the best previous general upper bound of the form $c^k |B|^{2k}$ with $c<1$. The paper also shows that when the base function has a rank-$r$ decomposition, Yates' algorithm evaluates the lifted decomposition in $O(r^k k)$ time, which lets known $O^*(3^t)$ and $O^*(2^t)$ algorithms for dominating sets and perfect matchings be recovered mechanically instead of by problem-specific cleverness. If Strassen's asymptotic rank conjecture holds, the same framework would yield quasi-linear $|B|^{k+o(k)}$ time for all product-type convolutions.","feed_headline":"Product-domain convolutions run in O(N^1.582) time","feed_subtitle":"A bilinear split-and-list proof embeds each convolution into fast matrix multiplication, beating c^k|B|^{2k} bounds.","key_machinery":"Two mechanisms carry the argument. The first is the bilinear split-and-list embedding of Lemma 3.1: from $u,v\\in\\mathbb{Q}^{D^3}$ one forms $U_{a,b;i,j}=\\sum_{\\ell:f(\\ell,j)=b}u_{a,i,\\ell}$ and $V_{i,j;c,d}=\\sum_{k:f(i,k)=d}v_{c,k,j}$, and then the linear projection $\\phi(e_{a,b;c,d})=e_{f(a,c),b,d}$ satisfies $u\\circledast_{f^3}v=\\phi(U\\cdot V)$. This reduces the third power of any convolution to multiplying two $D^2\\times D^2$ matrices, and applying it blockwise over the $k$ coordinates of $B^k$ is what yields the $|B|^{2\\omega/3\\cdot k}$ bound. The second is Yates' algorithm: given a rank-$r$ decomposition of the base function $h$, the Kronecker product decomposition (Lemma 2.3) lifts it to rank at most $r^k$ for $h^k$, and the lifted inner products can be evaluated by an $r$-ary tree in $O(r^k k)$ arithmetic operations.","core_discovery":"The discovery is a uniform bilinear 'split-and-list' embedding. For any partial function $f:D\\times D\\to D$, the convolution associated with the third power $f^3$ can be rewritten as $\\phi(U\\cdot V)$, where $U$ and $V$ are $D^2\\times D^2$ matrices whose entries are linear combinations of the input vectors, and $\\phi$ is a linear projection. Applying this embedding blockwise to the $k$ coordinates of a product-structured convolution over $B^k$ turns the whole computation into a single matrix product of size $|B|^{2\\lceil k/3\\rceil}$, so fast matrix multiplication yields $O(|B|^{2\\omega/3\\cdot k})$ operations. The same language gives a clean proof of Yates' algorithm: a rank-$r$ decomposition of the base function lifts via Kronecker products to a rank at most $r^k$ decomposition of $h^k$, and the lifted inner products can be collected in $O(r^k k)$ time. Together these results establish that product-structured convolutions, for arbitrary partial base functions, run in $O(N^{2\\omega/3})=O(N^{1.582})$ time on a domain of size $N=|B|^k$.","pith_inferences":["The unstated coordinate permutation in Lemma 3.1 appears repairable by choosing a consistent flattening convention for $D^3$, but making it explicit would be necessary before the reduction can be implemented exactly as written.","A natural next test is whether the $|B|^{2\\omega/3\\cdot k}$ bound is tight for product-structured convolutions or whether rank lower bounds force a larger exponent; the paper does not address lower bounds.","Because the split-and-list embedding recasts join-node computation as matrix multiplication, optimized matrix libraries could bring the asymptotic speed-up into practice for the small domains used in treewidth algorithms; this is an empirical extension the paper does not test."],"forward_implications":["Every convolution on a product domain $B^k$ with a fixed base function $h$—covering product, XOR convolution, subset convolution, and the dominating-set join—inherits the $O(|B|^{2\\omega/3\\cdot k})$ bound, independent of the semantic meaning of the states.","The reduction of Lemma 3.1 works for every partial function $f$, not only product-structured ones, so any future fast matrix multiplication algorithm automatically improves all such convolutions by the same exponent factor.","Yates' algorithm turns a rank bound for the base function into a concrete running time $O(r^k k)$; consequently, finding rank-$r$ decompositions for the base functions of classical problems reproduces the known $O(3^t)$ dominating-set and $O(2^t)$ perfect-matching algorithms in a mechanical way.","Under Strassen's asymptotic rank conjecture, Theorem 2.7 gives $O(|D|^{k+o(k)})$ time, meaning all product-type convolutions become quasi-linear in the size of the product domain $|D|^k$."],"supporting_citations":[{"why":"Supplies the split-and-list proof that embeds the third power of a convolution into multiplication of $D^2\\times D^2$ matrices; this is the core of Theorem 2.6.","marker":"[12]"},{"why":"Yates' algorithm is the subject of Theorem 2.5: it evaluates lifted rank-$r$ decompositions in $O(r^k k)$ time.","marker":"[18]"},{"why":"The join-node convolution for dominating sets whose $O^*(3^t)$ algorithm the paper explains mechanically via low-rank decompositions.","marker":"[16]"},{"why":"The previous general upper bound $c^k|B|^{2k}$ for $c<1$ that Theorem 2.6 improves upon.","marker":"[6]"},{"why":"Source of Strassen's asymptotic rank conjecture that Theorem 2.7 builds on to derive quasi-linear time.","marker":"[13]"},{"why":"Introduces fast subset convolution, the running example whose rank structure and $O(2^k k)$ implementation the paper's framework subsumes.","marker":"[3]"},{"why":"Recent work connecting the asymptotic rank conjecture to fine-grained algorithms, cited as context for the conjecture's algorithmic consequences.","marker":"[4]"}],"fun_headline_variants":["Convolutions in O(N^1.582) via fast matrix multiplication","Split-and-list method yields faster product-domain convolutions","New upper bound: O(N^1.582) for product-structured convolutions","Multilinear algebra improves convolution runtime to O(N^1.582)"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The running-time bound rests on the unstated coordinate permutation inside Lemma 3.1: the indices of $u$ and $v$ must be relabeled as $(a,i,\\ell)\\mapsto(a,\\ell,i)$ and $(c,k,j)\\mapsto(c,j,k)$ for the projected matrix product to equal the $f^3$-convolution, and if that alignment is wrong the claimed reduction collapses.","fun_headline_variants_meta":{"raw":{"variants":["Convolutions in O(N^1.582) via fast matrix multiplication","Split-and-list method yields faster product-domain convolutions","New upper bound: O(N^1.582) for product-structured convolutions","Multilinear algebra improves convolution runtime to O(N^1.582)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000762,"raw_usage":{"total_tokens":3503,"prompt_tokens":1187,"completion_tokens":2316,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":803,"completion_tokens_details":{"reasoning_tokens":2247}},"tokens_in":803,"tokens_out":2316,"duration_ms":17636,"temperature":1.0,"reasoning_tokens":2247,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:10:51.742735+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the two sides of Lemma 3.1 for a small base domain, for example $B=\\{0,1\\}$ with $h$ the OR function and $k=3$: build $u,v\\in\\mathbb{Q}^{B^3}$ with random entries, compute $\\phi(U\\cdot V)$ exactly as the proof defines $U$ and $V$, and compare it entrywise with the naive $f^3$-convolution after reordering the output coordinates according to the definition of $\\circledast_{f^3}$. A mismatch on any entry shows the proof requires an explicit coordinate permutation; equality on all $|B|^3$ entries confirms the reduction.","supporting_citations":[{"cited_title":"Strassen","cited_arxiv_id":null,"evidence_quote":"Supplies the split-and-list proof that embeds the third power of a convolution into multiplication of $D^2\\times D^2$ matrices; this is the core of Theorem 2.6."},{"cited_title":"The design and analysis of factorial experiments","cited_arxiv_id":null,"evidence_quote":"Yates' algorithm is the subject of Theorem 2.5: it evaluates lifted rank-$r$ decompositions in $O(r^k k)$ time."},{"cited_title":"Computing generalized convolutions faster than brute force.Algorithmica, 86(1):334–366, 2024.doi:10.1007/S00453-023-01176-2","cited_arxiv_id":null,"evidence_quote":"The previous general upper bound $c^k|B|^{2k}$ for $c<1$ that Theorem 2.6 improves upon."},{"cited_title":"Strassen.Algebra and Complexity, pages 429–446","cited_arxiv_id":null,"evidence_quote":"Source of Strassen's asymptotic rank conjecture that Theorem 2.7 builds on to derive quasi-linear time."}],"review_version":1}