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.

In this paper, we prove the first fixed-depth size-hierarchy theorem for uniform ${\mathrm{AC}}^0[\oplus]$. In particular, we show that for any fixed $d$ and integer parameter $k$, the class ${\mathcal{{C}}}_{d,k}$ of functions that have uniform ${\mathrm{AC}}^0[\oplus]$ formulas of depth $d$ and size $n^k$ form an infinite hierarchy. We show this by exhibiting the first class of functions that have uniform ${\mathrm{AC}}^0[\oplus]$ formulas of size $n^k$ but no ${\mathrm{AC}}^0[\oplus]$ formulas of size less than $n^{\varepsilon_0 k}$ for some absolute constant $\varepsilon_0 > 0$. The uniform formulas are designed to solve the $\delta$-coin problem, which is the computational problem of distinguishing between coins that are heads with probability $(1+\delta)/2$ or $(1-\delta)/2,$ where $\delta$ is a parameter that is going to $0$. We study the complexity of this problem and make progress on both upper bound and lower bound fronts. Regarding Upper bounds, for any constant $d\geq 2$, we show that there are uniform monotone ${\mathrm{AC}}^0$ formulas (i.e., made up of AND and OR gates only) solving the $\delta$-coin problem that have depth $d$, size $\exp(O(d\cdot(1/\delta)^{1/(d-1)}))$, and sample complexity (i.e., number of inputs) ${\mathop{\mathrm{poly}}}(1/\delta).$ This matches previous upper bounds of O'Donnell and Wimmer [ICALP 2007: Automata, Languages and Programming, Lecture Notes in Comput. Sci. 4596, Springer, New York, 2007, pp. 195--206] and Amano [ICALP 2009: Automata, Languages and Programming, Lecture Notes in Comput. Sci. 5555, Springer, New York, 2009, pp. 59--70] in terms of size (which is optimal), while improving the sample complexity from $\exp(O(d\cdot(1/\delta)^{1/(d-1)}))$ to ${\mathop{\mathrm{poly}}}(1/\delta)$. The improved sample complexity is crucial for proving the size-hierarchy theorem. Regarding Lower bounds, we show that the preceding upper bounds are nearly tight (in terms of size) even for the significantly stronger model of ${\mathrm{AC}}^0[\oplus]$ formulas (which are also allowed NOT and Parity gates): formally, we show that any ${\mathrm{AC}}^0[\oplus]$ formula solving the $\delta$-coin problem must have size $\exp(\Omega(d\cdot(1/\delta)^{1/(d-1)})).$ This strengthens a result of Shaltiel and Viola [SIAM J. Comput., 39 (2010), pp. 3122--3154], who prove an $\exp(\Omega((1/\delta)^{1/(d+2)}))$ lower bound for ${\mathrm{AC}}^0[\oplus]$ circuits, and a result of Cohen, Ganor, and Raz [APPROX-RANDOM, LIPIcs. Leibniz Int. Proc. Inform. 28, Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik, Wadern, 2014, pp. 618--629], who show an $\exp(\Omega((1/\delta)^{1/(d-1)}))$ lower bound for ${\mathrm{AC}}^0$ circuits. The upper bound is a derandomization involving a use of Janson's inequality and an extension of classical polynomial-based combinatorial designs. For the lower bound, we prove an optimal (up to a constant factor) degree lower bound for multivariate polynomials over ${\mathbb{F}}_2$ solving the $\delta$-coin problem, which may be of independent interest.

In this work we prove the first Fixed-depth Size-Hierarchy Theorem for uniform AC0[⊕]. In particular, we show that for any fixed d, the class Cd,k of functions that have uniform AC0[⊕] formulas of depth d and size nk form an infinite hierarchy. We show this by exhibiting the first class of explicit functions where we have nearly (up to a polynomial factor) matching upper and lower bounds for the class of AC0[⊕] formulas.

The problem of constructing hazard-free Boolean circuits dates back to the 1940s and is an important problem in circuit design. Our main lower-bound result unconditionally shows the existence of functions whose circuit complexity is polynomially bounded while every hazard-free implementation is provably of exponential size. Previous lower bounds on the hazard-free complexity were only valid for depth 2 circuits. The same proof method yields that every subcubic implementation of Boolean matrix multiplication must have hazards. These results follow from a crucial structural insight: Hazard-free complexity is a natural generalization of monotone complexity to all (not necessarily monotone) Boolean functions. Thus, we can apply known monotone complexity lower bounds to find lower bounds on the hazard-free complexity. We also lift these methods from the monotone setting to prove exponential hazard-free complexity lower bounds for non-monotone functions. As our main upper-bound result, we show how to efficiently convert a Boolean circuit into a bounded-bit hazard-free circuit with only a polynomially large blow-up in the number of gates. Previously, the best known method yielded exponentially large circuits in the worst case, so our algorithm gives an exponential improvement. As a side result, we establish the NP-completeness of several hazard detection problems.

We provide a characterisation for the size of proofs in tree-like Q-Resolution and tree-like QU-Resolution by a Prover–Delayer game, which is inspired by a similar characterisation for the proof size in classical tree-like Resolution. This gives one of the first successful transfers of one of the lower bound techniques for classical proof systems to QBF proof systems. We apply our technique to show the hardness of three classes of formulas for tree-like Q-Resolution. In particular, we give a proof of the hardness of the parity formulas from Beyersdorff et al. (2015) [10] for tree-like Q-Resolution and of the formulas of Kleine Büning et al. (1995) [29] for tree-like QU-Resolution.

The problem of constructing hazard-free Boolean circuits dates back to the 1940s and is an important problem in circuit design. Our main lower-bound result unconditionally shows the existence of functions whose circuit complexity is polynomially bounded while every hazard-free implementation is provably of exponential size. Previous lower bounds on the hazard-free complexity were only valid for depth 2 circuits. The same proof method yields that every subcubic implementation of Boolean matrix multiplication must have hazards. These results follow from a crucial structural insight: Hazard-free complexity is a natural generalization of monotone complexity to all (not necessarily monotone) Boolean functions. Thus, we can apply known monotone complexity lower bounds to find lower bounds on the hazard-free complexity. We also lift these methods from the monotone setting to prove exponential hazard-free complexity lower bounds for non-monotone functions.