CS 58500: Theoretical Computer Science Toolkit (Spring 2023)

  • Time: Tuesday and Thursday (01:30 pm - 02:45 pm)
  • Location: LWSN 1106
Campuswire Link:
    link (4-digit code is available on brightspace)
Teaching Assistant:

Course Outline and Policy: [html]
Key Emergency Preparedness Resources: [html]


A Tentative List of Topics:
  • Introduction and Review
    • Brief review of prerequisites
  • Selected Topics in Convex Analysis and Optimization
    • Introduction to convex sets and functions
    • Convex set results: Separating hyperplane and Caratheodory's theorems
    • Convex function results: Jensen's inequality and applications, Legendre-Fenchel transformation
    • Lagrangian duality and Karush-Kuhn-Tucker (KKT) conditions
    • Strong convexity and oracle complexity of gradient descent
    • Gradient descent and its variants [optional]
  • Foundations of Spectral Methods
    • Positive semidefiniteness. Spectral and singular value decompositions
    • Courant-Fischer-Weyl minimax theorems
    • Perron-Frobenius theory [optional]
    • Matrix norms and perturbation theory [optional]
  • Concentration Inequalities and their Applications in CS
    • Introduction to measure theory
    • Markov, Chebyshev, and Chernoff Bounds
    • Hoeffding and Bernstein inequalities
    • Martingales, Azuma-Hoeffding bound, and McDiarmid's inequality
    • Applications to learning theory (e.g., Glivenko-Cantelli)
    • Talagrand's Inequality [optional]
  • Discrete Fourier Analysis
    • Introduction to discrete Fourier Analysis and Abelian groups
    • Characters, bias, Fourier transform
    • Parseval's and Plancherel's identities
    • Blum-Luby-Rubinfeld (BLR) linearity testing
    • Convolution and translation invariant systems
    • Learning: The low-degree algorithms
  • Selected Topics
    • Applied analysis for Learning Theory
    • Coding Theory
    • Additional Randomized Techniques
    • Additional Topics in Discrete Fourier Analysis

Previously Offered:

CS 59000 ATK (Spring 2022)
CS 59000 MTK (Spring 2019)
CS 59000 MTK (Spring 2018)
CS 59000 MTK (Spring 2017)
CS 59000 MTK (Spring 2016)

Useful Materials: Representative Course Material