Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > POLYNOMIAL-TIME SAMPLABLE DISTRIBUTIONS:
Reports tagged with polynomial-time samplable distributions:
TR09-023 | 12th March 2009
Akinori Kawachi, Osamu Watanabe

Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems

Impagliazzo and Levin demonstrated [IL90] that the average-case hardness of any NP-search problem under any P-samplable distribution implies that of another NP-search problem under the uniform distribution. For this they developed a way to define a reduction from an NP-search problem F with ``mild hardness'' under any P-samplable distribution H; ... more >>>




ISSN 1433-8092 | Imprint