# Courses

## 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 http://people.cs.uchicago.edu/~razborov/teaching/winter09/notes.pdf; 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

**Description:**

- Introduction to Constraint Satisfaction Problems (CSPs) and approximation
- Applications of Semidefinite Programs (SDPs) to approximation: Max-Cut, Grothendieck problems, all CSPs
- Fast algorithms for approximately solving SDPs: the Arora-Kale framework
- SDPs for approximating the maximum of polynomials over semialgebraic sets: the Sum-of-Squares hierarchy

### 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:

- Statistical learning setup; loss, risk, generalization, connections to estimation and optimization
- Linear regression and logistic regression
- Regularization and model selection
- Support vector machines
- Neural networks
- Deep learning and, time permitting, convolutional neural networks

### 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.