{"id":"11c201a1-dc62-4b12-997b-8f966c1b6ddf","arxiv_id":"2605.30113","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Establishes sharp low-degree estimation thresholds in planted hypergraphs and tensor PCA, resolving open hardness questions and yielding polynomial-time algorithms above thresholds.","lead":"The paper identifies sharp thresholds for low-degree polynomial estimators in planted dense subhypergraph and tensor PCA models. This maps computational-statistical gaps in high-dimensional recovery problems.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"Reader already flagged the conditional-variant assumption as weakest and noted the review is abstract-only; the absence of any manuscript text precludes identifying a more specific load-bearing concern.","tokens_in":1817,"tokens_out":208,"duration_ms":14832,"concrete_test":"Obtain the full manuscript and re-derive the SNR threshold in the conditional variant (the section extending Sohn-Wein 2025); check whether the resulting threshold exactly matches the claimed sharp transition for planted dense subhypergraphs when the planted set size exceeds √ n.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The provided materials contain only the abstract; no equations, proof sketches, or technical sections are available. The central claim rests on a conditional extension of the Sohn-Wein framework producing the correct SNR above the √ n scale, but without the derivation it is impossible to locate an internal inconsistency, hidden assumption, or gap in the argument.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper studies low-degree estimation thresholds in the planted dense subhypergraph model on n vertices (distinguishing regimes above and below the √n scale for the planted set), sparse tensor PCA, and tensor PCA with general priors. Above √n it identifies a sharp threshold for low-degree estimation and converts the matching upper bounds into polynomial-time algorithms for almost exact recovery; below √n it establishes hardness, resolving questions left open by Schramm-Wein (2022) and Sohn-Wein (2025). Analogous sharp transitions are obtained for sparse tensor PCA, while a low-degree lower bound is proved for the general-prior tensor PCA model at the critical signal scale. All lower bounds hold for degree D = n^δ (δ > 0 constant) and rely on a conditional variant of the Sohn-Wein (2025) framework that is claimed to produce the correct signal-to-noise ratio where the unconditional approach is insufficient.","tokens_in":1863,"tokens_out":441,"duration_ms":25422,"significance":"If the conditional extension is rigorously justified, the results would resolve concrete open questions on computational-statistical gaps in hypergraph and tensor models, supply both matching lower and upper bounds, and yield explicit polynomial-time algorithms up to the identified thresholds. The work thereby strengthens the low-degree framework by demonstrating how a conditional variant can be used to obtain tight thresholds in regimes where prior unconditional analyses were inconclusive.","major_comments":[],"minor_comments":[{"comment":"The abstract states that the conditional variant 'yields the correct signal-to-noise ratio' but does not indicate where in the manuscript the verification that this variant preserves the original threshold (rather than shifting it) is carried out; a short pointer to the relevant lemma or proposition would help readers.","section":"Abstract"},{"comment":"The phrase 'almost exact recovery' is used for the algorithmic results above the threshold; a precise definition (e.g., in terms of overlap or Hamming error) should appear in the introduction or the statement of the algorithmic theorem.","section":null}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the careful reading and positive assessment of our work, including the recommendation for minor revision. We are glad that the contributions toward resolving open questions from Schramm-Wein (2022) and Sohn-Wein (2025) via the conditional low-degree framework are viewed as significant. Below we address the sole substantive point raised regarding justification of the conditional extension.","responses":[{"response":"We appreciate this observation. The manuscript already contains a self-contained rigorous development of the conditional variant (see Section 3 and the proofs in Sections 4–6). The conditional framework is defined via an explicit conditioning on a high-probability event that preserves the relevant moments while allowing the low-degree likelihood ratio to be computed exactly; all steps are deterministic and do not rely on unproven heuristics. This yields the sharp thresholds stated in Theorems 1.1, 1.3, and 1.5. We are happy to add a short clarifying paragraph in the introduction if the referee believes it would further emphasize the distinction from the unconditional approach.","revision_made":"partial","referee_comment":"If the conditional extension is rigorously justified, the results would resolve concrete open questions on computational-statistical gaps in hypergraph and tensor models, supply both matching lower and upper bounds, and yield explicit polynomial-time algorithms up to the identified thresholds. The work thereby strengthens the low-degree framework by demonstrating how a conditional variant can be used to obtain tight thresholds in regimes where prior unconditional analyses were inconclusive."}],"tokens_in":1420,"tokens_out":327,"duration_ms":19954,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"This paper pins down sharp low-degree estimation thresholds in the planted dense subhypergraph model once the hidden set exceeds sqrt(n). Above that scale it gives matching upper bounds and converts them into polynomial-time algorithms for almost exact recovery. Below the scale it confirms the hardness regimes predicted earlier, closing questions left open by Schramm-Wein and the prior Sohn-Wein work.\n\nThe technical step that makes this possible is a conditional variant of the Sohn-Wein framework. The unconditional version apparently does not produce the right signal-to-noise ratio in these models, so the authors condition on a suitable event to recover the correct threshold. They apply the same idea to sparse tensor PCA and obtain an analogous phase transition. For tensor PCA with a general prior they prove a low-degree lower bound exactly at the critical signal scale that matches the degree-signal tradeoff suggested in earlier papers.\n\nThe bounds hold for degrees up to n^delta and the paper supplies both lower and upper bounds in each case. The conversion of the upper bounds into explicit algorithms is a concrete plus.\n\nThe main soft spot is that everything rests on the conditional extension working as claimed. The abstract indicates the authors believe it yields the correct SNR where the unconditional approach fails, but the strength of the argument depends on how cleanly that conditioning is justified and whether it introduces any hidden dependence on the signal. The general-prior lower bound is solid but stops short of a full characterization.\n\nThis is for people already working on low-degree methods and statistical-computational gaps in hypergraph and tensor models. Readers who know the Sohn-Wein framework will follow the extension most easily.\n\nI would send it to peer review. The claims are specific, the open questions are real, and the framework extension is worth checking in detail.","headline":"This paper sharpens low-degree thresholds for planted dense subhypergraphs above sqrt(n), resolves two open questions via a conditional framework extension, and turns the upper bounds into poly-time algorithms.","tokens_in":2287,"tokens_out":440,"would_cite":true,"duration_ms":19578,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"In planted dense subhypergraphs with hidden set larger than sqrt(n), low-degree estimation has a sharp threshold.","keywords":["low-degree estimation","planted dense subhypergraph","tensor PCA","sharp threshold","statistical-computational gap","high-dimensional statistics","recovery algorithms","polynomial estimators"],"falsifier":"An explicit computation or simulation of the expected correlation of a degree-D polynomial with the hidden signal in the planted dense subhypergraph model, checking whether it crosses from below to above the detection threshold exactly at the claimed critical signal strength.","tokens_in":2714,"feed_emoji":"","tokens_out":723,"duration_ms":28209,"temperature":0.7,"pith_summary":"This paper identifies sharp thresholds for when low-degree polynomial estimators can recover hidden planted structures in hypergraph and tensor models. For planted dense subhypergraphs, when the hidden vertex set exceeds size sqrt(n), low-degree methods succeed above a certain signal strength and fail below it. Below the sqrt(n) scale, it shows that low-degree methods are hard in the regimes expected from earlier predictions. The work also finds similar transitions in sparse tensor PCA and establishes matching lower bounds for tensor PCA under general priors. These findings clarify the boundary between what low-degree methods can achieve and where computational gaps appear in high-dimensional inference.","feed_headline":"Sharp threshold governs low-degree recovery in planted hypergraphs","feed_subtitle":"Above sqrt(n) planted set size, low-degree methods succeed exactly when signal strength crosses a precise value, with matching hardness belo","key_machinery":"a conditional variant of the low-degree analysis framework that yields the correct signal-to-noise ratio","core_discovery":"The paper shows that in the planted dense subhypergraph model on n vertices, there exist two regimes split by the sqrt(n) scale for the planted set size. Above this scale, a sharp threshold governs low-degree estimation success. Below it, hardness is proven for low-degree methods. Analogous sharp phase transitions hold for sparse tensor PCA. For tensor PCA with general priors, a low-degree lower bound is proven at the critical signal scale, and the lower bounds hold for degrees up to n to a constant power, with matching upper bounds that yield efficient algorithms above the threshold in the larger-set regime.","pith_inferences":["The sqrt(n) scale may mark a transition point where different analysis techniques become necessary in other planted models.","These thresholds could guide the search for algorithms that surpass low-degree limitations in the hard regimes.","The conditional analysis approach might apply to additional high-dimensional statistical problems involving tensors or hypergraphs.","It raises the question of whether information-theoretic recovery remains possible in the regimes where low-degree methods fail."],"forward_implications":["Polynomial-time algorithms achieve almost exact recovery above the identified threshold in planted dense subhypergraphs and sparse tensor PCA when the planted set is larger than sqrt(n).","Low-degree lower bounds apply up to degree n to a positive constant power.","The results establish hardness for low-degree methods below the sqrt(n) scale in the predicted regimes.","For tensor PCA with a general prior, the low-degree bound matches the degree-signal tradeoff at the critical scale."],"fun_headline_variants":["Sqrt(n) splits low-degree thresholds in planted hypergraphs","Sharp low-degree transitions in tensor PCA and hypergraphs","Low-degree hardness below sqrt(n) for subhypergraph recovery","Tensor PCA low-degree lower bounds at critical signal scales"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The conditional variant of the low-degree analysis accurately identifies the signal-to-noise ratio in settings where the standard approach does not suffice.","fun_headline_variants_meta":{"raw":{"variants":["Sqrt(n) splits low-degree thresholds in planted hypergraphs","Sharp low-degree transitions in tensor PCA and hypergraphs","Low-degree hardness below sqrt(n) for subhypergraph recovery","Tensor PCA low-degree lower bounds at critical signal scales"]},"model":"grok-4.3","cost_usd":0.005801,"raw_usage":{"total_tokens":2838,"prompt_tokens":820,"num_sources_used":0,"completion_tokens":64,"cost_in_usd_ticks":58012000,"prompt_tokens_details":{"text_tokens":820,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1954,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":820,"tokens_out":64,"duration_ms":14945,"temperature":1.0,"reasoning_tokens":1954,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-29T00:00:18.917960+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An explicit computation or simulation of the expected correlation of a degree-D polynomial with the hidden signal in the planted dense subhypergraph model, checking whether it crosses from below to above the detection threshold exactly at the claimed critical signal strength.","supporting_citations":[],"review_version":1}