On Condensation of Block Sensitivity, Certificate Complexity and the ๐– ๐–ญ๐–ฃ \mathsf{AND} (and ๐–ฎ๐–ฑ \mathsf{OR} ) Decision Tree Complexity

Sai Soumya NalliKarthikeya Polisetty, Jayalal Sarma ยท 2026

Read On Condensation of Block Sensitivity, Certificate Complexity and the ๐– ๐–ญ๐–ฃ \mathsf{AND} (and ๐–ฎ๐–ฑ \mathsf{OR} ) Decision Tree Complexity by Sai Soumya NalliKarthikeya Polisetty, Jayalal Sarma (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-01042.txt.

Description

Sai Soumya Nalli and co-authors ask whether hard yes-no tasks can be shrunk to few inputs while staying hard. They show one trait, block sensitivity, will not shrink. A task with query cost k can lose most of its bite on every small slice, dropping to a much lower bound. That same task sinks a like claim for certificate cost, and it settles a 2024 open ask in the no. AND and OR decision trees meet the same fate, failing to shrink in the same sense.

Catalog record

CREATORSai Soumya NalliKarthikeya Polisetty, Jayalal Sarma
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34083
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library ยท About the Tower of Babel