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 :
Reports
Complete list of metadatas

Cited literature [4 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102308
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 11:09:01 AM
Last modification on : Friday, April 19, 2019 - 1:38:16 AM

File

RR2006-27.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102308, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

3

Files downloads

10