University of Warsaw - Central Authentication System
Strona główna

ean Functions and Randomness Extractors

General data

Course ID: 1000-2M13FBE
Erasmus code / ISCED: 11.3 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration The ISCED (International Standard Classification of Education) code has been designed by UNESCO.
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) Basic information on ECTS credits allocation principles:
  • the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS;
  • the student’s weekly hourly workload is 45 h;
  • 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes;
  • weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS;
  • work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load.

view allocation of credits
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

This course is not currently offered.
Course descriptions are protected by copyright.
Copyright by University of Warsaw.
ul. Banacha 2
02-097 Warszawa
tel: +48 22 55 44 214 https://www.mimuw.edu.pl/
contact accessibility statement USOSweb 7.0.3.0-2b06adb1e (2024-03-27)