Pith. sign in

REVIEW 4 major objections 6 minor 49 references

Provably Finding a Hidden Dense Submatrix among Many Planted Dense Submatrices via Convex Programming

T0 review · 4 major / 6 minor · reviewed 2026-08-03 · deepseek-v4-flash

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

Pith's one-line read This paper proves that a convex program can recover a hidden dense submatrix exactly, even when many other dense submatrices are planted in the same matrix, provided the target block is sufficiently dense and large relative to its rivals.

desk verdict A real multi-block extension with a genuine gap in the key spectral bound; worth refereeing, not yet proven. read the letter →

arxiv 2601.03946 v3 pith:MCM7MQMA submitted 2026-01-07 math.OC cs.LG

Valentine Olanubi (1) , Phineas Agar (1) , Brendan Ames (2) ((1) University of Alabama , Department of Mathematics , (2) University of Southampton , School of Mathematical Sciences) This is my paper · ORCID
classification math.OCcs.LG MSC 90C2590C2760B20
keywords densestsubmatrixproblemconvexrelaxationnuclearnormminimizationplanteddensestochasticblockmodelperfectrecoveryphasetransitionmaximumclique
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 densest submatrix problem asks for the fixed-size submatrix with the most 1s in a binary matrix; it is NP-hard and generalizes maximum clique. Prior convex-relaxation guarantees assumed a single dense block hidden in noise. This paper relaxes that to a heterogeneous planted-submatrix model with many dense blocks of varying sizes, and proves that a nuclear-norm convex program uniquely recovers the planted block when its expected density is sufficiently above the next-densest block and the block is large enough. The same framework gives an adversarial guarantee. Experiments on synthetic matrices and real collaboration networks match the predicted phase transitions.

What carries the argument

The machinery is the convex relaxation (3): minimize ||X||_* + gamma Tr(Y 1^T) subject to Tr(X 1^T)=mn, P_Omega(X-Y)=0, 0<=X<=11^T, Y>=0, where the nuclear norm promotes a rank-one solution X=uv^T. The proof builds a Lagrange-multiplier dual certificate with a matrix W in the nuclear-norm subdifferential, decomposes W = lambda R + lambda S, and bounds the spectral norms of R and S via Bernstein and matrix concentration inequalities; the required bound on S relies on Lemma 3.5, a coupling argument for random matrices with Bernoulli resampling.

What would settle it

Generate a planted-model instance that satisfies (4a)-(4c) exactly (e.g. m1=80, n1=80, M=N=1000, p11=0.8, p*=0.2) and solve the convex relaxation (3); if the support of the resulting optimal X is not exactly U1 x V1, then Theorem 2.1 is falsified.

Watch

Extended reading notes

Core claim

The central claim is Theorem 2.1: for matrices sampled from the planted submatrix model (a rectangular stochastic block model with per-block Bernoulli probabilities), if the target block is no larger than every other block, all blocks are large enough, and the density gap p11 - p* satisfies the explicit bound (4c), then the planted block is the unique densest m1 x n1 submatrix and X* = u1 v1^T is the unique optimal solution of the convex relaxation (3), with high probability. Theorem 2.2 gives an analogous guarantee against a deterministic adversary that adds and deletes a controlled number of entries. The proof constructs an explicit dual certificate satisfying the KKT conditions.

Load-bearing premise

The proof's bound on the spectral norm of the dual certificate's off-block term S requires that the actual column statistics inside the planted block be coupled with an independent Bernoulli resampling (Lemma 3.5); as written, S1 is resampled independently, so this coupling is absent and the sufficient conditions in Theorem 2.1 are not fully proven unless that step is repaired.

Editorial extensions

