ECCC-Report TR18-193https://eccc.weizmann.ac.il/report/2018/193Comments and Revisions published for TR18-193en-usSun, 18 Nov 2018 07:11:37 +0200-
Paper TR18-193
| The Hidden Subgroup Problem and MKTP |
Nicollas Sdroievski,
Murilo Silva,
AndrĂ© Vignatti
https://eccc.weizmann.ac.il/report/2018/193We 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 of the order of the given black-box group. This last result implies that for permutation groups, the dihedral group and many types of matrix groups the problem is in $\mathrm{ZPP}^\mathrm{MKTP}$. Lastly, we also show that two decision versions of the problem admit statistical zero knowledge proofs. These results help classify the relative difficulty of the Hidden Subgroup Problem.Sun, 18 Nov 2018 07:11:37 +0200https://eccc.weizmann.ac.il/report/2018/193