Courses of Study 2022-2023 
    
    Mar 28, 2024  
Courses of Study 2022-2023 [ARCHIVED CATALOG]

Add to Favorites (opens a new window)

CS 6817 - [Special Topics in Complexity Theory]


     
Fall. Not offered: 2022-2023. Next offered: 2023-2024. 4 credits. Letter grades only.

Prerequisite: CS 4820 .

E. Chattopadhyay.

This course will focus on the ‘Analysis of Boolean Functions’ with the objective to unravel properties of Boolean functions by studying their Fourier spectra. The harmonic analysis of Boolean functions has become a powerful tool in theoretical computer science, leading to ground breaking results in various areas such as social choice theory, hardness of approximation, learning theory, pseudorandomness, property testing and circuit complexity. In fact the tools developed in this area have found key applications beyond computer science, in particular leading to key developments in areas of random graphs, statistical physics, combinatorics and metric spaces. The course will aim to provide an in-depth introduction to this field of study.



Add to Favorites (opens a new window)