{"id":"a51de620-d497-48f1-a76d-ec1df0e531c6","arxiv_id":"2507.19259","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"For random Gaussian matrices, no online algorithm can beat the incremental greedy procedure's dense-submatrix value, with tight factor 4/(3√2), and 2√p/(p+1) for p-tensors.","lead":"This paper proves that a simple greedy algorithm is optimal among online algorithms for finding the densest submatrix of a random Gaussian matrix, with a tight factor of about 0.943 of the true optimum. It extends the same tight bound to higher-order tensors.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Branching-OGP proof asserts without justification that online outputs on correlated leaves form a forbidden tree with disjoint per-level coordinate sets; trivial online algorithms violate this, leaving Theorem 2.3 unproved.","rationale":"The reader's weakest assumption identifies exactly the load-bearing gap: the conversion of leaf successes into a forbidden structure with disjoint per-level coordinate sets is asserted without proof and is not implied by the online definition. My stress-test confirms this is not merely a missing detail: a trivial online algorithm produces identical coordinate sets across branches on a positive-probability success event, so the asserted implication is false as stated. Because Proposition 4.2 depends critically on disjointness for its variance computation and enumeration, the contradiction in Theorem 2.3 collapses unless a new argument is supplied. I found no other issue that changes the overall assessment: the positive-side Theorem 2.1 appears coherent, the constants are derived rather than fitted, and the branching-OGP methodology is a plausible route. The appropriate disposition is therefore the reader's existing CONDITIONAL verdict: the paper should be accepted only after the missing derivation or a replacement argument is provided. My concern does not move the verdict, so I recommend UNCHANGED.","tokens_in":10173,"tokens_out":12825,"duration_ms":143144,"concrete_test":"Set p=2, N=2, D=2, α_1=1/2, and let A be the online algorithm that always outputs rows and columns {1,...,k}. For the corresponding (T,α)-correlated instance, condition on the positive-probability event that every leaf's first k×k submatrix has average at least (4/3+ε)√(2 log n/k). Then Suc_A(Gv) holds for all leaves, but the natural assignment of A_v^(s) to segments of the common output gives A_v^(1)=A_v^(2)={k/2+1,...,k} for both depth-2 vertices, violating Definition 4.1. Verify this counterexample directly, then check whether any argument in the paper repairs (21) without the disjointness assumption; if not, the proof of Theorem 2.3 requires a new step, such as a combinatorial lemma extracting a disjoint subfamily of leaves, before the contradiction is valid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The upper bound in Theorem 2.3 rests on the sentence just before (27): if Suc_A(Gv) holds for all leaves of a (T,α)-correlated instance, then '{A(Gv)} forms forbidden structure according to Definition 2.2' (surely meaning Definition 4.1). Definition 4.1 requires, for each mode s, that the coordinate sets A_v^(s) be disjoint across distinct vertices at every depth. Nothing in the online definition, Definition 2.2, enforces this. The online constraint fixes prefixes within a single run on one input; it says nothing about outputs on different leaves of the correlated instance. Two leaves sharing an ancestor see identical entries up to α_j n and therefore have identical prefixes, but their later coordinate choices are made from independent suffix entries and can coincide arbitrarily. Indeed, the trivial online algorithm that always outputs rows and columns {1,...,k} gives identical A_v^(s) for all vertices at depth 2. On the positive-probability event that the first k×k submatrix of every leaf tensor has average above threshold, Suc_A(Gv) holds for all leaves while the required disjointness fails. Proposition 4.2's Gaussian tail estimate (22) uses disjointness to compute the variance as D^{ℓ-1}(α_ℓ^p−α_{ℓ-1}^p)k^p in (21); without disjointness the same tensor entry can contribute to several E_v, and the estimate (23) has no justification. Hence the central contradiction p_suc^{|L|} ≤ exp(−ck log n) is not established as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the problem of finding a k×⋯×k subtensor of maximum average value in an n^{⊗p} tensor with i.i.d. standard Gaussian entries. It proves a positive result, Theorem 2.1, showing that a generalized incremental greedy procedure (IGP) achieves average value asymptotic to (2p/(p+1))√(2 log n / k^{p−1}) with high probability when k=exp(o(log n)). It then claims a matching upper bound, Theorem 2.3, for the class of online algorithms (OLA), defined by a causal blockwise information constraint in Definition 2.2. The upper bound is established via a branching overlap gap property (OGP): a tree-indexed family of subtensors with large sums is shown to be exponentially unlikely (Proposition 4.2), and success of an OLA on a correlated tree instance is asserted to produce such a forbidden family. The final step, appearing just before Eq. (27), is the crucial reduction from OLA outputs to the forbidden structure of Definition 4.1.","tokens_in":10495,"tokens_out":22424,"duration_ms":222662,"significance":"If valid, Theorem 2.3 would give a sharp constant-factor characterization of the approximability of dense submatrix/subtensor search within a natural algorithmic class, and would showcase the branching-OGP method in a new setting. The positive side is a clean, self-contained Gaussian-tail argument, and the abstract forbidden-structure probability bound in Proposition 4.2 is coherent for the abstract tree family considered there. The weakness is the reduction from OLA to forbidden structures in Section 4.2, which is the load-bearing step for Theorem 2.3 and is, as written, not justified. The claimed optimality of IGP within OLA is therefore not established by this manuscript.","major_comments":[{"comment":"The assertion that if Suc_A(G^v) holds for all leaves v then {A(G^v)}_{v∈L} forms a forbidden structure according to Definition 4.1 is not a consequence of the online definition. Definition 4.1 requires, for each mode s, the sets A_v^{(s)} to be pairwise disjoint over distinct vertices v, v'. Definition 2.2 constrains each single run causally: the layer chosen at step s may depend only on entries indexed by coordinates at most ⌊s/k n⌋ and on the previous layers of the same run. It imposes no relation between the indices chosen in different runs on different leaves of a (T,α)-correlated instance. For example, the constant algorithm that always outputs the subtensor indexed by {1,…,k} in every mode belongs to OLA. On the event that this fixed subtensor has sum at least (2p/(p+1)+ε)D_n for every leaf G^v, Suc_A(G^v) holds for all v, but the fixed output supplies only k coordinate indices per mode, whereas the forbidden structure would require disjoint sets A_v^{(s)} whose total size across the tree is k∑_{ℓ=1}^N D^{ℓ−1}(α_ℓ−α_{ℓ−1}) > k for D>1. Thus the disjointness condition cannot be met, and Proposition 4.2 cannot be invoked. Consequently the bound p_suc^{|L|} ≤ exp(−ck log n) in Eq. (27) does not follow.","section":"Section 4.2, sentence before Eq. (27)"},{"comment":"The proof does not specify how the k sequential layers of an OLA algorithm are mapped to the N layers of the tree in Definition 4.1. Definition 2.2 has a layer for each step r=1,…,k, with information thresholds ⌊r/k n⌋, while Definition 4.1 uses an arbitrary partition 0=α_0<α_1<⋯<α_N=1 and requires sets A_v^{(s)} of sizes (α_j−α_{j−1})k for each tree vertex at depth j. The text never defines the sets A_v^{(s)} from the online algorithm's output, nor proves the size identity, nor explains how the thresholds align with the α_j, for instance through integers s_j≈α_j k. As written, the reduction from OLA to a forbidden structure is not a well-defined map, so the contradiction in Theorem 2.3 is not rigorously formulated.","section":"Section 4.2 / Definition 2.2"},{"comment":"The Gaussian tail computation in Proposition 4.2 is valid only for the abstract forbidden structure where the entry sets E_v are disjoint across vertices at each depth. This is where the variance D^{ℓ−1}(α_ℓ^p−α_{ℓ−1}^p)k^p in Eq. (21) comes from, and it is used to justify the exponent in Eq. (22). Because the reduction in Theorem 2.3 cannot guarantee disjointness of the sets A_v^{(s)} for OLA outputs, the estimate exp(−ck log n) in Eq. (12) does not transfer to the event that all leaves of the correlated instance succeed. If the sets overlap, the same Gaussian entries contribute to multiple E_v, and the variance in Eq. (21) is no longer correct, so the tail bound in Eq. (22) has no justification in the context of Theorem 2.3.","section":"Section 4.1, Eq. (21)–(22)"}],"minor_comments":[{"comment":"The text says 'forms forbidden structure according to Definition 2.2'; this should be Definition 4.1.","section":"Proof of Theorem 2.3, just before Eq. (27)"},{"comment":"The index i is used both for the level ℓ and as a summation index; for example, 'α_i−1' should be 'α_{ℓ−1}' and 'α_i' should be 'α_ℓ' in the sums over j.","section":"Eq. (17) and Eq. (22)"},{"comment":"Writing o_k(1) inside the probability event is nonstandard, since the event depends on k in a way that is not monotone. It would be cleaner to state that for every ε>0 there is k_0 such that for all k≥k_0, P[Avg(A(G)) ≥ (2p/(p+1)+ε)√(2 log n / k^{p−1})] ≤ exp(−c k log n).","section":"Theorem 2.3 statement"},{"comment":"The statement says 'for all 1≤r≤k, 1≤s≤p', but for r=1 some variances r^{s−1}(r−1)^{p−s} vanish when p>1 and s>1; the lemma should explicitly restrict to 2≤r≤k or define the quantities only for r≥2.","section":"Lemma 3.1"},{"comment":"The partition of [n] into k+1 disjoint sets is only partially described: the first k sets P_{i,n} are defined, but the (k+1)-st set is not. Since only P_{1,n},…,P_{k,n} are used, this is harmless but should be clarified.","section":"Eq. (5)"}],"recommendation":"reject","confidential_remarks":"The central upper-bound theorem is unproved because the branching-OGP reduction contains a false implication: success of an online algorithm on correlated leaves does not produce the disjoint forbidden structure required by Proposition 4.2. This is not a missing technical lemma but a structural mismatch between Definition 2.2 and Definition 4.1, and the constant-algorithm counterexample shows the asserted implication is false for the class OLA as defined. The positive result and the abstract OGP bound are interesting, but the main claim of the paper cannot be salvaged by minor edits within the current framework."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear Colleague,\n\nThe bottom line: the positive half is fine, but the negative half—the paper's main claim—has a gap that looks load-bearing. The assertion just before (27) that the outputs A(G_v) on correlated leaves form a forbidden structure in the sense of Definition 4.1 is not justified, and as stated it is false: nothing in the online definition prevents two leaves from outputting the same index layers. The trivial online algorithm that always outputs rows and columns {1,...,k} gives identical A_v^(s) for all vertices at the same depth, so the disjointness required in Proposition 4.2's variance computation fails. The Gaussian tail bound (23) therefore has no basis for that algorithm, and the contradiction leading to (27) does not go through.\n\nWhat is genuinely good: Theorem 2.1 (the IGP analysis for p-tensors) is a clean Gaussian-tail argument and seems correct. The branching-OGP framework is a natural fit here, and the constants 4/(3√2) and 2√p/(p+1) are derived rather than fitted. The paper is honest about relying on [14] and [5], and the literature is cited appropriately.\n\nWhere I sit: the gap is not cosmetic. It is the central step connecting correlated instances to the forbidden-structure probability. To my eye it is probably fixable—one would need to either prove that online outputs can be made near-disjoint at the cost of a negligible failure probability, or modify the OGP argument to handle overlaps—but the current manuscript does not contain that argument. The reader's report and the stress-test note are on target; I agree with the low soundness score.\n\nWho should read it: anyone working on algorithmic barriers in random structures will want to know this line of attack. But I would not cite Theorem 2.3 as proven until the gap is closed.\n\nRecommendation: send to peer review, but flag the missing disjointness argument prominently. The result, if repaired, is worth publishing; the current proof is not complete.","headline":"The positive side is solid, but the negative half's key disjointness assertion is unproven and false for a trivial algorithm, so Theorem 2.3 is not established as written.","tokens_in":11031,"tokens_out":8887,"would_cite":false,"duration_ms":85983,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62G32","60G70","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"For Gaussian data, every online algorithm for the densest submatrix problem is limited to 4/(3√2) of the optimum.","keywords":["large average submatrix","online algorithms","overlap gap property","branching overlap gap property","random tensor","Gaussian random matrix","approximation factor","computation-to-optimization gap"],"falsifier":"Run an online algorithm on a $(T,\\vec\\alpha)$-correlated instance with two sibling leaves and inspect the coordinate sets chosen at the same depth in $A(G_v)$ and $A(G_{v'})$; a single shared row or column index at a common depth violates the disjointness required by Definition 4.1. Producing such an instance-family would show the proof of Theorem 2.3 does not cover all algorithms in OLA as defined.","tokens_in":9971,"feed_emoji":"🎲","tokens_out":11407,"duration_ms":110234,"temperature":0.7,"pith_summary":"This paper studies the densest fixed-size submatrix (and subtensor) problem for matrices and tensors with independent standard Gaussian entries, where density is the average entry value. It establishes that for online algorithms—sequential procedures that build their output one coordinate at a time, a class that includes the best known polynomial-time greedy procedure—no algorithm can beat a fixed fraction of the true optimum. For matrices that fraction is $4/(3\\sqrt{2})\\approx 0.9428$; for $p$-th order tensors it is $2\\sqrt{p}/(1+p)$. A matching positive result shows that the existing Incremental Greedy Procedure already achieves this fraction with high probability, so the online class has a sharp approximation factor. If the paper is right, the long-suspected computation-to-optimization gap for this problem is fully explained within the online class, and any further improvement would require a non-online algorithm.","feed_headline":"Online dense-submatrix search hits a 4/(3√2)-factor wall","feed_subtitle":"The best online greedy procedure already achieves this bound, so the online class is exactly understood.","key_machinery":"The load-bearing object is the branching overlap gap property, implemented as a 'forbidden structure' (Definition 4.1): a $D$-regular tree of depth $N$ whose vertices carry disjoint coordinate sets $A_v^{(s)}\\subset[n]$ at each depth, with each leaf $v$ indexing a sub-tensor $M_v$ built from the union of the sets along its root-to-leaf ray. The structure is forbidden when every leaf has average at least $(\\kappa_p+\\epsilon)\\sqrt{2\\log n/k^{p-1}}$ with $\\kappa_p=2p/(p+1)$. Proposition 4.2 shows such structures have probability at most $\\exp(-cpk\\log n)$, by bounding a level-averaged Gaussian sum and choosing $D$ large enough to dominate the combinatorial enumeration of the coordinate sets. Lemma 4.4 converts any online algorithm into a candidate forbidden structure: on a $(T,\\vec\\alpha)$-correlated instance, where each vertex carries an independent Gaussian tensor and each leaf sees blocks from its ancestor tensors, conditional independence plus Jensen's inequality upgrades a single-instance success probability $p_{\\mathrm{suc}}$ to success on all leaves with probability at least $p_{\\mathrm{suc}}^{|L|}$. Comparing the two bounds forces $p_{\\mathrm{suc}}\\le \\exp(-(c/D^N)k\\log n)$.","core_discovery":"The paper proves Theorem 2.3: for a tensor $G\\in(\\mathbb R^n)^{\\otimes p}$ with i.i.d. standard normal entries, $k=k_n\\to\\infty$, and every $\\epsilon>0$, there is $c=c(\\epsilon,p)>0$ such that every online algorithm $A$ satisfies\n$$P\\left[\\mathrm{Ave}(A(G))\\ge \\left(\\frac{2p}{p+1}+\\epsilon+o_k(1)\\right)\\sqrt{\\frac{2\\log n}{$k^{{p-1}}$}}\\right]\\le \\exp(-ck\\log n).$$\nSince the Incremental Greedy Procedure is online and, by Theorem 2.1, attains the matching value $\\left(\\frac{2p}{p+1}-o_k(1)\\right)\\sqrt{2\\log n/k^{p-1}}$ with probability $1-o(1)$, the online class has approximation factor exactly $2\\sqrt{p}/(1+p)$ relative to the tensor optimum $\\sqrt{2p\\log n/k^{p-1}}$. For $p=2$, this factor is $4/(3\\sqrt{2})\\approx 0.9428$, recovering the value $\\frac{4}{3}\\sqrt{2\\log n/k}$ that the Incremental Greedy Procedure was already known to reach.","pith_inferences":["Editorial extension: the upper-bound argument uses only Gaussian tail bounds and block independence, so the same constant should hold for sub-Gaussian entries with matching sub-Gaussian norm; the paper does not claim this extension.","Editorial extension: the online barrier suggests that two-pass or backtracking algorithms are the natural candidates to close the remaining gap, since they are not constrained by the sequential coordinate-by-coordinate rule that the proof exploits.","Editorial extension: a finite-size simulation of the Incremental Greedy Procedure on standard normal matrices could test whether empirical averages track $4/(3\\sqrt{2})$ of the predicted optimum with finite-size corrections of order $1/\\sqrt{k}$; the paper reports no simulations."],"forward_implications":["The Incremental Greedy Procedure is optimal within the online class: no online algorithm can whp produce an average larger than $(\\frac{2p}{p+1}+o_k(1))\\sqrt{2\\log n/k^{p-1}}$.","For tensor order $p$, the relative gap $1-\\frac{2\\sqrt p}{1+p}$ grows with $p$, so higher-order tensors admit a larger gap between the online barrier and the true optimum.","Any polynomial-time algorithm that beats this factor must lie outside the online class as defined in Definition 2.2; the paper does not rule out such algorithms.","The branching-OGP proof supplies an elementary template for other dense-substructure problems where an ultrametric tree of high-value solutions can be ruled out by a Gaussian tail estimate."],"supporting_citations":[{"why":"Establishes the optimal value $2\\sqrt{\\log n/k}$ for the matrix case and introduces the LAS algorithm, fixing the benchmark against which the online factor is measured.","marker":"[1]"},{"why":"The graph-alignment branching-OGP construction on an ultrametric tree is the template whose correlated-instance technique this paper adapts.","marker":"[5]"},{"why":"Provides the equilibrium value $\\sqrt{2p\\log n/k^{p-1}}$ for the tensor problem, the target value for the online upper bound.","marker":"[6]"},{"why":"First applies overlap-gap methods to online algorithms in the random perceptron setting, justifying the class OLA as the right domain for the bound.","marker":"[9]"},{"why":"Introduces the Incremental Greedy Procedure and its matrix value $\\frac{4}{3}\\sqrt{2\\log n/k}$, whose optimality within OLA is the paper's main theorem.","marker":"[11]"},{"why":"Independent derivation of the tensor optimum and algorithmic barriers, used together with [6] to fix the tensor benchmark.","marker":"[13]"},{"why":"Develops Branching-OGP for mean-field spin glasses; the forbidden-structure argument here is a simple implementation of that machinery.","marker":"[14]"}],"fun_headline_variants":["Online dense-submatrix search: exact factor 4/(3√2) for p=2","Tight online approximation factor for dense submatrices: 4/(3√2)","Online algorithms for dense submatrices achieve exactly 94.28% of optimum","Greedy online method matches dense-submatrix optimum to 4/(3√2)","Exact online limit for dense submatrices: factor 2√p/(1+p)"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument treats the outputs $A(G_v)$ on the correlated leaf instances as a forbidden structure whose coordinate sets at each tree depth are disjoint; if two branches of the tree choose overlapping indices, the Gaussian tail bound that rules out the forbidden structure no longer applies.","fun_headline_variants_meta":{"raw":{"variants":["Online dense-submatrix search: exact factor 4/(3√2) for p=2","Tight online approximation factor for dense submatrices: 4/(3√2)","Online algorithms for dense submatrices achieve exactly 94.28% of optimum","Greedy online method matches dense-submatrix optimum to 4/(3√2)","Exact online limit for dense submatrices: factor 2√p/(1+p)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000399,"raw_usage":{"total_tokens":2106,"prompt_tokens":987,"completion_tokens":1119,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":603,"completion_tokens_details":{"reasoning_tokens":1006}},"tokens_in":603,"tokens_out":1119,"duration_ms":10115,"temperature":1.0,"reasoning_tokens":1006,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T17:58:25.066731+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an online algorithm on a $(T,\\vec\\alpha)$-correlated instance with two sibling leaves and inspect the coordinate sets chosen at the same depth in $A(G_v)$ and $A(G_{v'})$; a single shared row or column index at a common depth violates the disjointness required by Definition 4.1. Producing such an instance-family would show the proof of Theorem 2.3 does not cover all algorithms in OLA as defined.","supporting_citations":[{"cited_title":"Bhamidi, P","cited_arxiv_id":null,"evidence_quote":"Establishes the optimal value $2\\sqrt{\\log n/k}$ for the matrix case and introduces the LAS algorithm, fixing the benchmark against which the online factor is measured."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The graph-alignment branching-OGP construction on an ultrametric tree is the template whose correlated-instance technique this paper adapts."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the equilibrium value $\\sqrt{2p\\log n/k^{p-1}}$ for the tensor problem, the target value for the online upper bound."},{"cited_title":"Gamarnik, E","cited_arxiv_id":null,"evidence_quote":"First applies overlap-gap methods to online algorithms in the random perceptron setting, justifying the class OLA as the right domain for the bound."},{"cited_title":"Gamarnik and Q","cited_arxiv_id":null,"evidence_quote":"Introduces the Incremental Greedy Procedure and its matrix value $\\frac{4}{3}\\sqrt{2\\log n/k}$, whose optimality within OLA is the paper's main theorem."},{"cited_title":"Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers","cited_arxiv_id":"2506.17118","evidence_quote":"Independent derivation of the tensor optimum and algorithmic barriers, used together with [6] to fix the tensor benchmark."},{"cited_title":"Huang and M","cited_arxiv_id":null,"evidence_quote":"Develops Branching-OGP for mean-field spin glasses; the forbidden-structure argument here is a simple implementation of that machinery."}],"review_version":1}