Relacja z konferencji FOCS’89
Już od ponad dwudziestu lat do najbardziej prestiżowych konferencji w świecie w dziedzinie informatyki teoretycznej należą Symposium on Theory of Computing (STOC) oraz Symposium on Foundations of Computer Science (FOCS). Pierwsza z tych konferencji jest sponsorowana przez ACM, druga zaś — przez IEEE. Ponadto każdorazowo konferencje te uzyskują dodatkowe wsparcie, najczęściej z przemysłu. FOCS’89 sponsorowały m. in. IBM, AT&T Bell Laboratories, Xerox, DEC, Hewlett–Packard oraz wydawnictwo Springera.
Konferencje odbywają się corocznie: STOC wiosną, FOCS — jesienią i trwają trzy, cztery dni. Miejscem spotkania są z zasady renomowane ośrodki akademickie w USA.
Na przestrzeni lat główna tematyka konferencji STOC i FOCS ulegała zmianom. Zawsze jednak należały do niej zarówno klasyczne działy informatyki teoretycznej, hak i najnowsze tendencje w tej dziedzinie. W ostatnich latach program konferencji obejmował: algorytmy i struktury danych, języki formalne, teorię obliczeń i złożoność obliczeniową, kryptografię, bazy danych, obliczenia równoległe, geometrię obliczeniową, logikę i semantykę programów, uczenie się maszyn, obliczenia VLSI i robotykę.
Trzydzieste, jubileuszowe sympozjum FOCS odbyło się w Research Triangle Park (North Carolina) w dniach od 30 października do 1 listopada 1989 roku. Na obrzeżach parku są trzy miasta i trzy uczelnie: Duke University w Durham, University of North Carolina w Chapel Hill oraz North Carolina State University w Raleigh. Na terenie parku znajduje się stanowe centrum mikroelektroniki, zaliczane do najlepszych w USA. Miejscem spotkania FOCS’89 był Sheraton Imperial Hotel, w którym także mieszkali wszyscy uczestnicy. Miłą atrakcją konferencji był bankiet w klubie golfowym Duke University, na którym to bankiecie nie zabrakło toastów, przemówień i tortu z 30 świeczkami dla jubilata.
Komitet programowy FOCS’89, w składzie: Alok Aggarwal, Eric Bach, Zvi Galil, Juris Hartmanis, Charles Leiserson, Rohit Parikh, Nicholas Pippenger, Charles Rackoff, Ray Strong, Robert Tarjan, Mihalis Yannakkais i Frances Yao, wybrał 100 prac spośród rekordowej liczby 273 zgłoszonych na konferencję. Rozszerzone streszczenia prezentowanych prac zostały opublikowane przez organizatorów. Podobnie jak w latach ubiegłych, tegoroczne spotkanie FOCS zdominowały czołowe amerykańskie ośrodki badawcze: MIT, IBM, Stanford, Princeton i Berkeley. Silną reprezentację miały także Cornell i Chicago University. Przyjmując za kryterium miejsce, gdzie ludzie pracują, a nie ich narodowość, otrzymujemy następujące podsumowanie, w którym pierwsza liczba oznacza liczbę uczestników konferencji, druga zaś, chyba bardziej znacząca, liczbę autorów prac prezentowanych na FOCS’89. Wspólne prace są dzielone równo pomiędzy autorów. Oto dane: Francja (1; 0), Grecja (2; 1/3), Hiszpania (0; 1/3), Holandia (2; 1/2), Izrael (6; 7), Japonia (2; 1), Kanada (15; 5), Polska (3; 2), w tym: Uniwersytet Wrocławski (3; 1 1/2), WSP Opole (0; 1/2); RFN (8; 5), Szwajcaria (17 0), Węgry (0; 2 1/3), Włochy (3; 1/2), USA (347; 76), w tym: MIT (29; 7 5/6), IBM (17; 7), Stanford (15; 6 1/6), Princeton (10; 6), Berkeley (7; 5), Chicago (9; 4 3/4), Cornell (10; 4 1/2), Harvard (6; 2 1/2), AT&T Labs. (9; 2 1/2).
Program tegorocznego FOCS był bogatszy niż zwykle, w latach ubiegłych prezentowano zazwyczaj ok. 60 prac. Chociaż dominowały prace z algorytmów i struktur danych, obliczeń równoległych, geometrii obliczeniowej i uczenia się maszyn, to największe zainteresowanie uczestników FOCS wzbudziła praca Japończyka Tody z Tokio na temat strukturalnej złożoności obliczeniowej. Był to chyba jedyny referat, podczas którego na sali wykładowej zabrakło dla słuchaczy miejsc siedzących. Autor wykazał, że wszystkie problemu z hierarchii wielomianowej można zredukować wielomianowo (w sensie Turinga) do problemów z klasy PP.
Duża liczba reprezentowanych prac była poświęcona projektowaniu i analizie algorytmów równoległych. Pokazano np. efektywne NC algorytmy równoległe dla problemów: pokrycia wierzchołkowego grafu, testowania, czy dany graf jest k–wierzchołkowo spójny, znajdowania rozłącznych ścieżek w grafie oraz maksymalnego przepływu w sieci. Dzięki użyciu wyrafinowanych technik autorom kilku prezentowanych prac udało się otrzymać algorytmy optymalne, pozostałym zaś — algorytmy efektywniejsze niż dotychczas znane. John Reif i Vijaya Ramachandran skonstruowali np. taki optymalny NC algorytm, o złożoności czasowej log n, do testowania planarności grafu.
Oprócz algorytmów rozwiązujących konkretne problemy na konferencji pokazano także pewne ogólne techniki umożliwiające tworzenie efektywnych algorytmów równoległych NC. Zademonstrowano np. techniki zamiany losowych algorytmów równoległych RNC na algorytmy deterministyczne. Praca Bonnie Bergera i Johna Rompela z MIT, poświęcona takiej konwersji, została uznana przez komitet organizacyjny FOCS za najlepszą pracę konferencji napisaną wyłącznie przez studenta lub studentów, a jej autorzy zostali uhonorowani nagrodą Machteya.
Z dziedziny geometrii obliczeniowej przedstawiono kilka ciekawych rezultatów. Bernard Chazelle pokazał optymalny, liniowy algorytm dla problemu znajdowania części wspólnej dwóch wielościanów wypukłych w przestrzeni trójwymiarowej. Algorytm ten jest szybszy niż znany dotychczas o czynnik log n. Ponieważ algorytm jest dość prosty i nie wymaga skomplikowanych struktur danych, można go z powodzeniem stosować w praktyce. Znaczący jest także wynik udowodniony przez Janosa Pacha, Wiliama Steigera i Endre Szemerediego, ulepszający o czynnik log * n górną granicę liczby planarnych k–zbiorów uzyskanej w roku 1973 przez Erdösa, Lovasza, Simmonsa i Strausa.
Duża liczba prac była poświęcona uczeniu się maszyn. Między innymi Robert Shapire, Ming Li i Paul Vitanyi, a następnie D. Haussler, badali pewne warianty modelu PAC dla algorytmów samouczących się.
Na konferencji były także prezentowane prace m. in. z kryptografii, “Zero–Knowledge”, algorytmów VLSI i obwodów logicznych. Odbyła się także duża sesja poświęcona logice w informatyce.
Maciej Liśkiewicz
