Back to search

National and Kapodistrian University of Athens

On the structure of Boolean functions

Abstract

dc:description

Ο κύριος σκοπός αυτής της διπλωματικής εργασίας είναι να παρουσιάσουμε ορισμένα από τα πιο σημαντικά αποτελέσματα στον τομέα της ανάλυσης των Boolean συναρτήσεων και ταυτόχρονα να κατανοήσουμε σε βάθος τα δομικά τους χαρακτηριστικά. Στα δύο πρώτα κεφάλαια, παρέχουμε μια εισαγωγή σε ορισμένες προκαταρκτικές έννοιες και στη συνέχεια προχωρούμε στο Θεώρημα Kahn–Kalai–Linial (KKL) και στο Junta Theorem του Friedgut, τα οποία παρουσιάζονται αναλυτικά και αποτελούν σημαντικά εργαλεία σε αυτή την περιοχή. Στο κεφάλαιο 4, παρουσιάζουμε ένα θεώρημα δομής για τις Boolean συναρτήσεις με μικρές total influences, του Hamed Hatami, το οποίο γενικεύει τη δουλειά του Friedgut και του Bourgain και αποτελεί τον κύριο στόχο αυτής της εργασίας. Το συγκεκριμένο θεώρημα δείχνει ουσιαστικά ότι σε κάθε χώρο πιθανότητας, οι Boolean συναρτήσεις με μικρές total influences, είναι ουσιαστικά εκείνες που είναι σχεδόν μετρήσιμες ως προς ορισμένες φυσιολογικές υπο-σίγμα-άλγεβρες, και περιγράφει τη δομή των μονότονων set properties, που δεν παρουσιάζουν το φαινόμενο sharp threshold. Στο τελευταίο κεφάλαιο, παρουσιάζουμε το θεώρημα του Arrow, το οποίο αποτελεί βασικό αποτέλεσμα στην περιοχή της θεωρίας Social Choice.

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Σταυρακάκης Εμμανουήλ
  • Stavrakakis Emmanouil

Subjects

dc:subject × 2

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:3471182

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
citation

Σταυρακάκης Εμμανουήλ; Stavrakakis Emmanouil. On the structure of Boolean functions. 2025. https://pergamos.lib.uoa.gr/uoa/dl/object/3471182