Dobry tekst o wprowadzeniu do złożoności obwodu

Chciałbym zapytać o dobre teksty wprowadzające złożoność obwodu. Pomocne będą również wszelkie wskazówki dotyczące ostatnich postępów i otwartych problemów w tej dziedzinie.

Na początek jest oczywiście książka Arory i Baraka Computational Complexity: A Modern Approach . Stamtąd części 3 i 4 książki Jukny Boolean Function Complexity: Advances and Frontiers stanowią doskonały materiał do czytania. Ponadto Ryan Williams prowadzi fajny kurs na temat złożoności obwodów, którego notatki z kursu mogą być umieszczone online :)

Oprócz tych sugerowanych przez Arnaba poleciłbym również następującą książkę:

Wprowadzenie do złożoności obwodu: jednolite podejście autorstwa Heriberta Vollmera

Modele obliczeń autorstwa Johna E. Savage'a (więcej informacji / szczegółów / recenzji na amazon ). jest to w dużej mierze podręcznik dla studentów, ale wyróżnia się z punktu widzenia obwodu. zawiera wiele zaawansowanych tematów / dowodów i jest bezpłatny w Internecie i jest bardzo dobrze połączony za pomocą hiperłącza (spis treści, referencje, indeks itp.).