Hardness Condensation for Decision Tree Measures by Restrictions
Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh · 2026
Read Hardness Condensation for Decision Tree Measures by Restrictions by Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-00754.txt.
Description
Chandrima Kayal and colleagues ask whether a Boolean function whose complexity is far below its variable count can be limited to a similar number of variables with its measure preserved. Earlier work on queries showed lossless condensation is impossible there. The authors show decision tree measures, including block sensitivity and certificate measure, also resist lossless condensation. On the positive side, every function has a restriction keeping at least roughly the square root of its measure, with a slightly weaker result for randomised and quantum queries.
Catalog record
| CREATOR | Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62634 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602.00754