On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914394769719296 |
|---|---|
| author | Nalli, Sai Soumya Polisetty, Karthikeya Sarma, Jayalal |
| author_facet | Nalli, Sai Soumya Polisetty, Karthikeya Sarma, Jayalal |
| contents | Given an $n$-bit Boolean function with a complexity measure (such as block sensitivity, query complexity, etc.) $M(f) = k$, the hardness condensation question asks whether $f$ can be restricted to $O(k)$ variables such that the complexity measure is $Ω(k)$?
In this work, we study the condensability of block sensitivity, certificate complexity, AND (and OR) query complexity and Fourier sparsity. We show that block sensitivity does not condense under restrictions, unlike sensitivity: there exists a Boolean function $f$ with query complexity $k$ such that any restriction of $f$ to $O(k)$ variables has block sensitivity $O(k^{\frac{2}{3}})$. This answers an open question in Göös, Newman, Riazanov, and Sokolov (2024) in the negative. The same function yields an analogous incondensable result for certificate complexity. We further show that $\mathsf{AND}$(and $\mathsf{OR}$) decision trees are also incondensable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_01042 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity Nalli, Sai Soumya Polisetty, Karthikeya Sarma, Jayalal Computational Complexity Given an $n$-bit Boolean function with a complexity measure (such as block sensitivity, query complexity, etc.) $M(f) = k$, the hardness condensation question asks whether $f$ can be restricted to $O(k)$ variables such that the complexity measure is $Ω(k)$? In this work, we study the condensability of block sensitivity, certificate complexity, AND (and OR) query complexity and Fourier sparsity. We show that block sensitivity does not condense under restrictions, unlike sensitivity: there exists a Boolean function $f$ with query complexity $k$ such that any restriction of $f$ to $O(k)$ variables has block sensitivity $O(k^{\frac{2}{3}})$. This answers an open question in Göös, Newman, Riazanov, and Sokolov (2024) in the negative. The same function yields an analogous incondensable result for certificate complexity. We further show that $\mathsf{AND}$(and $\mathsf{OR}$) decision trees are also incondensable. |
| title | On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2602.01042 |