Theory of Computing Mini-courses

Propositional Proof Complexity

Instructor: Alexander A. Razborov
Schedule: 11:15-12:45 Wednesdays and Thursdays, from June 25th through July 3rd. (Note: July 9-10 classes canceled.)
Location: TTIC 530
Description: Proofs and computations are among the most basic concepts pertinent to virtually any intellectual human activity. On the intuitive and practical level, it has been perceived for centuries that specific proofs or computations can perform very differently in terms of their “efficiency”, “complexity” or “feasibility” understood e.g. in terms of length, time or space consumed or “inherent”, “logical” complexity. As long as computations are concerned, rigorous formalizations of these notions developed some 40-50 years ago eventually gave rise to what we call today Theoretical Computer Science.

It is much less known that there has been a similar and largely parallel effort for proofs, and the theory of feasible proofs resulted from this effort is precisely the main theme of our mini-course. It will be a significantly abridged version of a full-fledged graduate course I taught in 2009, and it will primarily focus on "concrete" results for so-called "weak" proof systems: Resolution, Geometric and Algebraic Proof Systems. Lecture notes are available on-line at; our choice of the material will roughly correspond to Sections 2,6,7 and Appendix A. No specific pre-requisites are required.

Semidefinite Programming and Constraint Satisfaction

Instructors: Madhur Tulsiani and Yury Makarychev
Schedule: 2:15-3:45 Monday, Tuesday, and Friday, June 24th to July 11th except July 4th
Location: TTIC 530

Click here for online reading and video recordings of the lectures.

Permutation Groups

Instructor: Laszlo Babai
Schedule: 2:15-3:45 Wednesday, July 9th
Location: TTIC 530
Description: This mini-course develops the basic concepts of the theory of permutation groups with a focus on the structural and asymptotic theory of primitive groups. While the subject is pure mathematics, it also serves as a foundation to the study of Boolean functions satisfying a symmetry condition. Prerequisite: an introducion to group theory (Sylow's theorems, the Jordan - Hölder theorem, solvability).

Complexity of Boolean Functions - seminar

Instructor: Laszlo Babai
Schedule: 2:15-3:45 Thu, July 10th; Mon, July 14th, Tue, July 15th, Mon, July 21st, and every day from Wed, July 23rd to Wed, Aug 15th
Location: TTIC 526
Description: This seminar will involve presentations by students and the instructor, including solving exercises and discussion of open problems. Topics to be discussed include the Fourier transform over finite abelian groups and various complexity measures of Boolean functions, including decision-tree complexity, sensitivity, certificate complexity, communication complexity, property testing complexity.

Property testing and open problems in the complexity of Boolean Functions

Instructor: Sourav Chakraborty
Schedule: 2:15-3:45 Wednesday, Thursday, and Friday, July 16th through July 18th and Tuesday, July 22
Location: TTIC 530

Machine Learning Mini-courses

Introduction to Modern Supervised Learning

Instructor: Greg Shakhnarovich
Schedule: 9:30-11:00 -- Tue, July 1; Thu, July 3; Tue, July 8; Thu, July 10; Fri, July 11; Tue, July 15; and Wed, July 16.
Location: TTIC 526
Description: The course will provide introduction to supervised learning, and cover principles and tools underlying some of the most successful statistical learning methods. The rough plan for the course:

Probabilistic Graphical Models

Instructor: John Lafferty
Schedule: 10:30-12:00 Monday and Wednesday, June 30th through July 14th
Location: TTIC 526
Description: This course will present an introduction to probabilistic graphical models, as developed in statistics and machine learning. Topics will include independence relations for directed and causal graphs, undirected graphs, the Hammersley-Clifford theorem, and the junction tree decomposition. Estimation methods for the Gaussian graphical model, the Ising model, and extensions of these models will be presented. Tools based on variational approximations and Markov chain sampling will be introduced.

Mathematics REU Courses

All courses in the Math REU are open to students in the Theory of Computing and Machine Learning REU. Please let us (Babai and Kurtz) know by email as soon as possible if you are interested in attending a Math REU course.

The following “apprentice course” is a part of the Math REU. The course runs from June 23 through July 25. Please check for schedule updates at the Math REU website.

Linear Algebra and Discrete Structures

Instructors Laszlo Babai (lectures), Sean Howe (math Ph.D. student, problem sessions)
Schedule for the first two weeks:
  Mon, June 23, 9:30 - 12:00 (lecture)
  Tue, June 24, 9:30 - 10:50 (problems)
  Wed, June 25, 9:30 - 10:50 (problems)
  Thu, June 25, 9:30 - 10:50 (problems)
  Fri, June 27, 9:30 - 12:00 (lecture)
  Mon, June 30, 9:30 - 12:00 (lecture)
  Tue, July 1, 9:30 - 10:50 (problems)
  Wed, July 2, 9:30 - 12:00 (lecture)
  Thu, July 3, 9:30 - 10:50 (problems)
Location: Ryerson 251. Problem sessions are followed by office hours 11:00-12:00 in Ry 277.
Description: The course will develop the usual topics of linear algebra and illustrate them on unusual (often striking) applications to discrete structures. Emphasis will be on creative problem solving and discovery. The basic topics include determinants, linear transformations, the characteristic polynomial, Euclidean spaces, orthogonalization, the Spectral Theorem, Singular Value Decomposition. Application areas to be highlighted include spectral graph theory (expansion, quasirandom graphs, Shannon capacity), random walks, clustering high-dimensional data, extremal set theory, and more.