We study the query complexity on slices of Boolean functions. Among other results we show that there exists a Boolean function for which we need to query all but 7 input bits to compute its value, even if we know beforehand that the number of 0's and 1's in the input are the same, i.e., when our input is from the middle slice. This answers a question of Byramji. Our proof is non-constructive, but we also propose a concrete candidate function that might have the above property. Our results are related to certain natural discrepancy type questions that, somewhat surprisingly, have not been studied before.
We study the query complexity on slices of Boolean functions. Among other results we show that there exists a Boolean function for which we need to query all but 7 input bits to compute its value, even if we know beforehand that the number of 0's and 1's in the input are the same, i.e., when our input is from the middle slice. This answers a question of Byramji. Our proof is non-constructive, but we also propose a concrete candidate function that might have the above property. Our results are related to certain natural discrepancy type questions that, somewhat surprisingly, have not been studied before.
We study the query complexity of Boolean functions f:{0,1}n→{0,1} in the noisy query model introduced by Feige, Raghavan, Peleg and Upfal [SICOMP 1994]. In this model, an algorithm can adaptively query the bits of an input vector, but each query result is independently flipped with constant probability p∈(0,1/2); repeated queries are allowed. The noisy query complexity Np(f) of a function f is defined as the minimum expected number of queries needed to compute f(x) with error probability at most 1/3, for the worst case input x. We prove a general lower bound on Np(f) based on degree statistics of certain subgraphs of the Boolean hypercube. This is the first general lower bound beyond those implied by the simple observation that Np(f) is lower bounded by the randomized query complexity. We show that this recovers (up to a constant factor) most previously known lower bounds on the noisy query complexity of Boolean functions, providing a unified framework for understanding these results and simplifying the proofs in several cases. Furthermore, this resolves in the affirmative an open problem of Gu, Li and Xu [COLT 2025] that Np(f)=Ω(I(f)logI(f)), where I(f) denotes the total influence of f. We also apply our general lower bound to obtain tight bounds on the noisy query complexity for several new functions.
We provide two sufficient and necessary conditions to characterize any n-bit partial Boolean function with exact quantum query complexity 1. Using the first characterization, we present all n-bit partial Boolean functions that depend on n bits and can be computed exactly by a 1-query quantum algorithm. Due to the second characterization, we construct a function F that maps any n-bit partial Boolean function to some integer, and if an n-bit partial Boolean function f depends on k bits and can be computed exactly by a 1-query quantum algorithm, then F(f) is non-positive. In addition, we show that the number of all n-bit partial Boolean functions that depend on k bits and can be computed exactly by a 1-query quantum algorithm is not bigger than an upper bound depending on n and k. Most importantly, the upper bound is far less than the number of all n-bit partial Boolean functions for all efficiently big n.
We investigate efficient algorithms for computing Boolean function properties relevant to query complexity. Such properties include, for example, deterministic, randomized, and quantum query complexities; block sensitivity; certificate complexity; and degree as a real polynomial. The algorithms compute the properties, given an n-variable function's truth table (of size N=2 n ) as input. Our main results are the following: O(N log 2 3 log N) algorithms for many common properties, an O(N log 2 5 log N) algorithm for block sensitivity, an O(N) algorithm for testing "quasi symmetry," a notion of a "tree decomposition" of a Boolean function, proof that the decomposition is unique, and an O(N log 2 3 log N) algorithm for finding it, a subexponential-time approximation algorithm for space-bounded quantum query complexity. To develop this algorithm, we give a new way to search systematically through unitary matrices using finite-precision arithmetic. The algorithms discussed have been implemented in a linkable library.
Given a Boolean function f:{0,1}n→{0,1}, the goal in the usual query model is to compute f on an unknown input x∈{0,1}n while minimizing the number of queries to x. One can also consider a "distinguishing" problem denoted by fsab: given an input x∈f−1(0) and an input y∈f−1(1), either all differing locations are replaced by a ∗, or all differing locations are replaced by †, and an algorithm's goal is to identify which of these is the case while minimizing the number of queries. Ben-David and Kothari [ToC'18] introduced the notion of randomized sabotage complexity of a Boolean function to be the zero-error randomized query complexity of fsab. A natural follow-up question is to understand Q(fsab), the quantum query complexity of fsab. In this paper, we initiate a systematic study of this. The following are our main results: ∙ If we have additional query access to x and y, then Q(fsab)=O(min{Q(f),n}). ∙ If an algorithm is also required to output a differing index of a 0-input and a 1-input, then Q(fsab)=O(min{Q(f)1.5,n}). ∙Q(fsab)=Ω(fbs(f)), where fbs(f) denotes the fractional block sensitivity of f. By known results, along with the results in the previous bullets, this implies that Q(fsab) is polynomially related to Q(f). ∙ The bound above is easily seen to be tight for standard functions such as And, Or, Majority and Parity. We show that when f is the Indexing function, Q(fsab)=Θ(fbs(f)), ruling out the possibility that Q(fsab)=Θ(fbs(f)) for all f.
The problem of finding optimal querying policy, for expected query complexity of symmetric boolean threshold functions was solved in [1] in the context of collocated networks. In this paper, instead of considering the optimal policy to compute the functions, we define the problem of verification of the function value. We use this idea to provide a simpler proof of the optimal querying policy for threshold functions. The method is more generic and is extended to delta and some other symmetric functions. We also provide some partial results for interval functions and finally address a question posed in [1]. Recently we have extended these results to any symmetric function of boolean inputs, which we mention at the end.