2026-07-23T17:40:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27072 2026-07-23T11:36:19Z ddc:004 open_access

Bounds for Hardness Condensation in the Query Model Kayal, Chandrima Mittal, Rajat Nalli, Sai Soumya Paraashar, Manaswi Polisetty, Karthikeya Sarma, Jayalal Saurabh, Nitin Query Complexity Decision Trees Hardness Condensation For any Boolean function f:{0,1}ⁿ → {0,1} with a complexity measure having value k ≪ n, is it possible to restrict the function f to Θ(k) variables while keeping the complexity preserved at Θ(k)? Instantiation of this question for the measure of circuit complexity of the Boolean function was shown to be related to circuit lower bounds (Buresh-Oppenheim and Santhanam, 2006). Variants of the above question were also shown to have connections to the log-rank conjecture in communication complexity (Hrubeš, 2024) and lower bounds in proof complexity (Razborov, 2016). In the context of communication and query complexity, this question was recently studied by Göös, Newman, Riazanov and Sokolov (2024). They showed, among other results, that query complexity cannot be condensed losslessly. In this work, we show that there exists a Boolean function f such that any restriction of f to O(ℳ(f)) variables has ℳ(⋅)-complexity at most Õ(ℳ(f)^{2/3}), where ℳ is one of block sensitivity (bs), fractional block sensitivity (fbs), certificate complexity (𝖢), deterministic query complexity (𝖣), zero-error randomized query complexity (𝖱₀), and AND (and OR)-decision tree query complexity. This improves upon the results of Göös, Newman, Riazanov, and Sokolov (2024) for 𝖣 and 𝖱₀, and in particular answers their open question about the condensation of block sensitivity. We 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(ℳ(f)) variables such that its ℳ(⋅)-complexity is at least Ω(ℳ(f)^{1/2}), where ℳ ∈ {bs,fbs,𝖢,UC_{min},UC₁,UC,𝖣,deg̃,λ}. In addition, we show lossy condensation for randomized and quantum query complexity with a slightly smaller exponent. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chandrima Kayal and Rajat Mittal and Sai Soumya Nalli and Manaswi Paraashar and Karthikeya Polisetty and Jayalal Sarma and Nitin Saurabh 2026 Is Part Of LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2026.30 urn:nbn:de:0030-drops-270722 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.30 eng https://creativecommons.org/licenses/by/4.0/legalcode