
PreviousNext
We study the complexity of finding the values and optimal strategies of
MEAN PAYOFF GAMES on graphs, a family of perfect information games
introduced by Ehrenfeucht and Mycielski and considered by Gurvich,
Karzanov and Khachiyan. We describe a pseudo-polynomial time algorithm
for the solution of such games, the decision ...
more >>>
This paper studies distributions which
can be ``approximated'' by sampling algorithms in time polynomial in
the length of their outputs. First, it is known that if
polynomial-time samplable distributions are polynomial-time
computable, then NP collapses to P. This paper shows by a simple
...
more >>>
We consider noninteractive zero-knowledge proofs in the shared random
string model proposed by Blum, Feldman and Micali \cite{bfm}. Until
recently there was a sizable polynomial gap between the most
efficient noninteractive proofs for {\sf NP} based on general
complexity assumptions \cite{fls} versus those based on specific
algebraic assumptions \cite{Da}. ...
more >>>
PreviousNext