 | Use this page to maintain syllabus information, learning objectives, required materials, and technical requirements for the course. |
| CS 58500 - Theoretical Computer Science Toolkit |
|---|
|
Associated Term:
Spring 2023
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. Required Materials: Technical Requirements: |
| Return to Previous | New Search |
 |