If this is right

  • If Theorem 2.1 holds, the densest submatrix can be found in polynomial time (via SDP or ADMM) for a broad class of instances with many dense blocks, not just a single planted block.
  • The sufficient condition gives a quantitative phase-transition curve: recovery is guaranteed once p11 - p* exceeds a max of terms scaling like sqrt(sigma_tilde^2 N log N / (m1 n1)), sqrt(sigma11^2 log N / min(m1,n1)), and sqrt(max{sigma_tilde^2,1} (log N)^3 / min(m1,n1)), which can be used to tune the regularization parameter gamma.
  • The adversarial guarantee (Theorem 2.2) shows the convex program is robust to a two-person hiding game: unless the adversary is allowed to add or delete Omega(m1 n1) entries or create near-planted blocks, the planted block is recovered.
  • The results specialize to and generalize prior guarantees for planted cliques, max-edge bicliques, and dense subgraphs; on real networks, the program recovers known maximum cliques in the Jazz, Karate, Dolphins, Les Miserables, and ASOIAF networks.

Reading between the lines

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

  • The proof gap around Lemma 3.4 and Lemma 3.5 (independent resampling versus the required coupling) suggests a concrete repair: construct S1 by resampling only off-diagonal blocks after conditioning on the planted block's column sums, or replace Lemma 3.5 with a direct two-sided concentration bound; until then, the claimed spectral bound is not fully established.
  • The phase-transition condition (4c) has the same qualitative shape as recovery thresholds in biclustering and semidefinite-programming community detection, so the result likely extends to weighted or dense matrices after binarization, and to recovering all dense blocks via a union of rank-one solutions.
  • When several blocks tie for densest (as in multiple maximum cliques), the paper's experiments show the convex solution becomes a convex combination of the tied blocks; a rounding scheme based on the diagonal of X may disambiguate them, but the paper leaves this unproven.
  • The condition (4a) that the planted block is no larger than any rival block is an admitted simplification; the authors note a deterministic condition on average densities should remove it, so a natural next step is a version without (4a).
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 6 minor

Summary. The paper studies the densest m×n submatrix problem for binary matrices that may contain many planted dense blocks. It proposes a nuclear-norm relaxation (3), constructs explicit dual certificates, and states sufficient conditions for a planted block to be the unique densest submatrix and the unique optimal solution of the relaxation. Theorem 2.1 gives such conditions for a heterogeneous stochastic block model; Theorem 2.2 gives an analogous deterministic adversarial guarantee. Numerical experiments on synthetic matrices and real-world networks are presented as empirical verification of the predicted phase transitions. The main technical engine is a KKT certificate whose dual subgradient W is decomposed as W = λR + λS, with ∥R∥ bounded by Lemma 3.3 and ∥S∥ by Lemma 3.4.

Significance. If the recovery guarantees were fully established, the paper would be a useful advance: it extends convex-relaxation recovery beyond the single-planted-block setting to multiple dense blocks with heterogeneous edge probabilities, and it provides an adversarial counterpart. The dual-certificate construction is concrete, and the authors release implementations in Python, MATLAB, and R. The catch is that the proof of the key S-bound is incomplete as written, and the numerical experiments do not provide the claimed verification of the theoretical phase transition. The contribution is therefore conditional, but the issues are of the kind that can, in principle, be repaired or reframed; this is not a desk-reject situation.

