# Query Complexity of Hypergraph Connectivity and Learnability using CUT Oracles

arXiv: https://arxiv.org/abs/2607.01216 · HTML: https://mlsanity.com/paper/2607.01216/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2026.

## Built on by (most cited first, 1 of 1)

- [Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds](https://mlsanity.com/paper/2608.02176/) (2026)

## Abstract (arXiv)

We investigate the power of CUT queries to reveal the structure of unknown hypergraphs. While simple graphs allow for optimal O(n)-query connectivity algorithms, hypergraphs face a fundamental identifiability barrier in that distinct hypergraphs can share identical cut-profiles, making exact edge learning impossible in general, a primitive crucial in the graph connectivity algorithms. We first present a zero-error randomized algorithm that identifies the connected components of any weighted hypergraph using O(n) expected queries, matching the Omega(n) lower bound. This approach bypasses the reconstruction barrier by introducing the notion of ``independent families'' -- vertex subpartitions that do not share hyperedges -- and iteratively coarsening them using auxiliary weighted graph connectivity techniques [Liao-Chakrabarty, 2024]. Second, we demonstrate that the impossibility of exact learning depends on hyperedge parity. For even-parity hypergraphs, we show that the structure is reconstructible using a M"obius transform on the CUT function to implement binary-search-style vertex identification. This yields deterministic algorithms for obtaining k-connectivity certificates for r-bounded even hypergraphs in tildeOr(kn) queries. Finally, we bypass parity and rank constraints for linear hypergraphs, achieving a subquadratic tildeO(kn1.5) query complexity for k-connectivity. This significantly improves upon the general tildeO(n2) bound derived via symmetric submodular function minimization.