Bounds for Hardness Condensation in the Query Model
Pith reviewed 2026-05-22 11:08 UTC · model grok-4.3
The pith
There exist Boolean functions where restricting to O(k) variables drops block sensitivity and certificate complexity to O(k to the 2/3).
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
There exists a Boolean function f such that any restriction of f to O(M(f)) variables has M-complexity at most O-tilde(M(f) to the 2/3), where M is in {bs, fbs, C, D}. This establishes that these decision-tree measures cannot be condensed losslessly. The authors also show that for every Boolean function there exists a restriction to O(M(f)) variables whose M-complexity is at least Omega(M(f) to the 1/2), for M in {bs, fbs, C, UC_min, UC_1, UC, D, tilde-deg, lambda}, with a slightly weaker guarantee for randomized and quantum query complexity.
What carries the argument
The existence of a specific Boolean function f (established combinatorially) that forces any linear-sized restriction to lose a polynomial factor in its block sensitivity or certificate complexity.
If this is right
- Lossless condensation is impossible for block sensitivity, fractional block sensitivity, certificate complexity, and decision tree complexity.
- A square-root lossy condensation is always possible for block sensitivity and eight other measures including unambiguous certificates and approximate degree.
- A slightly weaker positive condensation bound holds for randomized and quantum query complexity.
- The 2/3 upper bound on the drop improves the quantitative separation shown in prior work.
Where Pith is reading between the lines
- The result indicates that hardness for these measures is distributed across many variables and cannot be localized to a small subset.
- Similar polynomial losses might appear when trying to reduce input size in related models such as communication complexity.
- The gap between the 2/3 negative bound and the 1/2 positive bound leaves open the possibility of tighter condensation thresholds.
Load-bearing premise
A particular Boolean function exists whose restrictions to O(M(f)) variables exhibit a sharp drop in the chosen complexity measure.
What would settle it
An explicit Boolean function f for which some restriction to O(M(f)) variables retains M-complexity Omega(M(f) to the power 0.9) or higher, or a proof that every function admits a lossless condensation.
read the original abstract
For any Boolean function $f:\{0,1\}^n \to \{0,1\}$ with a complexity measure having value $k \ll n$, is it possible to restrict the function $f$ to $\Theta(k)$ variables while keeping the complexity preserved at $\Theta(k)$? This question, in the context of query complexity, was recently studied by G{\"{o}}{\"{o}}s, Newman, Riazanov and Sokolov (STOC 2024). They showed, among other results, that query complexity can not be condensed losslessly. They asked if complexity measures like block sensitivity or unambiguous certificate complexity can be condensed losslessly? In this work, we show that decision tree measures like block sensitivity and certificate complexity, cannot be condensed losslessly. That is, there exists a Boolean function $f$ such that any restriction of $f$ to $O(\mathcal{M}(f))$ variables has $\mathcal{M}(\cdot)$-complexity at most $\tilde{O}(\mathcal{M}(f)^{2/3})$, where $\mathcal{M} \in \{\mathsf{bs},\mathsf{fbs},\mathsf{C},\mathsf{D}\}$. This also improves upon a result of G{\"{o}}{\"{o}}s, Newman, Riazanov and Sokolov (STOC 2024). We also complement the negative results on lossless condensation with positive results about lossy condensation. In particular, we show that for every Boolean function $f$ there exists a restriction of $f$ to $O(\mathcal{M}(f))$ variables such that its $\mathcal{M}(\cdot)$-complexity is at least $\Omega(\mathcal{M}(f)^{1/2})$, where $\mathcal{M} \in \{\mathsf{bs},\mathsf{fbs},\mathsf{C},\mathsf{UC}_{min},\mathsf{UC}_1,\mathsf{UC},\mathsf{D},\widetilde{\mathsf{deg}},\lambda\}$. We also show a slightly weaker positive result for randomized and quantum query complexity.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies hardness condensation for Boolean functions in the query model. It proves that for M in {bs, fbs, C, D}, there exists a function f with M(f)=k such that every restriction to O(k) variables satisfies M(f|ρ) ≤ Õ(k^{2/3}). This shows lossless condensation is impossible and improves on Goos et al. (STOC 2024). Complementing this, for every f the authors show there exists a restriction to O(k) variables with M(f|ρ) ≥ Ω(k^{1/2}) for M in {bs, fbs, C, UC_min, UC_1, UC, D, deg~, λ}, with slightly weaker positive results for randomized and quantum query complexity.
Significance. If the claims hold, the work gives precise polynomial bounds on condensation rates for standard query measures, resolving open questions on lossless condensation for bs, fbs, C and D while establishing a general Ω(√k) lower bound that applies to many measures. The explicit exponents and the separation between negative and positive results clarify the landscape of query complexity under restrictions and may aid further separations or reductions in the area.
major comments (1)
- [§4 (Negative condensation results)] The negative result (existence of f with the stated drop for all O(k)-variable restrictions) is proved via the probabilistic method. The union bound over binom(n, O(k)) restrictions must succeed; with n polynomial in k this is exp(Θ(k log k)) terms. The paper must verify that the tail probability for a fixed restriction violating the Õ(k^{2/3}) bound is sufficiently small (exp(-Ω(k log k))) for each of bs, fbs, C and D so that the overall probability is positive. The choice of the 2/3 exponent should be shown to arise from this calculation rather than post-hoc tuning.
minor comments (2)
- [Abstract] In the abstract and introduction, clarify exactly which prior bound of Goos et al. is improved and by what factor.
- [§2 (Preliminaries)] Define all measures (including fbs, UC variants, λ) at first use and ensure notation for Õ is uniform across theorems.
Simulated Author's Rebuttal
We thank the referee for their careful reading and constructive feedback on our manuscript. We address the major comment below and will revise the paper to provide the requested clarifications and explicit calculations.
read point-by-point responses
-
Referee: [§4 (Negative condensation results)] The negative result (existence of f with the stated drop for all O(k)-variable restrictions) is proved via the probabilistic method. The union bound over binom(n, O(k)) restrictions must succeed; with n polynomial in k this is exp(Θ(k log k)) terms. The paper must verify that the tail probability for a fixed restriction violating the Õ(k^{2/3}) bound is sufficiently small (exp(-Ω(k log k))) for each of bs, fbs, C and D so that the overall probability is positive. The choice of the 2/3 exponent should be shown to arise from this calculation rather than post-hoc tuning.
Authors: We agree that the manuscript would benefit from a more explicit verification of the tail bounds and the derivation of the exponent. In the revised version of Section 4, we will add a detailed calculation showing that, in our probabilistic construction with n polynomial in k, the probability that any fixed restriction ρ to O(k) variables yields M(f|ρ) > Õ(k^{2/3}) is at most exp(-Ω(k log k)) for each of bs, fbs, C, and D. This is obtained via measure-specific concentration arguments that ensure the union bound succeeds with positive probability. We will also include an explicit parameter-balancing step demonstrating that the exponent 2/3 arises naturally as the largest value for which the tail decay is strong enough to dominate the exp(Θ(k log k)) union-bound terms, rather than being chosen arbitrarily. revision: yes
Circularity Check
No significant circularity; claims rest on explicit constructions and existence proofs
full rationale
The negative condensation results rely on combinatorial arguments establishing existence of a specific Boolean function f whose restrictions to O(M(f)) variables exhibit the stated complexity drop for M in {bs, fbs, C, D}. The positive lossy condensation results show, for arbitrary f, existence of a suitable restriction achieving Omega(M(f)^{1/2}) complexity. Neither direction reduces any claimed prediction or first-principles result to its own inputs by construction, fitted parameters, or load-bearing self-citations. The derivation chain is self-contained against external combinatorial and probabilistic benchmarks.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Boolean functions are total functions from {0,1}^n to {0,1} and the listed complexity measures (bs, fbs, C, D, etc.) are defined in the standard way via decision trees or certificates.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.