Hardness as randomness: a survey of universal derandomization

Details Hardness as randomness: a survey of universal derandomization Hardness as randomness: a survey of universal derandomization

2003-04-28

arxiv.org/abs/cs/0304040v1

Proceedings of the ICM, Beijing 2002, vol. 3, 659--672

Computer Science

Computational Complexity

Scientific paper

We survey recent developments in the study of probabilistic complexity classes. While the evidence seems to support the conjecture that probabilism can be deterministically simulated with relatively low overhead, i.e., that $P=BPP$, it also indicates that this may be a difficult question to resolve. In fact, proving that probabilistic algorithms have non-trivial deterministic simulations is basically equivalent to proving circuit lower bounds, either in the algebraic or Boolean models.

Affiliated with

Also associated with

No associations

Rating

Hardness as randomness: a survey of universal derandomization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hardness as randomness: a survey of universal derandomization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardness as randomness: a survey of universal derandomization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-333836