Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ERRORLESS HEURISTICS:
Reports tagged with errorless heuristics:
TR08-073 | 4th August 2008
Dmitry Itsykson

Structural complexity of AvgBPP

We study class AvgBPP that consists of distributional problems that can be solved in average polynomial time (in terms of Levin's average-case complexity) by randomized algorithms with bounded error. We prove that there exists a distributional problem that is complete for AvgBPP under polynomial-time samplable distributions. Since we use deterministic ... more >>>




ISSN 1433-8092 | Imprint