[Theory] Theory topics courses for this quarter

[Aaron Potechin via Theory]

Hi everyone,

We would like to advertise our theory topics courses for this quarter. The course descriptions are below.

Note: While it is only possible to officially enroll in one of our courses, you are more than welcome to attend more than one of our courses.

Sincerely,
Haotian, Aaron, and Will


Topics in Theoretical Computer Science: Geometric Discrepancy Theory

Haotian Jiang (jhtdavid at uchicago.edu)

MW 3:00pm-4:20pm, RY 277

Course description:

Discrepancy theory studies the irregularities of distributions. Typical questions studied in discrepancy theory include: "What is the 'most uniform' way of distributing n points in the unit square, and how big must the irregularity be?", "What is the best way to divide a set of n objects into two groups that are as 'similar' as possible?" These questions have been studied since the 1930s and progress on them have found extensive applications to many areas of mathematics, computer science, statistics, finance, etc. In this seminar course, we study discrepancy with respect to classes of geometric shapes. We will discuss classical and recent results in these directions, and in the course of understanding their proofs, appreciate the extensive set of beautiful underlying mathematical tools. This course will take the form of a reading group (with a few lectures by myself in the beginning to properly set things up). We will read part of the fantastic textbooks by Jiri Matousek and Bernard Chazelle for the classical results, and several recent papers for the latest developments.

This course will be graded Pass/Fail.


Topics in Theoretical Computer Science: The Sum of Squares Hierarchy

Aaron Potechin (potechin at uchicago.edu)

MW 1:30pm-2:50pm, RY 277
Course Description:
The sum of squares hierarchy (SoS) is a hierarchy of semidefinite programs which is broadly applicable, surprisingly powerful, and in some sense, simple. In particular, SoS can be applied to almost any combinatorial optimization problem and captures the best known algorithms for many problems including max cut, sparsest cut, and unique games. However, at its heart, all SoS is using is polynomial equalities and the fact that squares are non-negative over the real numbers.
The goal of this course is to give a good intuition for SoS by describing much of what is known so far about SoS. Topics which will be covered include semidefinite programming, Positivstellensatz/SoS proofs, pseudo-expectation values, the Goemans-Williamson algorithm for max cut, linear and semidefinite programs for sparsest cut, applications of SoS to planted sparse vector, tensor completion, and robust estimation, SoS lower bounds for 3-XOR, knapsack, and planted clique, the low-degree conjecture, the unique games conjecture, and the small-set expansion hypothesis.
This course will have letter grades based on problem sets.

Topics in Theoretical Computer Science: Circuit Complexity
William Hoza (williamhoza at uchicago.edu)
TR 9:30am-10:50am, RY 255

Course description:

One of the most mathematically appealing ways to model computation is using Boolean circuits: networks of logic gates applied to Boolean variables. One can using counting arguments to show that there exist Boolean functions with exponential "circuit complexity," i.e., all circuits computing these functions have exponentially many gates. However, nobody knows how to prove that specific functions of interest have high circuit complexity. In this course, we will primarily study bounded-depth circuits, which can be considered a model of super-fast parallel algorithms. We will see that such circuits are powerful enough to perform many interesting computations, but we will also prove that they have severe limitations.

This course will have letter grades based on problem sets.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20240930/e49faa5d/attachment.html>