major comments (4)
  1. [Section 3.5.3, Lemma 3.4/3.5] The proof defines S1 by independently resampling fresh Bernoulli variables in U1×V_s and U_r×V1, then sets S2 = S − S1. Lemma 3.5 bounds Θ − Θ̃ where Θ̃ is a deterministic function of the same Θ through the column counts n_j in (47). In contrast, the ν_j and μ_i used in S are counts from the original A, while S1 is a fresh draw independent of those counts. Hence S2 does not have the coupled form required by Lemma 3.5; equalities (48) and (49) do not follow. Since the bound ∥W∥ ≤ 1 in (50) relies on (48)–(49), the KKT certificate for Theorem 2.1 is not established as written. A genuinely different argument is needed for S.
  2. [Section 5.2, Figures 4a/4b] The claimed verification is not tied to Theorem 2.1. In Experiment 1 the plotted threshold q = 0.25 + max{sqrt(M log M/(3m)), log M/m} has constants 3 and 1 chosen ad hoc; the third term of (4c), sqrt(max{σ̃²,1}(log N)^3 / min{m1,n1}), is absent and would dominate for the tested sizes. In Experiment 2, p11 = p22 = q, so p* = q and the gap p11 − p* = 0, violating (4c); for m > 250 condition (4a) also fails, and for m < M/2 the target is not the unique densest m×m-submatrix. Thus the experiments do not verify the phase transition claimed in Theorem 2.1; they only illustrate behavior in related regimes.
  3. [Section 4, Eqs. (51)–(53)] The certificate in Theorem 3.1 uses the subgradient u1v1^T/√(m1n1), so λ must be compared to 1/√(m1n1). The displayed condition in (51), λ ≥ 1/(m1n1) + 2(1−δ̃)γ, and the final choice λ = 1/(m1n1) + c(1−δ̃)√(m1n1) use 1/(m1n1) instead. Consequently (52) and (53) have the wrong scale, and the proof of nonnegativity of Λ and the bound ∥W∥ < 1 for Theorem 2.2 does not go through. If this is a typo it should be corrected and the surrounding algebra checked; as written it is a load-bearing inconsistency.
  4. [Theorem 2.1, uniqueness claim] Theorem 2.1 also asserts that (U1,V1) is the unique densest m1×n1-submatrix with high probability. Section 3 proves uniqueness of the optimal solution of (3) via Theorem 3.1, but I did not find an argument showing that the optimality of X* implies, or that (4a)–(4c) directly imply, combinatorial uniqueness among all O(M^{m1} N^{n1}) submatrices. Since Remark 2 says (4a) is imposed 'largely to ensure' this, the theorem should either include the missing concentration argument or state the uniqueness claim with a separate proof.
minor comments (6)
  1. [Abstract and Section 1] The abstract says 'deterministic adversarial' without completing the phrase; it should be 'deterministic adversarial model' or 'adversarially generated matrices.' Also, 'wide application the study' is missing 'in.'
  2. [Appendix A, Lemma A.1 proof] The display 'p_s n − 6 max{...} < n_j < p_s n − 6 max{...}' has the same expression on both sides; the right-hand side should be p_s n + 6 max{...}.
  3. [Section 3.4.2, Eq. (33)] The notation σ²_{p1s} is not defined; it should be p_{1s}(1 − p_{1s}) or a variance proxy explicitly defined before use.
  4. [Section 5.5.1.1] The displayed value 'γ=12√mn=0.03' appears to be missing a denominator; it should be γ = 12/√(mn), since m = n = 400 gives 12/400 = 0.03.
  5. [Section 5.2.1] The statement that 'Conditions (4a) and (4b) hold by our choice of m and M' in Experiment 1 ignores the third term of (4c); the plotted curve also omits that term, which confuses the reader about what is being verified.
  6. [Lemma 3.5] The lemma statement lacks the side condition, used in the proof, that the block sizes n_s are large enough relative to log N. It should either state that condition or be formulated for the parameter regime guaranteed by (4b).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the recovery theorems are derived from an explicit KKT dual certificate plus concentration bounds, not from fitted inputs or author-imported uniqueness.

full rationale

The paper's central claim (Theorems 2.1 and 2.2) is a sufficient-condition result. The proof is constructive: Section 3.2 builds explicit Lagrange multipliers Λ, Ξ and a subgradient W satisfying the KKT system (9); Section 3.5 bounds ∥W∥ via the decomposition W=λR+λS, using Lemma 3.3 for R and Lemma 3.4 for S, both obtained from the stated matrix Bernstein and scalar Bernstein inequalities. No parameter is fitted to the data being predicted; the γ interval in (5) and the SNR condition (4c) are solved out of the requirement ∥W∥≤1 and the nonnegativity of Λ and Ξ. The theorem's conclusion that (U1,V1) is the unique densest submatrix follows from uniqueness of the relaxation optimum, not from assumption (4a) alone; (4a) is explicitly acknowledged as a simplifying assumption. Citations to the authors' earlier work [5,6,7,14] are used for background, for ADMM implementation, and for the claim that the new conditions specialize prior guarantees; they are not used to prove the new theorem. The numerical phase-transition curves in Section 5.2 use hand-set constants (c1=1 or 6) and oracle values of p11 and p*, and Experiment 2 runs outside assumption (4a), so the numerics are not an independent quantitative test; that is an experimental-design weakness, not a circular derivation. The gap in the proof of Lemma 3.4 (S1 is independently resampled, so S2 is not literally the coupled Θ−Θ̃ object of Lemma 3.5) is a serious correctness/missing-argument issue, but it is not a reduction of the theorem to its own assumptions and therefore is not scored as circularity.

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

