| Title | : | Sensitivity and Query Complexity under Uncertainty |
| Speaker | : | Sai Soumya Nalli (Microsoft Research) |
| Details | : | Tue, Aug 12, 2025 4:00 PM, @ SSB 334 |
| Abstract | : | In this work, we study the query complexity of Boolean functions in the presence of uncertainty, motivated by parallel computation with an unlimited number of processors where some inputs may be unknown. We allow each query to return one of three values: zero, one, or unknown, and the output may also be zero, one, or unknown, with “unknown” given only when the answer cannot be determined 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 (2019) in our model, show that deterministic query complexity is at most quadratic in its randomised query complexity and quartic in its quantum query complexity, and exhibit an exponential gap between decision-tree complexities for Boolean functions and their hazard-free extensions. We also present optimal constructions for converting decision trees into their hazard-free counterparts (parameterised by the number of unknowns) and give lower bounds in terms of prime implicants and prime implicates. This talk is based on joint work with (in alphabetical order) Deepu Benson, Balagopal Komarath, Nikhil Mande, Jayalal Sarma and Karteek Sreenivasaiah. The arXiv version can be found at https://arxiv.org/pdf/2507.00148 |