{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreicycn3ix4fkp7vlku5ge37gfhzfhzmbd5zsu4mawpv5i3kr7naa44",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mnz63kpso6w2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.11448v1",
  "publishedAt": "2026-06-11T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Yuzhou Gu",
    "Xin Li",
    "Yinzhan Xu"
  ],
  "textContent": "**Authors:** Yuzhou Gu, Xin Li, Yinzhan Xu\n\nWe study the query complexity of Boolean functions $f: \\\\{0, 1\\\\}^n \\rightarrow \\\\{0, 1\\\\}$ in the noisy query model introduced by Feige, Raghavan, Peleg and Upfal [SICOMP 1994]. In this model, an algorithm can adaptively query the bits of an input vector, but each query result is independently flipped with constant probability $p \\in (0, 1/2)$; repeated queries are allowed. The noisy query complexity $\\mathsf{N}_p(f)$ of a function $f$ is defined as the minimum expected number of queries needed to compute $f(x)$ with error probability at most $1/3$, for the worst case input $x$. We prove a general lower bound on $\\mathsf{N}_p(f)$ based on degree statistics of certain subgraphs of the Boolean hypercube. This is the first general lower bound beyond those implied by the simple observation that $\\mathsf{N}_p(f)$ is lower bounded by the randomized query complexity. We show that this recovers (up to a constant factor) most previously known lower bounds on the noisy query complexity of Boolean functions, providing a unified framework for understanding these results and simplifying the proofs in several cases. Furthermore, this resolves in the affirmative an open problem of Gu, Li and Xu [COLT 2025] that $\\mathsf{N}_p(f) = Ω(\\mathsf{I}(f) \\log \\mathsf{I}(f))$, where $\\mathsf{I}(f)$ denotes the total influence of $f$. We also apply our general lower bound to obtain tight bounds on the noisy query complexity for several new functions.",
  "title": "A Unified Lower Bound on the Noisy Query Complexity of Boolean Functions"
}