{"ID":6626551,"CreatedAt":"2026-07-15T02:56:36.47817413Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.13011","arxiv_id":"2607.13011","title":"Testing the Independent Set Property in Hypergraphs","abstract":"The optimal sample complexity of testing if an $n$-vertex graph has an independent set of size $ρn$, or is $\\varepsilon$-far from having an independent set of size $ρn$, was established to be $\\widetilde{O}(ρ^3/\\varepsilon^2)$, in a notable result by Blais and Seth (SICOMP 2025). In contrast, for $q$-uniform hypergraphs, there is a significant gap between the best known upper and lower bounds, and there has been no progress on the problem for the last two decades. In this work, we prove a new upper bound of $\\widetilde{O}\\!\\left(\\frac{qρ^{2q-3}}{\\varepsilon^2 (q-2)!^2}\\right)$ on the sample complexity of testing the $ρ$-independent set property. The previous best known upper bound was $\\widetilde{O}\\!\\left(\\frac{2^q q! ρ^{2q}}{\\varepsilon^3}\\right)$, due to Langberg (RANDOM 2004). This establishes the optimal dependence on $\\varepsilon$ and gives an exponential improvement in the dependence on $q$. We prove our result via a new application of the hypergraph container method.","short_abstract":"The optimal sample complexity of testing if an $n$-vertex graph has an independent set of size $ρn$, or is $\\varepsilon$-far from having an independent set of size $ρn$, was established to be $\\widetilde{O}(ρ^3/\\varepsilon^2)$, in a notable result by Blais and Seth (SICOMP 2025). In contrast, for $q$-uniform hypergraph...","url_abs":"https://arxiv.org/abs/2607.13011","url_pdf":"https://arxiv.org/pdf/2607.13011v1","authors":"[\"Elena Grigorescu\",\"Shreya Nasa\",\"Cameron Seth\"]","published":"2026-07-14T17:52:23Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}