Analysis of Boolean Functions

Aim 

 

This week long course has three broad aims : 

1) To give a rapid introduction to Fourier analysis of Boolean functions and to discuss these from a probabilistic perspective. 

2) Discuss some of the basic problems from combinatorial optimization, notably the Travelling Salesman problem and the Max-Cut problem and approximation algorithms for these.

3) Show how the analysis of Boolean functions can be used to show optimal inapproximability results. 

 

We expect a mix of students from Mathematics/Statistics, Industrial Engineering and Computer Engineering,  departments : The topics of this summer school lie in the intersection of these three disciplines and students will benefit from new perspectives on topics that they are familiar with. 

 

There are three prerequisites for attendance : Familliarity with discrete probability, some knowledge of algorithms and an interest in theoretical aspects of algorithm analysis. 

 

Umit Islak, Bogazici University

Zafeiriakis Zafeiriakopoulos, Gebze Teknik University

Alp Bassa, Bogazici University

Ekin Ozman, Bogazici University

Lectures from 9 - 10:30 and 14:00-15:30