
PreviousNext
It is known that there exists a PCP characterization of NP
where the verifier makes 3 queries and has a {\em one-sided}
error that is bounded away from 1; and also that 2 queries
do not suffice for such a characterization. Thus PCPs with
3 ...
more >>>
Let G be a finite cyclic group with generator \alpha and with
an encoding so that multiplication is computable in polynomial time. We
study the security of bits of the discrete log x when given \exp_{\alpha}(x),
assuming that the exponentiation function \exp_{\alpha}(x) = \alpha^x is one-way.
...
more >>>
A Uniform Generation procedure for $NP$ is an
algorithm which given any input in a fixed NP-language, outputs a uniformly
distributed NP-witness for membership of the input in the language.
We present a Uniform Generation procedure for $NP$ that runs in probabilistic
polynomial-time with an NP-oracle. This improves upon ...
more >>>
PreviousNext