Chcę się dowiedzieć o algorytmach algebraicznych i złożoności tysiąca. W szczególności interesuje mnie PIT.
Czy istnieje zestaw notatek z wykładów, książek, prac i ankiet dla studentów, którzy przeczytali standardowy podręcznik o teorii, taki jak książka Sipsera lub podręcznik złożoności Arory-Baraka.
Zestaw referencji będzie zawierał najnowsze zaawansowane wyniki.
Odpowiedzi:
Ogromna księga Burgissera-Clausena-Shokrollahi jest standardowym odniesieniem do teorii złożoności algebraicznej (i nie jestem do końca pewna, czy istnieją inne z punktu widzenia złożoności, chociaż zdecydowanie istnieją inne dotyczące algorytmów algebraicznych), ale nie robi tego dużo PIT.
Ankiety Chen-Kayal-Wigderson ( bezpłatnie dostępne ze strony Wigderona ) i Shpilka-Yehudayoff ( dostępne bezpłatnie ze strony Shpilka ) obejmują znacznie więcej ostatnich wyników dotyczących dolnych granic i derandomizacji PIT dla małych klas obwodów algebraicznych.
Adres ICM Agrawal z 2006 r. Daje dobry przegląd problemu permanentnego w porównaniu z determinantem i pomimo tego, że ma 8 lat, jest wciąż dość aktualny. (Myślę, że jedyną najnowszą dolną granicą jest Landsberg-Manivel-Ressayre , która ma tę samą dolną granicę, ale dla przybliżonej złożoności determinantej zamiast po prostu determinantycznej złożoności.)