Instructor:
Prof. Bernhard Haeupler

Time and location:
Tuesday and Thursday, 10:30AM-11:50AM, GHC 4211
first class: Sept. 8th

Office hours:
Anytime; please send an email first.


Overview

Randomness has proven as an incredibly powerful resource for developing beautiful, simple, and efficient algorithms with provable performance guarantees. Algorithmic Superpower Randomization is a research centered special topics graduate course that will teach how YOU can unleash the power of randomization in YOUR research.

Together we will explore a biased random sample of both classical and modern topics in theoretical computer science related to randomness and algorithms. The tentative list of topics includes:

  • The Probabilistic Method
  • Error Correcting Codes
  • Distributed Algorithms (Maximal Independent Set, ...)
  • Approximate Limited Independence and Applications (Derandomization, Identity Testing, Hashing, ...)
  • Algorithms for the Lovasz Local Lemma
  • Communication Complexity and Coding for Interactive Communications
  • Network Coding

This course might be particularly interesting to you if you are a graduate (or a very strong undergraduate) student who wants to do theoretical computer science research. We will very interactively discuss and jointly (re-)discover solutions to the problems covered in class. We will also constantly try to identify and examine possible ways to extend or branch off existing solutions and results.

Prerequisites

There are no official prerequisites for this course. However, to be able to enjoy, follow, and contribute to the class a level of mathematical maturity typically found in a CMU computer science theory graduate student is required. We will build on a typical undergraduate background in math (e.g., elementary combinatorics, graph theory, discrete probability, basic algebra/calculus) and theoretical computer science (running time analysis, big-O/Omega/Theta, basic fundamental algorithms). If you are worried about these fundamentals please contact me and we can determine together whether this class is at the right level for you.

Learning Objectives:

After successfully completing this course, you will have gained or improved your ability to:

  • determine and explain the behavior of random processes and algorithms
  • use a probabilistic approach and perspective in understanding (non-probabilistic) combinatorial problems
  • apply probabilisitc tools to unleash the power of randomization when
    • designing your own randomized algorithms for combinatorial problems
    • analyzing their performance using rigorous proofs
    • proving the existence of amazing structures using the probabilistic method
The class and class project will further be a great opportunity to gain (more) experience in:
  • identifying and examining possible research questions and directions
  • working collaboratively on open ended research problems
  • presenting technical results in talks and in writing

Coursework

Our classes will be very interactive. Your questions, suggestions, and discussions will carry the class forward so you owe it to your classmates and me to actively participate in every lecture.

In order for us to have notes to refer back to, each lecture will be scribed by one student. Depending on the number of students you might get to scribe more than once.

During the first part of the course I might give out some ungraded homework problems to help you practice concepts developed in class.

The most exciting and fun part of the course will be the class projects. If you want, you can work together with a fellow classmate. For the project you choose, in consultation with me, a paper or topic related to the class which you are particularly interested in. You will identify and read up on related works and identify questions going beyond the current knowledge found in the literature. You will then try to explore as much as possible where these questions lead you (and your team). Every week some progress on the project should be documented in writing and at the end of the semester you can present your results to your classmates and hear about the cool stuff they worked on.

Evaluation

Grading will be based on class participation and the class project (see coursework).

Links

Course Note Latex Template
Scribe Signup Sheet
CMU Academic Integrity Policy