All reports by Author Nicollas Sdroievski:

__
TR18-193
| 14th November 2018
__

Nicollas Sdroievski, Murilo Silva, AndrĂ© Vignatti#### The Hidden Subgroup Problem and MKTP

Nicollas Sdroievski, Murilo Silva, AndrĂ© Vignatti

We show that the Hidden Subgroup Problem for black-box groups is in $\mathrm{BPP}^\mathrm{MKTP}$ (where $\mathrm{MKTP}$ is the Minimum $\mathrm{KT}$ Problem) using the techniques of Allender et al (2018). We also show that the problem is in $\mathrm{ZPP}^\mathrm{MKTP}$ provided that there is a \emph{pac overestimator} computable in $\mathrm{ZPP}^\mathrm{MKTP}$ for the logarithm ... more >>>