Average-case deterministic query complexity of boolean functions with fixed weight

We explore the average-case deterministic query complexity of boolean functions under the uniform distribution, denoted by Dₐve(f), the minimum average depth of zero-error decision tree computing a boolean function f. This measure found several applications across diverse fields. We study Dₐve(f) of several common functions, including penalty shoot-out functions, symmetric functions, linear threshold functions and tribes functions. Let wt(f) denote the number of the inputs on which f outputs $1$. We prove that Dₐve(f) ≤ log wt(f)/log n + O(log log wt(f)/log n) when wt(f) ≥ 4 log n (otherwise, Dₐve(f) = O(1)), and that for almost all fixed-weight functions, Dₐve(f) ≥ log wt(f)/log n - O( log log wt(f)/log n), which implies the tightness of the upper bound up to an additive logarithmic term. We also study Dₐve(f) of circuits. Using H{a}stad's switching lemma or Rossman's switching lemma [Comput. Complexity Conf. 137, 2019], one can derive upper bounds Dₐve(f) ≤ n(1 - 1/O(k)) for width-k CNFs/DNFs and Dₐve(f) ≤ n(1 - 1/O(log s)) for size-s CNFs/DNFs, respectively. For any w ≥ 1.1 log n, we prove the existence of some width-w size-(2ʷ/w) DNF formula with Dₐve (f) = n (1 - log n/Θ(w)), providing evidence on the tightness of the switching lemmas.