A Theorist's Toolkit
- The main goal of this course is to give students understanding of the basic methods and techniques used in research of theoretical computer science.
- It is suggested that students will be able to formulate theoretical computer science problems.
- It is expected to develop students' ability to solve problems by using the methods of theoretical computer science.
- Students are expected to master the basic definitions and facts of mathematics and theoretical computer science covered in the course.
- It is expected that students will know how to use basic methods of theoretical computer science.
- It is planned to develop students' skills of transition from discussing practical problems to their mathematical formulations and further analysis of the formulated mathematical problems.
- Polynomial method.Representation of boolean functions by polynomials, applications to decision trees, boolean circuits and communication complexity.
- Probabilistic methods.Chernoff bound and applications. Generalization to dependent random variables.
- Boolean Fourier analysis.Basic notions, results and applications.
- ColloquiumThere is no exam. The course grade is given according to the cumulative assessment.
- Arora, S., & Barak, B. (2009). Computational Complexity : A Modern Approach. Cambridge: Cambridge eText. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=304712
- Ryan O’Donnell. (2012). Analysis of Boolean Functions. Http://Www.Cs.Mcgill.ca/%7Edenis/Barbados2012.Pdf.