Back to search

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

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Τέντες Αριστείδης. Expander graphs, randomness extractors and error correcting codes. 2009. https://pergamos.lib.uoa.gr/uoa/dl/object/1321056