{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1321056"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1321056","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Expander graphs, randomness extractors and error correcting codes","abstract":"Ο σκοπός της εργασίας είναι να κάνει μια εισαγωγή από τρεις έννοιες που είναι σημαντικές στη Θεωρία Πολυπλοκότητας, στην Κρυπτογραφία αλλά και στη Θεωρία Ψευδοτυχαιότητας γενικότερα. Οι έννοιες αυτές είναι οι Expander Γράφοι, Εξαγωγή Τυχαιότητας και Κώδικες Διόρθωσης Λαθών με Λίστα. Οι expander γράφοι έχουν την ιδιότητα ότι αποτελούνται απο λίγες ακμές όμως οι κορυφές τους είναι πολύ καλά συνδεδεμένοι. Ένας αλγόριθμος εξάγει τυχαιότητα όταν παίρνει σαν είσοδο μία ακολοθία που δεν έχει τέλεια τυχαιότητα και επιστρέφει μία άλλη ακολουθία που είναι σχεδόν τυχαία. Οι Κώδικες Διόρθωσης Λαθών με Λίστα ίσως να φαίνεται ότι δεν έχουν άμεση σχέση με τη θεωρία Ψευδοτυχαιότητας. Χρησιμοποιούνται για να λύσουν το πρόβλημα επικοινωνίας σε ένα δίκτυο το οποίο μπορεί να εισάγει θόρυβο μεγαλύτερο από αυτόν που μπορούν να αφαιρέσουν οι απλοί Κώδικες Διόρθωσης Λαθών. Η αποκωδικοποίηση σε αυτήν την περίπτωση δε γίνεται με την επιστροφη μίας μοναδικής λέξης, αλλά με την επιστροφή μίας λίστας λέξεων η οποία σίγουρα θα περιέχει την αρχική λέξη. Η καθεμία από αυτές τις τρεις έννοιες έχει μελετηθεί ξεχωριστά, χρησιμοποιώντας αρκετά διαφορετικές τεχνικές. Ωστόσο, υπάρχει τρόπος να εκφραστεί η καθεμία ως περίπτωση της άλλης. Πιο συγκεκριμένα οι expander γράφοι και αλγόριθμοι εξαγωγής τυχαιότητας μπορούν να εκφραστούν σαν Κώδικες Διόρθωσης Λαθών με Λίστα και το αντίστροφο.","abstract_html":"Ο σκοπός της εργασίας είναι να κάνει μια εισαγωγή από τρεις έννοιες που είναι σημαντικές στη Θεωρία Πολυπλοκότητας, στην Κρυπτογραφία αλλά και στη Θεωρία Ψευδοτυχαιότητας γενικότερα. Οι έννοιες αυτές είναι οι Expander Γράφοι, Εξαγωγή Τυχαιότητας και Κώδικες Διόρθωσης Λαθών με Λίστα. Οι expander γράφοι έχουν την ιδιότητα ότι αποτελούνται απο λίγες ακμές όμως οι κορυφές τους είναι πολύ καλά συνδεδεμένοι. Ένας αλγόριθμος εξάγει τυχαιότητα όταν παίρνει σαν είσοδο μία ακολοθία που δεν έχει τέλεια τυχαιότητα και επιστρέφει μία άλλη ακολουθία που είναι σχεδόν τυχαία. Οι Κώδικες Διόρθωσης Λαθών με Λίστα ίσως να φαίνεται ότι δεν έχουν άμεση σχέση με τη θεωρία Ψευδοτυχαιότητας. Χρησιμοποιούνται για να λύσουν το πρόβλημα επικοινωνίας σε ένα δίκτυο το οποίο μπορεί να εισάγει θόρυβο μεγαλύτερο από αυτόν που μπορούν να αφαιρέσουν οι απλοί Κώδικες Διόρθωσης Λαθών. Η αποκωδικοποίηση σε αυτήν την περίπτωση δε γίνεται με την επιστροφη μίας μοναδικής λέξης, αλλά με την επιστροφή μίας λίστας λέξεων η οποία σίγουρα θα περιέχει την αρχική λέξη. Η καθεμία από αυτές τις τρεις έννοιες έχει μελετηθεί ξεχωριστά, χρησιμοποιώντας αρκετά διαφορετικές τεχνικές. Ωστόσο, υπάρχει τρόπος να εκφραστεί η καθεμία ως περίπτωση της άλλης. Πιο συγκεκριμένα οι expander γράφοι και αλγόριθμοι εξαγωγής τυχαιότητας μπορούν να εκφραστούν σαν Κώδικες Διόρθωσης Λαθών με Λίστα και το αντίστροφο.","abstract_has_math":false,"creators":["Τέντες Αριστείδης"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2009,"date_issued":"2009","date_published":"2009","updated_at":"2026-11-19T05:26:38Z","subjects":[],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1321056"],"render_values":[{"text":"uoadl:1321056","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1321056","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1321056","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1321056","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Τέντες Αριστείδης"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2009"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1321056","https://pergamos.lib.uoa.gr/uoa/dl/object/1321056"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Ο σκοπός της εργασίας είναι να κάνει μια εισαγωγή από τρεις έννοιες που είναι σημαντικές στη Θεωρία Πολυπλοκότητας, στην Κρυπτογραφία αλλά και στη Θεωρία Ψευδοτυχαιότητας γενικότερα. Οι έννοιες αυτές είναι οι Expander Γράφοι, Εξαγωγή Τυχαιότητας και Κώδικες Διόρθωσης Λαθών με Λίστα. Οι expander γράφοι έχουν την ιδιότητα ότι αποτελούνται απο λίγες ακμές όμως οι κορυφές τους είναι πολύ καλά συνδεδεμένοι. Ένας αλγόριθμος εξάγει τυχαιότητα όταν παίρνει σαν είσοδο μία ακολοθία που δεν έχει τέλεια τυχαιότητα και επιστρέφει μία άλλη ακολουθία που είναι σχεδόν τυχαία. Οι Κώδικες Διόρθωσης Λαθών με Λίστα ίσως να φαίνεται ότι δεν έχουν άμεση σχέση με τη θεωρία Ψευδοτυχαιότητας. Χρησιμοποιούνται για να λύσουν το πρόβλημα επικοινωνίας σε ένα δίκτυο το οποίο μπορεί να εισάγει θόρυβο μεγαλύτερο από αυτόν που μπορούν να αφαιρέσουν οι απλοί Κώδικες Διόρθωσης Λαθών. Η αποκωδικοποίηση σε αυτήν την περίπτωση δε γίνεται με την επιστροφη μίας μοναδικής λέξης, αλλά με την επιστροφή μίας λίστας λέξεων η οποία σίγουρα θα περιέχει την αρχική λέξη. Η καθεμία από αυτές τις τρεις έννοιες έχει μελετηθεί ξεχωριστά, χρησιμοποιώντας αρκετά διαφορετικές τεχνικές. Ωστόσο, υπάρχει τρόπος να εκφραστεί η καθεμία ως περίπτωση της άλλης. Πιο συγκεκριμένα οι expander γράφοι και αλγόριθμοι εξαγωγής τυχαιότητας μπορούν να εκφραστούν σαν Κώδικες Διόρθωσης Λαθών με Λίστα και το αντίστροφο.","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."]},{"key":"dc:title","label":"Title","values":["Expander graphs, randomness extractors and error correcting codes"]}]}],"canonical_facts":{"dc:creator":["Τέντες Αριστείδης"],"dc:date":["2009"],"dc:description":["Ο σκοπός της εργασίας είναι να κάνει μια εισαγωγή από τρεις έννοιες που είναι σημαντικές στη Θεωρία Πολυπλοκότητας, στην Κρυπτογραφία αλλά και στη Θεωρία Ψευδοτυχαιότητας γενικότερα. Οι έννοιες αυτές είναι οι Expander Γράφοι, Εξαγωγή Τυχαιότητας και Κώδικες Διόρθωσης Λαθών με Λίστα. Οι expander γράφοι έχουν την ιδιότητα ότι αποτελούνται απο λίγες ακμές όμως οι κορυφές τους είναι πολύ καλά συνδεδεμένοι. Ένας αλγόριθμος εξάγει τυχαιότητα όταν παίρνει σαν είσοδο μία ακολοθία που δεν έχει τέλεια τυχαιότητα και επιστρέφει μία άλλη ακολουθία που είναι σχεδόν τυχαία. Οι Κώδικες Διόρθωσης Λαθών με Λίστα ίσως να φαίνεται ότι δεν έχουν άμεση σχέση με τη θεωρία Ψευδοτυχαιότητας. Χρησιμοποιούνται για να λύσουν το πρόβλημα επικοινωνίας σε ένα δίκτυο το οποίο μπορεί να εισάγει θόρυβο μεγαλύτερο από αυτόν που μπορούν να αφαιρέσουν οι απλοί Κώδικες Διόρθωσης Λαθών. Η αποκωδικοποίηση σε αυτήν την περίπτωση δε γίνεται με την επιστροφη μίας μοναδικής λέξης, αλλά με την επιστροφή μίας λίστας λέξεων η οποία σίγουρα θα περιέχει την αρχική λέξη. Η καθεμία από αυτές τις τρεις έννοιες έχει μελετηθεί ξεχωριστά, χρησιμοποιώντας αρκετά διαφορετικές τεχνικές. Ωστόσο, υπάρχει τρόπος να εκφραστεί η καθεμία ως περίπτωση της άλλης. Πιο συγκεκριμένα οι expander γράφοι και αλγόριθμοι εξαγωγής τυχαιότητας μπορούν να εκφραστούν σαν Κώδικες Διόρθωσης Λαθών με Λίστα και το αντίστροφο.","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."],"dc:identifier":["uoadl:1321056","https://pergamos.lib.uoa.gr/uoa/dl/object/1321056"],"dc:language":["English"],"dc:title":["Expander graphs, randomness extractors and error correcting codes"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:26:38Z"}