National and Kapodistrian University of Athens
Expander graphs, randomness extractors and error correcting codes
Abstract
dc:descriptionΟ σκοπός της εργασίας είναι να κάνει μια εισαγωγή από τρεις έννοιες που είναι σημαντικές στη Θεωρία Πολυπλοκότητας, στην Κρυπτογραφία αλλά και στη Θεωρία Ψευδοτυχαιότητας γενικότερα. Οι έννοιες αυτές είναι οι Expander Γράφοι, Εξαγωγή Τυχαιότητας και Κώδικες Διόρθωσης Λαθών με Λίστα. Οι expander γράφοι έχουν την ιδιότητα ότι αποτελούνται απο λίγες ακμές όμως οι κορυφές τους είναι πολύ καλά συνδεδεμένοι. Ένας αλγόριθμος εξάγει τυχαιότητα όταν παίρνει σαν είσοδο μία ακολοθία που δεν έχει τέλεια τυχαιότητα και επιστρέφει μία άλλη ακολουθία που είναι σχεδόν τυχαία. Οι Κώδικες Διόρθωσης Λαθών με Λίστα ίσως να φαίνεται ότι δεν έχουν άμεση σχέση με τη θεωρία Ψευδοτυχαιότητας. Χρησιμοποιούνται για να λύσουν το πρόβλημα επικοινωνίας σε ένα δίκτυο το οποίο μπορεί να εισάγει θόρυβο μεγαλύτερο από αυτόν που μπορούν να αφαιρέσουν οι απλοί Κώδικες Διόρθωσης Λαθών. Η αποκωδικοποίηση σε αυτήν την περίπτωση δε γίνεται με την επιστροφη μίας μοναδικής λέξης, αλλά με την επιστροφή μίας λίστας λέξεων η οποία σίγουρα θα περιέχει την αρχική λέξη. Η καθεμία από αυτές τις τρεις έννοιες έχει μελετηθεί ξεχωριστά, χρησιμοποιώντας αρκετά διαφορετικές τεχνικές. Ωστόσο, υπάρχει τρόπος να εκφραστεί η καθεμία ως περίπτωση της άλλης. Πιο συγκεκριμένα οι expander γράφοι και αλγόριθμοι εξαγωγής τυχαιότητας μπορούν να εκφραστούν σαν Κώδικες Διόρθωσης Λαθών με Λίστα και το αντίστροφο.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Τέντες Αριστείδης
Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:1321056