{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihel5q6mlhkc6tf7web7papxahcsyx56ewgfe5bn3d2rgewj3uzkq",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mpo3k65p4vj2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2607.01216v1",
  "publishedAt": "2026-07-02T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Deeparnab Chakrabarty",
    "Hang Liao"
  ],
  "textContent": "**Authors:** Deeparnab Chakrabarty, Hang Liao\n\nWe 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 $Ω(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öbius 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 $\\tilde{O}_r(kn)$ queries. Finally, we bypass parity and rank constraints for linear hypergraphs, achieving a subquadratic $\\tilde{O}(kn^{1.5})$ query complexity for $k$-connectivity. This significantly improves upon the general $\\tilde{O}(n^2)$ bound derived via symmetric submodular function minimization.",
  "title": "Query Complexity of Hypergraph Connectivity and Learnability using CUT Oracles"
}