Let RE denote randomized query complexity for error probability epsilon, and R := R-1/3. In this work we investigate whether a perfect composition theorem R(f o g(n)) = Omega(R(f) center dot R(g)) holds for a relation...
详细信息
ISBN:
(纸本)9783959773119
Let RE denote randomized query complexity for error probability epsilon, and R := R-1/3. In this work we investigate whether a perfect composition theorem R(f o g(n)) = Omega(R(f) center dot R(g)) holds for a relation f subset of {0,1}(n) x S and a total inner function g: {0,1}(m) -> {0, 1}. Composition theorems of the form R(f o g(n)) = Omega(R(f) center dot M(g)) are known for various measures M. Such measures include the sabotage complexity RS defined by Ben-David and Kothari (ICALP 2015), the max-conflict complexity defined by Gavinsky, Lee, Santha and Sanyal (ICALP 2019), and the linearized complexity measure defined by Ben-David, Blais, Goos and Maystre (FOCS 2022). The above measures are asymptotically non-decreasing in the above order. However, for total Boolean functions no asymptotic separation is known between any two of them. Let D-prod denote the maximum distributional querycomplexity with respect to any product (over variables) distribution. In this work we show that for any total Boolean function g, the sabotage complexity RS(g) = (Omega) over tilde (D-prod (g)). This gives the composition theorem R(f o g(n)) = (R(f) center dot D-prod (g)) In light of the minimax theorem which states that R(g) is the maximum distributional complexity of g over any distribution, our result makes progress towards answering the composition question. We prove our result by means of a complexity measure R-epsilon(prod) that we define for total Boolean functions. Informally, R-epsilon(prod) (g) is the minimum complexity of any randomized decision tree with unlabelled leaves with the property that, for every product distribution it over the inputs, the average bias of its leaves is at least ((1 - epsilon) - epsilon)/2 = 1/2 - epsilon. It follows by standard arguments R-1/3(prod)(g) = Omega(D-prod (g)). We show that R-1/3(prod) is equivalent to the sabotage complexity up to a logarithmic factor. Ben-David and Kothari asked whether RS(g) = Theta(R(g)) for total functions g. W
We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions and are equal to the fractional block sensitivity fbs(f). That includes the Kolmogorov complexi...
详细信息
We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions and are equal to the fractional block sensitivity fbs(f). That includes the Kolmogorov complexity bound of Laplante and Magniez and the earlier relational adversary bound of Aaronson. This equivalence also implies that for total functions, the relational adversary is equivalent to a simpler lower bound, which we call rank-1 relational adversary. For partial functions, we show unbounded separations between fbs(f) and other adversary bounds, as well as between the adversary bounds themselves. We also show that, for partial functions, fractional block sensitivity cannot give lower bounds larger than root ***(f), where n is the number of variables and bs(f) is the block sensitivity. Then, we exhibit a partial function f that matches this upper bound, fbs(f) = Omega(root ***(f)).
We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions, and are equal to the fractional block sensitivity fbs(f). That includes the Kolmogorov complex...
详细信息
ISBN:
(纸本)9783959770620
We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions, and are equal to the fractional block sensitivity fbs(f). That includes the Kolmogorov complexity bound of Laplante and Magniez and the earlier relational adversary bound of Aaronson. For partial functions, we show unbounded separations between fbs( f) and other adversary bounds, as well as between the relational and Kolmogorov complexity bounds. We also show that, for partial functions, fractional block sensitivity cannot give lower bounds larger than root ***(f), where n is the number of variables and bs(f) is the block sensitivity. Then we exhibit a partial function f that matches this upper bound, fbs(f) = Omega 2 (root ***(f)).
暂无评论