W tym miejscu umieszczamy materiały, które mogą stanowić bazę do przygotowywanego referatu.
Zagadnienia wybrane przez Damiana Niwińskiego:
- Zhen Zhang, Raymond W. Yeung,
On Characterization of Entropy Function via Information Inequalities,
IEEE Trans. Inf. Theory 44(4): 1440-1452 (1998)
https://www.cs.cornell.edu/courses/cs783/2007fa/papers/ZYnonShannon.pdf
Przełomowa praca odkrywająca nierówność entropijną, która nie wynika z podstawowych praw określonych przez Shannona. - Mahmoud Abo Khamis, Phokion G. Kolaitis, Hung Q. Ngo, Dan Suciu,
Decision Problems in Information Theory. ICALP 2020: 106:1-106:20
https://drops.dagstuhl.de/opus/volltexte/2020/12513/pdf/LIPIcs-ICALP-2020-106.pdf
Praca podejmuje problem algorytmicznej rozstrzygalności nierówności wiążących entropię. - Jarek Duda,
Asymmetric numeral systems: entropy coding combining speed of Huffman
coding with compression rate of arithmetic coding
https://arxiv.org/abs/1311.2540
Praca wprowadziła odkrywczą metodę kompresji tekstów opartą o tzw. asymetryczne systemy liczbowe, która połączyła algorytmiczną efektywność kodów Huffmana z jakością kompresji kodowania arytmetycznego. Technika została zastosowana w jądrze Linuxa, ale także w systemach używanych przez koncerny Google, Facebook, Apple i Dropbox. - Yanyi Liu, Rafael Pass,
On the Possibility of Basing Cryptography on EXP =/= BPP
https://eccc.weizmann.ac.il/report/2021/056/
Praca pokazuje, że istnienie funkcji jednokierunkowych -- co stanowi centralną hipotezę kryptografii asymetrycznej -- można oprzeć na pewnej hipotezie dotyczącej złożoności informacyjnej Kołmogorowa. - Hao Huang,
Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture
https://arxiv.org/pdf/1907.00847.pdf
Czułość funkcji boolowskich. Zaskakujące rozwiązanie 30-letniej hipotezy: dla danej funkcji boolowskiej szacujemy minimalną liczbę bitów o tej własności, że zmiana jednego z nich spowoduje zmianę wartości funkcji. Rozwiązanie używa pięknego argumentu geometrycznego. Oryginalny artykuł Hao Huanga, omówienie w Delcie 1, 2:
http://www.deltami.edu.pl/temat/matematyka/logika/2020/06/29/czulosc-funkcji-logicznych/
http://www.deltami.edu.pl/temat/matematyka/logika/2020/07/28/czulosc-funkcji-logicznych-ii/ - Rozdziały z książki
Thomas M. Cover, Joy A. Thomas, Elements of Information Theory, 2nd Edition
https://www.wiley.com/en-us/Elements+of+Information+Theory%2C+2nd+Edition-p-9780471241959
Wybrane tematy nie objęte programem wykładu Teoria informacji, jak w szczególności związki z błądzeniem losowym i drugą zasadą termodynamiki (rozdz. 4), entropią języka naturalnego (rozdz. 6), przesyłaniem wiadomości w sieci (rozdz. 15).
Zagadnienia wybrane przez Eryka Kopczyńskiego:
- Galanis, Goldberg, Guo, Yang,
Counting Solutions to Random CNF Formulas
https://drops.dagstuhl.de/opus/volltexte/2020/12460/pdf/LIPIcs-ICALP-2020-53.pdf
Praca porusza ciekawy problem spełnialności dla losowej formuły k-SAT. - Martin Grohe, Pascal Schweitzer, Daniel Wiebking,
Deep Weisfeiler Leman
https://arxiv.org/pdf/2003.10935.pdf
Podejście do problemu izomorfizmu grafów.
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.