The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties

We thank the Editor and the Referees for investing time and effort in the evaluation of our manuscript. We replied to the Referees, and we resubmit an improved version of the manuscript. We answer here to the points the Editor raised.

Work is peripheral to the scope of SciPost Physics.

We did not find an explicit argument relating to this in the Referee reports and in the Editorial Recommendation, so we can only answer in general terms. We believe that our work is well within the scope of SciPost Physics: - Our object of study is a timely computational problem, see the concurrent appearance of our work, [1] and [2], which are more mathematical, but still rooted in the physics of spin glasses. For e.g., [2] adapts ideas from the rigorous study of p-spin models at large p, which has been first studied heuristically by Derrida in his classic paper [5]. - Our toolbox is that of statistical physics of disordered systems, using replica theory, Franz-Parisi analysis, and the clustering OGP analysis to probe equilibrium and out-of-equilibrium behavior of the system. We compute entropies, we look for phase transitions. Our problem may be born in computer science, but the questions we ask are those physicists would ask, and the tools we use all appeared first in the study of spin glasses. We remark that questions relating to algorithmic hardness were explored by recent published papers in this venue [3,4], written by physicists, using a physics toolbox, and studying models from computer science.

We wrote the paper as physicists interested in studying computational problems with statistical mechanics, for physicists interested in studying computational problems with statistical mechanics. All in all we believe that our paper is appropriate for a physics audience.

Address the concerns and requested changes of the Referees.

We answered point-by-point the reports of the referees, and implemented their suggestions. See the answers under the original submission, and the list of changes below.

Formatting.

We adapted our formatting to the guidelines, and polished the references. In particular, we reshaped the introduction (which contained already a discussion of perspectives), and added a corresponding mandatory conclusion section.

Relationship with [1].

In [1], the authors study the p-MAS problem in the setting of both linear and sublinear size, for large values of the tensor order p. It is well known that the p-spin model (of which the p-MAS is close, Boolean relative) converges to a Random Energy Model as p increases [5]: the authors of [1] leverage this property (in its non-trivial rigorous formulation) to provide algorithmic bounds for the problem. On the other hand, in our work we explore landscape properties in the limit k/N→0, but for finite tensor order p, thus far from the Random Energy Model limit. We also remark that our results at large p (Section 2.4) are compatible with [1]. In summary, [1] is yet another concurrent and complementary work on the same model, together with [2] and with ours, signalling the interest of the larger interdisciplinary community in the study of this problem.

Multiple arXiv versions.

Versions v1 and v2 on the arXiv are identical, except for the way we cited [2] (at the time of submission [2] was still an unpublished work, and in v1 not all authors names were correctly listed). We were not aware of the existence of [1], which appeared on the arXiv after both our submission of v2 to arXiv, and our original submission to SciPost. We now comment on [1] in the manuscript.

References

[1] Abhishek Hegade K, R., and Eren C. Kızıldağ. "Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers." 2025, arXiv: 2506.17118. [2] Bhamidi, S., Gamarnik, D., & Gong, S. (2025). Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms. arXiv preprint arXiv:2507.19259 [3]: Barbier, D. (2025). How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states. SciPost Physics, 18(3), 115. [4]: Annesi, B. L., Malatesta, E., & Zamponi, F. (2025). Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks. SciPost Physics, 18(4), 118. [5]: B. Derrida. Random-energy model: Limit of a family of disordered models. Phys. Rev. Lett., 45:79–82, Jul 1980

• After Table 1: we now comment on the negative result of the Franz-Parisi analysis, as argued in the answer to both Referees.
• Paragraph "Concurrent work: algorithmic properties for large $p$": we now compare with concurrent work [1], which appeared after our submission.
• Last paragraph of Section 3.2: we comment on the difference between the case 1 << k << N, and k/N = m with m->0.
• Section 4.1, after Algorithm 2: we stress that the IGP analysis has been put on rigorous grounds by concurrent work [1,2].
• Last paragraph of Section 4.2: we remark that the LAS analysis is structural, and that we are not adapting the convergence proof.
• Second paragraph of Section 6: we added a paragraph with more intuition on the Franz-Parisi analysis, along the lines of our discussion with Referee 2.
• Section 7: we added a Conclusion section, including lines 861-868 that previously appeared in the introduction ("Perspectives" paragraph).
• Typos: we corrected several typos, including those highlighted by Referee 1.
• Nomenclature: we changed "rank" to "order" when referring to the number of tensor indices as suggested by Referee 1.