2019. 11. 08. 10:00 - 2019. 11. 08. 12:00
Szeged, Bolyai Intézet, Bolyai Épület, I. emelet, Riesz terem, Aradi vértanúk tere 1.
-
-
-
-
Esemény típusa: szeminárium
Szervezés: Külsős
-
-

Leírás

SZTE, TTIK, Bolyai Intézet, Kombinatorika szeminárium

Absztrakt. Nagyon sok mód van Boole-függvények bonyolultságának mérésére. A 80-as évektől kezdődően mind a mai napig aktív kutatási területről van szó.
Döntési fa bonyolultság (determinisztikus/nem-determinisztikus), valós-fokszám, blokk-érzékenység, érzékenység egy olyan csoport, amely tagjai nagyon szoros kapcsolatban vannak. Az érzékenység kivételével rég óta tudjuk, hogy a többi polinomiális kapcsolatban van egymással. A `sensitivity conjecture' a 90-es évekből ered és azt mondja, hogy az érzékenység is polinomiális kapcsolatban áll a többivel.
Ezt oldotta meg Huang az idén. Erről lesz szó.