Unique Games Conjecture i trudność aproksymacji

Począwszy od sławnego twierdzenia PCP, do dnia dzisiejszego znamy bardzo dużo wyników dowodzących trudność aproksymacji różnych problemów. O ile dowodzenie braku istnienia PTASa jest zazwyczaj mniej lub bardziej skomplikowaną redukcją kombinatoryczną, o tyle otrzymani ścisłych oszacowań, pokrywających się z najlepszymi znanymi algorytmami aproksymacyjnymi, wymaga często zaawansowanych technik z rachunku prawdopodobieństwa i analizy fourierowskiej. W czasie referatu zaszkicuję historię tej dziedziny, pokażę podstawowe techniki oraz postaram się uzasadnić znaczenie hipotezy Unique Games. Referat powstał w oparciu o warsztaty dotyczące trudności aproksymacji, które organizowaliśmy z Markiem Cyganem, Michałem Pilipczukiem i Jakubem Wojtaszczykiem.