On the probabilistic query complexity of transitively symmetric problems

Abstract : We obtain optimal lower bounds on the nonadaptive probabilistic query complexityof a class of problems defined by a rather weak symmetry condition. Infact, for each problem in this class, given a number T of queries we computeexactly the performance (i.e., the probability of success on the worst instance)of the best nonadaptive probabilistic algorithm that makes T queries. We showthat this optimal performance is given by a minimax formula involving certainprobability distributions. Moreover, we identify two classes of problems forwhich adaptivity does not help.We illustrate these results on a few natural examples, including unorderedsearch, Simon’s problem, distinguishing one-to-one functions from two-to-onefunctions, and hidden translation. For these last three examples (which are ofparticular interest in quantum computing), the recent theorems of Aaronson,of Laplante and Magniez, and of Bar-Yossef, Kumar and Sivakumar on theprobabilistic complexity of black-box problems do not yield any nonconstantlower bound.
Document type :
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 11:09:01 AM
Last modification on : Wednesday, November 20, 2019 - 7:24:07 AM


Files produced by the author(s)


  • HAL Id : hal-02102308, version 1



Pascal Koiran, Vincent Nesme, Natacha Portier. On the probabilistic query complexity of transitively symmetric problems. [Research Report] LIP RR-2006-27, Laboratoire de l'informatique du parallélisme. 2006, 2+18p. ⟨hal-02102308⟩



Record views


Files downloads