Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with samplable distribution:
TR11-167 | 6th December 2011
Nikolay Vereshchagin

Improving on Gutfreund, Shaltiel, and Ta-Shma's paper "If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances''

Revisions: 1

Assume that $NP\ne RP$. Gutfreund, Shaltiel, and Ta-Shma in [Computational Complexity 16(4):412-441 (2007)] have proved that for every randomized polynomial time decision algorithm $D$ for SAT there is a polynomial time samplable distribution such that $D$ errs with probability at least $1/6-\epsilon$ on a random formula chosen with respect to ... more >>>

TR22-010 | 18th January 2022
Marshall Ball, Dana Dachman-Soled, Julian Loss

(Nondeterministic) Hardness vs. Non-Malleability

We present the first truly explicit constructions of \emph{non-malleable codes} against tampering by bounded polynomial size circuits. These objects imply unproven circuit lower bounds and our construction is secure provided E requires exponential size nondeterministic circuits, an assumption from the derandomization literature.

Prior works on NMC ... more >>>

ISSN 1433-8092 | Imprint