Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 02, 2015, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Malte Milatz
If P is some non-trivial monotone graph property, the evasiveness conjecture states that any deterministic algorithm to decide P must in the worst case query all the edges of the input graph.
In the 1980s the conjecture was proved for the case where the number of vertices is a prime power. In this talk we will have a look at this proof, so as to understand the role of that peculiar hypothesis.
Automatic MiSe System Software Version 1.4803M | admin login