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

CREATORChandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62634
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602.00754

Browse the full library · About the Tower of Babel