Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-108 | 16th July 2016 00:32

Discrete Logarithm and Minimum Circuit Size

RSS-Feed




TR16-108
Authors: Michael Rudow
Publication: 17th July 2016 23:46
Downloads: 1835
Keywords: 


Abstract:

This paper shows that the Discrete Logarithm Problem is in ZPP^(MCSP) (where MCSP is the Minimum Circuit Size Problem). This result improves the previous bound that the Discrete Logarithm Problem is in BPP^(MCSP) Allender et al. (2006). In doing so, this paper helps classify the relative difficulty of the Minimum Circuit Size Problem.



ISSN 1433-8092 | Imprint