Sharp Low-Degree Thresholds for Planted-vs-Planted Testing

• URL: http://arxiv.org/abs/2606.05266v1
• Date: Wed, 03 Jun 2026 16:28:30 GMT
• Title: Sharp Low-Degree Thresholds for Planted-vs-Planted Testing
• Abstract summary: We prove matching low-degree upper and lower bounds for counting communities in the planted submatrix and planted dense subgraph models.<n>The task of weak testing, where the goal is to outperform random guessing, does not have a sharp threshold but rather a smooth transition, which we identify.
• Score: 41.99297964131035
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We establish the first sharp thresholds for low-degree polynomial tests in planted-vs-planted settings, where the goal is to determine with vanishing error which of two structured planted mechanisms generated the observed data. We prove matching low-degree upper and lower bounds for counting communities in the planted submatrix and planted dense subgraph models. The resulting testing threshold coincides, down to the sharp constant, with the known low-degree recovery threshold. In contrast, the task of weak testing, where the goal is to outperform random guessing, does not have a sharp threshold but rather a smooth transition, which we identify. To prove our results, we develop a framework for planted-vs-planted testing that builds on a latent-variable expansion originating in low-degree recovery and employs new methods to identify and prune non-signal contributions.

Related papers

• Minimax bounds for watermarked and masked recursive discrete distribution estimation [15.724207170366846]
  In the absence of a distinguishing mechanism, it has been shown that adding synthetic samples significantly reduces the marginal efficacy of new real samples.<n>We show that it is impossible to improve performance by adding watermarks unless the false negative rate of detection also vanishes.<n>We propose masking, a randomization procedure that narrows the gap in the remaining regimes to a Jensen gap.
  arXiv  Detail & Related papers  (2026-08-31T17:00:09Z)
• Evaluating Histogram Matching for Robust Deep learning-Based Grapevine Disease Detection [3.9714494364463526]
  Histogram Matching is a technique that transforms the pixel intensity distribution of an image to match a reference profile.<n>We propose a dual-stage integration of HM: (i) as a preprocessing step for normalization, and (ii) as a data augmentation technique to introduce controlled training variability.
  arXiv  Detail & Related papers  (2026-04-21T14:27:21Z)
• Temper-Then-Tilt: Principled Unlearning for Generative Models through Tempering and Classifier Guidance [51.532841645285835]
  We study machine unlearning in large generative models by framing the task as density ratio estimation to a target distribution.<n>We show it can fail to faithfully unlearn with finite samples when the forget set represents a sharp, concentrated data distribution.<n>We introduce Temper-Then-Tilt Unlearning (T3-Unlearning), which freezes the base model and applies a two-step inference procedure.
  arXiv  Detail & Related papers  (2026-02-10T19:08:40Z)
• PurSAMERE: Reliable Adversarial Purification via Sharpness-Aware Minimization of Expected Reconstruction Error [3.9306877728266425]
  We propose a novel deterministic purification method to improve adversarial robustness.<n>The method searches within its local neighborhood for a purified sample that minimizes the expected reconstruction error.<n>We show significant gains in adversarial robustness over state-of-the-art methods under strong deterministic white-box attacks.
  arXiv  Detail & Related papers  (2026-02-06T00:06:30Z)
• Shift Before You Learn: Enabling Low-Rank Representations in Reinforcement Learning [56.87989363424]
  We show that a low-rank structure naturally emerges in the shifted successor measure.<n>We quantify the amount of shift needed for effective low-rank approximation and estimation.
  arXiv  Detail & Related papers  (2025-09-05T15:48:20Z)
• A Novel Convolutional Neural Network-Based Framework for Complex Multiclass Brassica Seed Classification [0.0]
  This study proposes a novel convolutional neural network (CNN)-based framework for the efficient classification of ten common Brassica seed types.<n> Experimental results using our collected Brassica seed dataset demonstrate that the proposed model achieved a high accuracy rate of 93 percent.
  arXiv  Detail & Related papers  (2025-05-26T20:18:45Z)
• Twofold Debiasing Enhances Fine-Grained Learning with Coarse Labels [22.58772008332314]
  coarse-grained supervised pre-training suppresses the extraction of critical fine-grained features for discrimination.<n>Models suffer from overfitting due to biased distributions caused by limited fine-grained samples.<n>We propose the Twofold Debiasing (TFB) method, which addresses these challenges through detailed feature enhancement and distribution calibration.
  arXiv  Detail & Related papers  (2025-02-27T06:41:49Z)
• PlantPlotGAN: A Physics-Informed Generative Adversarial Network for Plant Disease Prediction [2.7409168462107347]
  We propose PlantPlotGAN, a physics-informed generative model capable of creating synthetic multispectral plot images with realistic vegetation indices. The results demonstrate that the synthetic imagery generated from PlantPlotGAN outperforms state-of-the-art methods regarding the Fr'echet inception distance.
  arXiv  Detail & Related papers  (2023-10-27T16:56:28Z)
• Shrinking Class Space for Enhanced Certainty in Semi-Supervised Learning [59.44422468242455]
  We propose a novel method dubbed ShrinkMatch to learn uncertain samples. For each uncertain sample, it adaptively seeks a shrunk class space, which merely contains the original top-1 class. We then impose a consistency regularization between a pair of strongly and weakly augmented samples in the shrunk space to strive for discriminative representations.
  arXiv  Detail & Related papers  (2023-08-13T14:05:24Z)
• MetaRF: Differentiable Random Forest for Reaction Yield Prediction with a Few Trails [58.47364143304643]
  In this paper, we focus on the reaction yield prediction problem. We first put forth MetaRF, an attention-based differentiable random forest model specially designed for the few-shot yield prediction. To improve the few-shot learning performance, we further introduce a dimension-reduction based sampling method.
  arXiv  Detail & Related papers  (2022-08-22T06:40:13Z)
• Fake It Till You Make It: Near-Distribution Novelty Detection by Score-Based Generative Models [54.182955830194445]
  existing models either fail or face a dramatic drop under the so-called near-distribution" setting. We propose to exploit a score-based generative model to produce synthetic near-distribution anomalous data. Our method improves the near-distribution novelty detection by 6% and passes the state-of-the-art by 1% to 5% across nine novelty detection benchmarks.
  arXiv  Detail & Related papers  (2022-05-28T02:02:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.