W tym miejscu umieszczamy materiały, które mogą stanowić bazę do przygotowywanego referatu.

Zagadnienia wybrane przez Damiana Niwińskiego:

Zagadnienia wybrane przez Eryka Kopczyńskiego:

Zagadnienia wybrane przez Tomasza Kazanę:

  • Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett, Non-malleable Codes from Additive Combinatorics
    https://eprint.iacr.org/2013/201.pdf

    Kody niekowalne to kody o pewnych specyficznych własnościach. Można zauważyć (metodami erdosewskimi), że niemal każdy kod jest niekowaly. Mimo to pokazanie konkretnych przykładów stanowiło wyzwanie dla wielu badaczy ostatnich lat. Ta praca stanowi przykład takiej konstrukcji, dodatkowo korzystający z metod (interesującej samej w sobie) tzw. kombinatoryki addytywnej.

  • Andrzej Grzesik, Daniel Kral, Laszlo Miklos Lovasz, Elusive extramal graphs
    https://arxiv.org/abs/1807.01141

    Interesująca praca, po lekturze której można się zaznajomić z dziwnymi tworami, czyli tzw. grafonami, a więc gigantycznymi grafami o nieprzeliczalnej liczbie wierzchołków.

  • Craig Gentry, Computing Arbitrary Functions of Encrypted Data
    https://crypto.stanford.edu/craig/easy-fhe.pdf

    Craig Gentry rozwiązał długo otwarty problem istnienia tzw. w pełni homomorficznego szyfrowania (FHE), umożliwiającego obliczenia na zaszyfrowanych danych. Dzięki FHE jest już teoretycznie (choć na razie nie zadawalająco efektywnie) możliwe np. zadanie zapytań do wyszukiwarki internetowej w taki sposób, że użytkownik dostaje poprawną odpowiedź, pomimo że serwer nawet nie wie, o co jest pytany! Proponowana praca to uproszczona wersja oryginalnej pracy, napisana przez samego autora.

  • Ronald de Wolf, A Brief Introduction to Fourier Analysis on the Boolean Cube
    https://theoryofcomputing.org/articles/gs001/gs001.pdf

    Praca pokazująca, że analiza Fouriera nie musi się kojarzyć z funkcjami ciągłymi, a może dotyczyć dyskretnych obiektów. Metody pokazane w tej pracy wydają się mieć bardzo duży potencjał w szeroko rozumianej informatyce teoretycznej. Lektura proponowanej pracy może znacząca poszerzyć warsztat narzędziowy prelegenta.

  • Eshan Chattopadhyay, David Zuckerman, Explicit two-source extractors and resilient functions
    https://annals.math.princeton.edu/2019/189-3/p01

    Ważna i przełomowa praca z dziedziny ekstraktorów, a więc funkcji, które ze ,,słabej'' losowości produkują ,,lepszą'' losowość. Prostym przykładem tego typu obiektu jest konstrukcja von Neumanna dotycząca symulacji prawdziwej monety za pomocą monety niesymetrycznej.

  • Kai-Min Chung, Rafael Pass, The Randomness Complexity of Parallel Repetition
    https://www.cs.cornell.edu/~rafael/papers/rand-para.pdf

Konferencje naukowe:

Odczyty z następujących konferencji mogą być warte uwagi:
FOCS, STOC, ISIT, ITCS, RANDOM, SODA, CCC, ITC, TCC.