3 credits
Spring 2025 Lecture Upper Division
This course covers fundamental techniques and a range of mathematical tools that underlie today's research in theoretical computer science. The course material is essential for research in theoretical computer science as well as machine learning theory. The course is targeted at students who plan to pursue research in these areas. Topics will be chosen from four core areas: Convex Analysis and Optimization, Spectral Methods, Concentration Inequalities, and Discrete Fourier Analysis. Depending on student and instructor interest, additional topics will be chosen and may include applied analysis, coding theory, probabilistic proofs, and more advanced topics in discrete Fourier analysis. Students will read papers in theoretical computer science and machine learning theory using, exploring and extending the covered techniques and tools. Students are expected to be proficient in probability theory, have the maturity to follow and carry out basic analysis proofs, and have completed courses in calculus, linear algebra, discrete mathematics, and analysis of algorithms. More specifically, the course expects mastery of the material covered in Calculus III, Linear Algebra, Probability, Foundations of CS, and Analysis of Algorithms.
Learning Outcomes1Explain and justify the merits and limitations of convex optimization algorithms.
2Describe the characteristics and the role of convexity in optimization.
3Formulate mathematically problems that have solutions based on convex optimization or matric analysis tools and analyze them effectively.
4Predict typicality of the outcome in experiments.
5Explain how to use and apply concentration bounds, including Chernoff-Hoeffding Bound, Martingales and Azuma's Inequality, and applications of the Talagrand inequality.
6Develop precise mathematical formulation of problems and analyze using frameworks related to concentration of measure.
7Apply Discrete Fourier Transform to determine properties of functions.
8Explain why Fourier Analysis of Boolean Functions is a major tool in theoretical CS and describe application scenarios including property testing, cryptography, complexity, learning theory, pseudorandomness, hardness of approximation, and random graph theory.
9Identify properties of functions based on the properties of their spectrum.
10Explain the basic ideas underlying the tradeoff between the amount of redundancy used and the number of errors that can be corrected by a code.
11Describe achieving the optimal tradeoff between redundancy and error correction for codes that come equipped with efficient encoding and decoding.
12Illustrate how and why concatenated codes support the construction of asymptotically good codes.
Restrictions
made by Purdue students.