Unit:
Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και ΥπολογισμούLibrary of the School of Science
Author:
Τέντες Αριστείδης
Supervisors info:
Ευστάθιος Ζάχος Καθηγητής (Επιβλέπων), Α. Παγουρτζής Αναπλ. Καθηγητής , Δ. Φωτάκης Λέκτορας
Original Title:
Expander graphs, randomness extractors and error correcting codes
Translated title:
Expander Γράφοι, Εξαγωγή Τυχαιότητας και Κώδικες Διόρθωσεις Λαθών με Λίστα
Summary:
The purpose of this thesis is to introduce three important notions of
Complexity, Cryptography and generally Pseudorandomness. We survey the notions
of Expander Graphs, Randomness Extractors and List Decodable Error Correcting
Codes. The former are graphs that on the one hand are very sparse, namely they
do not have many edges, yet on the other hand are very well connected.
Randomness Extractors are function that take as input a string of imperfect
randomness and output a (close to) uniformly random string. List Decodable
Error Correcting Codes have seemingly little relevance with Pseudorandomness.
They try to solve the problem of communication over a network that introduces
higher noise than can be tolerated by simple Error Correcting Codes. The
decoding procedure does not uniquely decode a codeword, but rather gives a list
that includes the original message.
All three objects have their own body of research, each one with seemingly
irrelevant techniques. However, it can be shown that they can be expressed in
terms of the other. That is, Expander Graphs and Randomness Extractors can be
expressed in the language of List Decodable Error Correcting Codes and vice
versa.
Keywords:
Pseudorandomness, Complexity Theory, Expander Graphs, Randomness Extractors, List Decodable Error Correcting Codes
