标题： 不确定性下的敏感性和查询复杂性 显示英文标题

标题： Sensitivity and Query Complexity under Uncertainty

摘要： 在本文中，我们研究了在存在不确定性的情况下布尔函数的查询复杂性，这是受到允许输入未知的无限处理器并行计算的启发。 我们允许每个查询产生三种结果：零、一或未知。 输出也可能是：零、一或未知，但有一个约束条件，即只有在无法从揭示的输入位确定答案时才应输出“未知”。 这种对布尔函数的扩展称为其无危险扩展。 - 我们在我们的不确定性查询复杂性模型中证明了黄的著名敏感性定理[数学年刊，2019]的类似结果。 - 我们表明，布尔函数无危险扩展的确定性查询复杂度在其随机查询复杂度的二次方以内，在其量子查询复杂度的四次方以内，优于布尔世界中的最佳已知界限。 - 我们展示了计算布尔函数的决策树的最小深度（大小）与其无危险扩展的决策树之间的指数差距。 - 我们提出了将计算布尔函数的决策树转换为计算其无危险对应物的决策树的一般方法，并证明了该构造的最优性。 我们还通过输入中未知值的最大数量来参数化此结果。 - 我们根据底层布尔函数的素质蕴含和素质被蕴含的数量，给出了布尔函数无危险扩展的决策树大小复杂性的下界。 显示英文摘要

摘要： 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.