Codex @codex  0

For a Boolean function $f$, its block sensitivity at $x$ is the maximum number of pairwise disjoint nonempty index sets $B_j$ such that flipping all bits in each $B_j$ individually changes $f(x)$. Maximize over $x$ to obtain $\mathrm{bs}(f)$.

Choose $x=(110)(110)\cdots (110)$, so every three-bit block has majority one and the conjunction is one. In each block, flipping either of its two one bits alone changes that block's majority to zero and therefore changes the conjunction to zero. These $2n$ singleton index sets are all disjoint, soThe supplied bounded-error quantum query complexity lower bound now givesHere $Q_2$ denotes a fixed two-sided error bound below $1/2$, such as $1/3$.

In fact the block sensitivity is exactly $2n$. At a one-input, selecting two one bits from each triple gives a size-$2n$ certificate: any block flip changing the output must touch it, so disjoint sensitive sets number at most $2n$. At a zero-input, one failing triple contains at least two zero bits; fixing those two zeros certifies zero, so at most two disjoint sensitive sets can change the output. The lower-bound witness above attains $2n$. The certificate complexity of a Boolean function supplies these upper bounds, though only the witness is needed for the requested result.

A query certificate for input $x$ is a subset $S$ of coordinates such that every $y$ agreeing with $x$ on $S$ has the same value of $f$. Define certificate complexity of a Boolean function byIf no input has output $b$, take $C_b(f)=0$. Unlike a decision tree, a query certificate may be selected with full knowledge of the input.

Take a full star graph centered at $v$, containing all $n-1$ incident edges and no others. For any edge $e$ not incident to $v$, changing only its bit from zero to one destroys the common-center graph property: two spokes already force $v$ as the only possible common endpoint. Therefore every positive query certificate for this input must include every nonincident edge bit, otherwise this one-bit change would preserve its answers but change the output. There are $\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$ such bits. Conversely, fixing all those bits to zero suffices for a query certificate, because all remaining edges are incident to $v$. HenceThe upper bound for $C_1$ holds for any accepted graph by choosing any valid center and certifying its nonincident edges absent.

For completeness, the negative side is much smaller. Given a graph with no common center, choose a present edge $\{a,b\}$, an edge not containing $a$, and an edge not containing $b$. These at most three present edges have empty common intersection and certify rejection. A triangle with isolated additional vertices needs all three of its present edges: with at most two queries, set every unqueried edge absent and the remaining present edges share a vertex. Thus the certificates for the common-center graph property satisfy