On the Computation and Verification Query Complexity of Symmetric Functions

In the query model of multivariate function computation, the values of the inputs are queried se-quentially in an order that may depend on previously revealed values until the function’s value can be determined. The function’s computation query complexity is the lowest expected number of queries required by any query order. Instead of computation, it is often easier to consider verification, where the value of the function is given and the queries aim to verify it. The lowest expected number of queries necessary is the function’s verification query complexity. We show that for all symmetric func-tions of independent binary random variables, the computation and verification complexities coincide. This provides a simple method for finding the query complexity and optimal query order for computing many functions. We also show that after relaxing any of the symmetry, independence, or binary inputs restrictions, there are functions whose verification complexity is strictly lower than their computation complexity.