The paper introduces no new physical or mathematical entities. Its free parameters are mostly universal constants in the theorem statements and a hand-chosen γ in experiments. The main extra assumptions are the multi-block Bernoulli model, the adversarial noise caps, and the simplified size condition (4a).

free parameters (2)
  • Phase-transition constants in experiments = 1 in Experiment 1, 6 in Experiment 2
    The plotted curves use constants c1=1 and c1=6 chosen by hand; they do not follow from the theorem's stated constants and the curve formulas do not match (4c).
  • Regularization parameter γ in experiments = 6/(m(q−p*)) in synthetic tests; 12/m on real networks
    γ is hand-selected with a heuristic factor of 6 or 12; the theorem only guarantees an interval with unspecified universal constants.
assumptions (5)
  • domain assumption Entries of A are independent Bernoulli within each planted block
    The planted submatrix model defined in Definition 1.2 supplies the probability model used throughout the proof.
  • domain assumption Adversarial deletion/addition bounds in Section 2.3.1
    The adversary is limited to deleting at most (1−δ~)m1 entries per column and adding at most δm1 entries per column outside the planted block; the recovery theorem depends on these caps.
  • standard math Scalar and matrix Bernstein inequalities
    Lemmas 3.1 and 3.2, and Theorem A.1, are used for binomial tails and spectral norm bounds.
  • ad hoc to paper Condition (4a): m1n1 ≤ m_r n_s for every off-diagonal block
    This is used to ensure the planted block is the densest expected m1×n1 submatrix; the authors acknowledge in Remark 2 that a more complicated condition would be needed without it.
  • ad hoc to paper Condition (4b): (log N)^3 ≤ min{m_r^2, n_s^2}
    This block-size growth condition is needed to absorb (log N)^{3/2} terms in the proof of the W bound.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Provably Finding a Hidden Dense Submatrix among Many Planted Dense Submatrices via Convex Programming." pith.science (2026). https://pith.science/paper/MCM7MQMA

@misc{pith2026260103946,
  author       = {Pith},
  title        = {Pith review of: Provably Finding a Hidden Dense Submatrix among Many Planted Dense Submatrices via Convex Programming},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MCM7MQMA}},
  note         = {Machine review of arXiv:2601.03946}
}
read the original abstract

We consider the densest submatrix problem, which seeks the submatrix of fixed size of a given binary matrix that contains the most nonzero entries. This problem is a natural generalization of fundamental problems in combinatorial optimization, e.g., the densest subgraph, maximum clique, and maximum edge biclique problems, and has wide application the study of complex networks. Much recent research has focused on the development of sufficient conditions for exact solution of the densest submatrix problem via convex relaxation. The vast majority of these sufficient conditions establish identification of the densest submatrix within a graph containing exactly one large dense submatrix hidden by noise. The assumptions of these underlying models are not observed in real-world networks, where the data may correspond to a matrix containing many dense submatrices of varying sizes. We extend and generalize these results to the more realistic setting where the input matrix may contain \emph{many} large dense subgraphs. Specifically, we establish sufficient conditions under which we can expect to solve the densest submatrix problem in polynomial time for random input matrices sampled from a generalization of the stochastic block model. Moreover, we also provide sufficient conditions for perfect recovery under a deterministic adversarial. Numerical experiments involving randomly generated problem instances and real-world collaboration and communication networks are used empirically to verify the theoretical phase-transitions to perfect recovery given by these sufficient conditions.

Figures

Figures reproduced from arXiv: 2601.03946 by the authors.

