ean Functions and Randomness Extractors
General data
Course ID: | 1000-2M13FBE |
Erasmus code / ISCED: |
11.3
|
Course title: | ean Functions and Randomness Extractors |
Name in Polish: | Funkcje boolowskie i ekstraktory losowości |
Organizational unit: | Faculty of Mathematics, Informatics, and Mechanics |
Course groups: |
(in Polish) Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka Elective courses for Computer Science |
ECTS credit allocation (and other scores): |
(not available)
|
Language: | English |
Type of course: | elective monographs |
Prerequisites (description): | Basic knowlege of the probability theory and discreete mathematics. |
Short description: |
The course introduces methods of continuous Fourier analysis applied to functions on finite Abelian groups. Surprisingly, the results obtained this way are much stronger in the finite case then in continuous one. The abovementioned methods are widely used in modern cryptography and in the theory of randomness extractors. The randomness extractors theory attempts to obtain the most efficient ways of converting a non-uniform string of bits into a uniform one with as little assumptions on the input distribution as possible. Recent breakthroughs in the extractors theory were obtained with the methods of the discrete Fourier analysis. We will not assume that the students are familiar with any of those methods and theorems. Everything will be defined and proved from scratch. |
Full description: |
-Introduction to basic notions and theorems in harmonic analysis -Linearity of boolean functions -Bent functions - how to construct function as far as possible from linear functions family -Non-deterministic functions - why nothing works as intended -Probabilistic properties testing -Characteristic function and its properties, XOR-Lemma -Entropy and min-entropy of Boolean vector - how to measure randomness of given random vector -Introduction to Extractors Theory -Two-Source Extractors, Weak and Strong Extractors, Barak theorem -Bourgains Extractor - record-breaker |
Bibliography: |
http://www.cs.cmu.edu/ódonnell/aobf12/ |
Learning outcomes: |
Student: -knows basic methods of harmonic analysis -can apply Walsh Transform to Boolean function or random Boolean vector -can check basic properties of function with Walsh Transform -knows basic methods of properties testing -understands notion of entropy and min-entropy -knows examples of Two-Source Extractors -Understands difference between weak and strong extractors |
Assessment methods and assessment criteria: |
Homeworks and exam |
Copyright by University of Warsaw.