Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, November 14, 2013, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Nemanja Skoric
"Can randomness help computation?" and "Do natural hard problems exist?" are some of the most important questions in theoretical computer science. It turns out there is a surprising connection between these two.
It is reasonable to think that simulating a probabilistic algorithm with a deterministic one, requires significant loss in efficiency. However, there is evidence that this is not true. Under widely believed assumptions, BPP = P, where BPP is the class of problems computable by randomized polynomial algorithms, with an error probability of at most 1/3. Following a series of papers by Blum. Micali, Yao, Nisan, Wigderson, Impagliazzo et al. it was shown in '97 that if there is a problem computable in deterministic time 2 c n, for some constant c, which can not be computed by a circuit of size 2 d n, for some constant d, then BPP = P.
In this talk, we will present a high-level picture of the work by Nisan and Wigderson '94, which shows a weaker statement than the one above. Namely, under the assumption that a problem computable in time 2c n can not be approximated by a circuit of size 2d n, BPP = P.
Automatic MiSe System Software Version 1.4803M | admin login