Sensitivity and Query Complexity Under Uncertainty

Benson, D ORCID: 0000-0002-5393-1162, Komarath, B ORCID: 0009-0008-3007-6280, Mande, N ORCID: 0000-0002-9520-7340, Nalli, SS ORCID: 0009-0000-0678-9450, Sarma, J ORCID: 0000-0002-4819-5711 and Sreenivasaiah, K ORCID: 0000-0001-7396-3383 (2025) Sensitivity and Query Complexity Under Uncertainty. In: International Symposium on Mathematical Foundations of Computer Science (MFCS), 2025-8-25 - 2025-8-29, Warsaw.

Text REF_BKMSSS25_MFCS.pdf - Author Accepted Manuscript Available under License Creative Commons Attribution. Download (593kB) | Preview

Abstract

In this paper, we study the query complexity of Boolean functions in the presence of uncertainty, motivated by parallel computation with an unlimited number of processors where inputs are allowed to be unknown. We allow each query to produce three results: zero, one, or unknown. The output could also be: zero, one, or unknown, with the constraint that we should output “unknown” only when we cannot determine the answer from the revealed input bits. Such an extension of a Boolean function is called its hazard-free extension. We prove an analogue of Huang’s celebrated sensitivity theorem [Annals of Mathematics, 2019] in our model of query complexity with uncertainty. We show that the deterministic query complexity of the hazard-free extension of a Boolean function is at most quadratic in its randomized query complexity and quartic in its quantum query complexity, improving upon the best-known bounds in the Boolean world. We exhibit an exponential gap between the smallest depth (size) of decision trees computing a Boolean function, and those computing its hazard-free extension. We present general methods to convert decision trees for Boolean functions to those for their hazard-free counterparts, and show optimality of this construction. We also parameterize this result by the maximum number of unknown values in the input. We show lower bounds on size complexity of decision trees for hazard-free extensions of Boolean functions in terms of the number of prime implicants and prime implicates of the underlying Boolean function.

Item Type:	Conference Item (Unspecified)
Divisions:	Faculty of Science and Engineering Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	14 Jul 2025 10:24
Last Modified:	24 Sep 2025 08:25
DOI:	10.4230/LIPIcs.MFCS.2025.17
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3193711