Figure 1
Figure 1. Examples of matrices sampled from planted submatrix and balanced planted submatrix models [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Examples of easy and hard to solve instances of the densest submatrix problem sampled in [PITH_FULL_IMAGE:figures/full_fig_p025_2.png] view at source ↗
Figure 3
Figure 3. Examples of easy, hard, and impossible graphs for recovery of the planted submatrix sampled [PITH_FULL_IMAGE:figures/full_fig_p027_3.png] view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: Recovery counts for Experiments 1 and 2. Darker squares indicate more recoveries out of 10 [PITH_FULL_IMAGE:figures/full_fig_p027_4.png]
Figure 5
Figure 5. Figure 5: Adjacency matrices of the JAZZ, KARATE, DOLPHINS, and LESMIS networks and recovered [PITH_FULL_IMAGE:figures/full_fig_p029_5.png]
Figure 6
Figure 6. Figure 6: Adjacency matrices of the character interaction networks for Books 1,2,3, and 5 of the [PITH_FULL_IMAGE:figures/full_fig_p030_6.png]
Figure 7
Figure 7. Figure 7: Adjacency matrix of the character interaction network for Book 4 of the [PITH_FULL_IMAGE:figures/full_fig_p031_7.png]
Figure 8
Figure 8. Figure 8: Average recovery error with 95%-confidence interval before and after rounding for each choice [PITH_FULL_IMAGE:figures/full_fig_p033_8.png]
Figure 9
Figure 9. Figure 9: Recovery error before and after rounding, and run-time, for each choice of [PITH_FULL_IMAGE:figures/full_fig_p034_9.png]
Figure 10
Figure 10. Figure 10: Recovery error before and after rounding, and run-time, for each choice of [PITH_FULL_IMAGE:figures/full_fig_p034_10.png]
Figure 11
Figure 11. Figure 11: Recovered solutions for a random matrix sampled from the planted submatrix model from [PITH_FULL_IMAGE:figures/full_fig_p035_11.png]
Figure 12
Figure 12. Figure 12: Recovered solutions for the JAZZ Network for different choices of [PITH_FULL_IMAGE:figures/full_fig_p035_12.png]
Figure 13
Figure 13. Figure 13: Recovered solutions for the ASOIAF Book 1 Network for different choices of γ. 35 [PITH_FULL_IMAGE:figures/full_fig_p035_13.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

49 extracted references · 2 linked inside Pith

  1. [1]

    [Accessed 24- 10-2025]

    Network of Thrones — networkofthrones.com.https://networkofthrones.com/. [Accessed 24- 10-2025]

    2025

  2. [2]

    Community detection and stochastic block models, 2023

    Emmanuel Abbe. Community detection and stochastic block models, 2023

    2023

  3. [3]

    Inapprox- imability of densestκ-subgraph from average case hardness.Unpublished manuscript, 1:6, 2011

    Noga Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz, and Omri Weinstein. Inapprox- imability of densestκ-subgraph from average case hardness.Unpublished manuscript, 1:6, 2011

    2011

  4. [4]

    Finding a large hidden clique in a random graph.Random Structures & Algorithms, 13(3-4):457–466, 1998

    Noga Alon, Michael Krivelevich, and Benny Sudakov. Finding a large hidden clique in a random graph.Random Structures & Algorithms, 13(3-4):457–466, 1998

    1998

  5. [5]

    Guaranteed clustering and biclustering via semidefinite programming.Mathe- matical Programming, 147(1):429–465, 2014

    Brendan PW Ames. Guaranteed clustering and biclustering via semidefinite programming.Mathe- matical Programming, 147(1):429–465, 2014

    2014

  6. [6]

    Guaranteed recovery of planted cliques and dense subgraphs by convex relax- ation.Journal of Optimization Theory and Applications, 167(2):653–675, 2015

    Brendan PW Ames. Guaranteed recovery of planted cliques and dense subgraphs by convex relax- ation.Journal of Optimization Theory and Applications, 167(2):653–675, 2015

    2015

  7. [7]

    Nuclear norm minimization for the planted clique and biclique problems.Mathematical programming, 129(1):69–89, 2011

    Brendan PW Ames and Stephen A Vavasis. Nuclear norm minimization for the planted clique and biclique problems.Mathematical programming, 129(1):69–89, 2011

    2011

  8. [8]

    Finding large and small dense subgraphs.arXiv preprint cs/0702032, 2007

    Reid Andersen. Finding large and small dense subgraphs.arXiv preprint cs/0702032, 2007

    arXiv 2007

Show all 49 references
  1. [9]

    Clique relaxations in social network analysis: The maximum k-plex problem.Operations Research, 59(1):133–142, 2011

    Balabhaskar Balasundaram, Sergiy Butenko, and Illya V Hicks. Clique relaxations in social network analysis: The maximum k-plex problem.Operations Research, 59(1):133–142, 2011

    2011

  2. [10]

    Sharp nonasymptotic bounds on the norm of random matrices with independent entries

    Afonso S Bandeira and Ramon Van Handel. Sharp nonasymptotic bounds on the norm of random matrices with independent entries. 2016

    2016

  3. [11]

    The game of Game of Thrones: Networked concordances and fractal dramaturgy

    Andrew Beveridge and Michael Chemers. The game of Game of Thrones: Networked concordances and fractal dramaturgy. InReading Contemporary Serial Television Universes, pages 201–225. Routledge, 2018

    2018

  4. [12]

    Network of Thrones.Math Horizons, 23(4):18–22, 2016

    Andrew Beveridge and Jie Shan. Network of Thrones.Math Horizons, 23(4):18–22, 2016. 36

    2016

  5. [13]

    Mining market data: A network ap- proach.Computers & Operations Research, 33(11):3171–3184, 2006

    Vladimir Boginski, Sergiy Butenko, and Panos M Pardalos. Mining market data: A network ap- proach.Computers & Operations Research, 33(11):3171–3184, 2006

    2006

  6. [14]

    Convex optimization for the densest subgraph and densest submatrix problems

    Polina Bombina and Brendan Ames. Convex optimization for the densest subgraph and densest submatrix problems. InSN Operations Research Forum, volume 1, pages 1–24. Springer, 2020

    2020

  7. [15]

    Oxford university press, 2013

    St´ ephane Boucheron, G´ abor Lugosi, and Pascal Massart.Concentration inequalities: A nonasymp- totic theory of independence. Oxford university press, 2013

    2013

  8. [16]

    Convex pptimization.Cambridge UP, 2004

    Stephen Boyd. Convex pptimization.Cambridge UP, 2004

    2004

  9. [17]

    Distributed opti- mization and statistical learning via the alternating direction method of multipliers.Foundations and Trends®in Machine learning, 3(1):1–122, 2011

    Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al. Distributed opti- mization and statistical learning via the alternating direction method of multipliers.Foundations and Trends®in Machine learning, 3(1):1–122, 2011

    2011

  10. [18]

    Algorithm 457: finding all cliques of an undirected graph.Commu- nications of the ACM, 16(9):575–577, 1973

    Coen Bron and Joep Kerbosch. Algorithm 457: finding all cliques of an undirected graph.Commu- nications of the ACM, 16(9):575–577, 1973

    1973

  11. [19]

    Robust principal component analysis? Journal of the ACM (JACM), 58(3):1–37, 2011

    Emmanuel J Cand` es, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM (JACM), 58(3):1–37, 2011

    2011

  12. [20]

    A note on the problem of reporting maximal cliques

    Fr´ ed´ eric Cazals and Chinmay Karande. A note on the problem of reporting maximal cliques. Theoretical computer science, 407(1-3):564–568, 2008

    2008

  13. [21]

    Rank-sparsity incoherence for matrix decomposition.SIAM Journal on Optimization, 21(2):572–596, 2011

    Venkat Chandrasekaran, Sujay Sanghavi, Pablo A Parrilo, and Alan S Willsky. Rank-sparsity incoherence for matrix decomposition.SIAM Journal on Optimization, 21(2):572–596, 2011

    2011

  14. [22]

    Statistical-computational phase transitions in planted models: The high-dimensional setting

    Yudong Chen and Jiaming Xu. Statistical-computational phase transitions in planted models: The high-dimensional setting. InInternational conference on machine learning, pages 244–252. PMLR, 2014

    2014

  15. [23]

    Detection and recovery of hidden submatrices

    Marom Dadon, Wasim Huleihel, and Tamir Bendory. Detection and recovery of hidden submatrices. IEEE Transactions on Signal and Information Processing over Networks, 10:69–82, 2024

    2024

  16. [24]

    A generalization of the Sherman-Morrison-Woodbury formula.Applied Mathe- matics Letters, 24(9):1561–1564, 2011

    Chun Yuan Deng. A generalization of the Sherman-Morrison-Woodbury formula.Applied Mathe- matics Letters, 24(9):1561–1564, 2011

    2011

  17. [25]

    Finding approximately rank-one submatrices with the nuclear norm andℓ 1-norm.SIAM Journal on Optimization, 23(4):2502–2540, 2013

    Xuan Vinh Doan and Stephen Vavasis. Finding approximately rank-one submatrices with the nuclear norm andℓ 1-norm.SIAM Journal on Optimization, 23(4):2502–2540, 2013

    2013

  18. [26]

    Relations between average case complexity and approximation complexity

    Uriel Feige. Relations between average case complexity and approximation complexity. InProceed- ings of the thiry-fourth annual ACM symposium on Theory of computing, pages 534–543, 2002

    2002

  19. [27]

    Finding and certifying a large hidden clique in a semirandom graph.Random Structures & Algorithms, 16(2):195–208, 2000

    Uriel Feige and Robert Krauthgamer. Finding and certifying a large hidden clique in a semirandom graph.Random Structures & Algorithms, 16(2):195–208, 2000

    2000

  20. [28]

    Community structure in jazz.Advances in complex systems, 6(04):565–573, 2003

    Pablo M Gleiser and Leon Danon. Community structure in jazz.Advances in complex systems, 6(04):565–573, 2003

    2003

  21. [29]

    JHU Press, 2013

    Gene H Golub and Charles F Van Loan.Matrix Computations. JHU Press, 2013

    2013

  22. [30]

    Identification of a 5-protein biomarker molecular signa- ture for predicting Alzheimer’s disease.PloS One, 3(9):e3111, 2008

    Mart ´ ın G´ omez Ravetti and Pablo Moscato. Identification of a 5-protein biomarker molecular signa- ture for predicting Alzheimer’s disease.PloS One, 3(9):e3111, 2008

    2008

  23. [31]

    On the linear convergence of the alternating direction method of multipliers.Mathematical Programming, 162(1):165–199, 2017

    Mingyi Hong and Zhi-Quan Luo. On the linear convergence of the alternating direction method of multipliers.Mathematical Programming, 162(1):165–199, 2017

    2017

  24. [32]

    Impact of interference on multi-hop wireless network performance

    Kamal Jain, Jitendra Padhye, Venkata N Padmanabhan, and Lili Qiu. Impact of interference on multi-hop wireless network performance. InProceedings of the 9th annual international conference on Mobile computing and networking, pages 66–80, 2003

    2003

  25. [33]

    Reducibility among combinatorial problems

    Richard M Karp. Reducibility among combinatorial problems. In50 Years of Integer Programming 1958-2008: from the Early Years to the State-of-the-Art, pages 219–241. Springer, 2009

    1958

  26. [34]

    Ruling out PTAs for graph min-bisection, densek-subgraph, and bipartite clique

    Subhash Khot. Ruling out PTAs for graph min-bisection, densek-subgraph, and bipartite clique. SIAM Journal on Computing, 36(4):1025–1071, 2006. 37

    2006

  27. [35]

    AcM Press New York, 1993

    Donald Ervin Knuth.The Stanford GraphBase: a platform for combinatorial computing, volume 1. AcM Press New York, 1993

    1993

  28. [36]

    A survey on the densest subgraph problem and its variants.ACM Computing Surveys, 56(8):1–40, 2024

    Tommaso Lanciano, Atsushi Miyauchi, Adriano Fazzone, and Francesco Bonchi. A survey on the densest subgraph problem and its variants.ACM Computing Surveys, 56(8):1–40, 2024

    2024

  29. [37]

    The dimension-free structure of nonhomoge- neous random matrices.Inventiones mathematicae, 214(3):1031–1080, 2018

    Rafa l Lata la, Ramon van Handel, and Pierre Youssef. The dimension-free structure of nonhomoge- neous random matrices.Inventiones mathematicae, 214(3):1031–1080, 2018

    2018

  30. [38]

    David Lusseau, Karsten Schneider, Oliver J Boisseau, Patti Haase, Elisabeth Slooten, and Steve M Dawson. The bottlenose dolphin community of doubtful sound features a large proportion of long- lasting associations: can geographic isolation explain this unique trait?Behavioral ...

    2003

  31. [39]

    Maximum cliques in protein structure comparison

    No¨ el Malod-Dognin, Rumen Andonov, and Nicola Yanev. Maximum cliques in protein structure comparison. InExperimental Algorithms: 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy, May 20-22, 2010. Proceedings 9, pages 106–117. Springer, 2010

    2010

  32. [40]

    Harnessing the mathematics of matrix decomposition to solve planted and maximum clique problem.arXiv preprint arXiv:2307.09022, 2023

    Salma Omer and Montaz Ali. Harnessing the mathematics of matrix decomposition to solve planted and maximum clique problem.arXiv preprint arXiv:2307.09022, 2023

    2023 arXiv

  33. [41]

    Maximum edge bi-clique via matrix decomposition.Journal of Industrial and Management Optimization, 21(11):6270–6294, 2025

    Salma Omer and Montaz Ali. Maximum edge bi-clique via matrix decomposition.Journal of Industrial and Management Optimization, 21(11):6270–6294, 2025

    2025

  34. [42]

    Clique relaxation models in social network analysis

    Jeffrey Pattillo, Nataly Youssef, and Sergiy Butenko. Clique relaxation models in social network analysis. InHandbook of Optimization in Complex Networks: Communication and Social Networks, pages 143–162. Springer, 2011

    2011

  35. [43]

    Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization.SIAM review, 52(3):471–501, 2010

    Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization.SIAM review, 52(3):471–501, 2010

    2010

  36. [44]

    Graph clustering.Computer Science Review, 1(1):27–64, 2007

    Satu Elisa Schaeffer. Graph clustering.Computer Science Review, 1(1):27–64, 2007

    2007

  37. [45]

    Sharp phase transitions in estimation with low-degree polynomials

    Youngtak Sohn and Alexander S Wein. Sharp phase transitions in estimation with low-degree polynomials. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 891–902, 2025

    2025

  38. [46]

    A semidefinite programming-based branch-and-cut algorithm for biclustering

    Antonio M Sudoso. A semidefinite programming-based branch-and-cut algorithm for biclustering. INFORMS Journal on Computing, 37(6):1433–1456, 2025

    2025

  39. [47]

    The worst-case time complexity for generat- ing all maximal cliques and computational experiments.Theoretical computer science, 363(1):28–42, 2006

    Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. The worst-case time complexity for generat- ing all maximal cliques and computational experiments.Theoretical computer science, 363(1):28–42, 2006

    2006

  40. [48]

    User-friendly tail bounds for sums of random matrices.Foundations of computational mathematics, 12:389–434, 2012

    Joel A Tropp. User-friendly tail bounds for sums of random matrices.Foundations of computational mathematics, 12:389–434, 2012

    2012

  41. [49]

    An information flow model for conflict and fission in small groups.Journal of anthropological research, 33(4):452–473, 1977

    Wayne W Zachary. An information flow model for conflict and fission in small groups.Journal of anthropological research, 33(4):452–473, 1977. A Proof of Lemma 3.5 Lemma 3.5 is a special case of the Matrix Bernstein Inequality applied toZ=Θ− ˜Θas found in the hypothesis of Lemm...

    1977

Pith tools

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