Description
Egy n-változós Boole-függvény érzékenysége egy adott x inputon azon bitjeinek száma, amit megváltoztatva a függvény értéke is
megváltozik. A függvény érzékenysége a legnagyobb érzékenység a 2^n input között. A blokk-érzékenység ennek egy általánosítása: bitek helyett bit-blokkok megfordításával kell az értéket megváltoztatni és a páronként diszjunkt blokkok számát maximalizáljuk.
Technikailag nagyon hasznos fogalom legalább akkora mint az érzékenység. Sokan azt gondolták, hogy sokkal nagyobb nem is lehet.
Szegedy és Nisan 1994-ben sejtette, hogy az érzékenység és blokk-érzékenység közötti kapcsolat polinomiális. Több mint 25
évig a sejtés egy központi megoldatlan probléma volt. 2019-ben Huang megoldotta a sejtést egyszerű érveléssel, ami BSc-s lineáris algebrai ismeretekre támaszkodott.
Az előadás a kérdés hátteréről, példákról és a megoldásról szól.