|Select the desired Level or Schedule Type to find available classes for the course.
|CS 58500 - Theoretical Computer Science Toolkit
Credit Hours: 3.00. 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.
3.000 Credit hours
Levels: Graduate, Professional, Undergraduate
Schedule Types: Distance Learning, Lecture
Offered By: College of Science
Department: Computer Science
May be offered at any of the following campuses:
Learning Outcomes: 1. Explain and justify the merits and limitations of convex optimization algorithms. 2. Describe the characteristics and the role of convexity in optimization. 3. Formulate mathematically problems that have solutions based on convex optimization or matric analysis tools and analyze them effectively. 4. Predict typicality of the outcome in experiments. 5. Explain how to use and apply concentration bounds, including Chernoff-Hoeffding Bound, Martingales and Azuma's Inequality, and applications of the Talagrand inequality. 6. Develop precise mathematical formulation of problems and analyze using frameworks related to concentration of measure. 7. Apply Discrete Fourier Transform to determine properties of functions. 8. Explain 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. 9. Identify properties of functions based on the properties of their spectrum. 10. Explain the basic ideas underlying the tradeoff between the amount of redundancy used and the number of errors that can be corrected by a code. 11. Describe achieving the optimal tradeoff between redundancy and error correction for codes that come equipped with efficient encoding and decoding. 12. Illustrate how and why concatenated codes support the construction of asymptotically good codes.
Must be enrolled in one of the following Programs:
Short Title: TCS Toolkit