Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MACHINES THAT TAKE ADVICE:
Reports tagged with machines that take advice:
TR02-039 | 30th June 2002
Oded Goldreich, Avi Wigderson

#### Derandomization that is rarely wrong from short advice that is typically good

For every $\epsilon>0$,
we present a {\em deterministic}\/ log-space algorithm
that correctly decides undirected graph connectivity
on all but at most $2^{n^\epsilon}$ of the $n$-vertex graphs.
The same holds for every problem in Symmetric Log-space (i.e., $\SL$).

Making no assumptions (and in particular not assuming the ... more >>>

TR05-018 | 6th February 2005
Oded Goldreich

#### On Promise Problems (a survey in memory of Shimon Even [1935-2004])

The notion of promise problems was introduced and initially studied
by Even, Selman and Yacobi
(Information and Control, Vol.~61, pages 159-173, 1984).
notion has found in the twenty years that elapsed.
These include the notion ... more >>>

ISSN 1433-8092 | Imprint