### (a.k.a. Great Ideas in Theoretical Computer Science Seminar)

Theoretical Computer Science is full of great ideas, so once a week, the MIT Theory group gets together to socialize and share some knowledge. We'll briefly share some interesting ideas, and discuss a superset of these ideas over lunch.

**Where**: G5 Lounge, Stata Center.

**When**: Typically on Tue/Wed/Thu at lunch time. For exact dates and times,

***** Please contact us with any **feedback**, or if you would like to **give a talk**.

***** If you are a new student/intern/visitor, we will likely come after you. So you might as well volunteer...

**Speaker Guidelines**: If you are about to give a talk, you might want to check out these

guidelines.

## Upcoming Talk

The 2014-2015 Theory Lunch run is concluded. Thanks to all the speakers and attendees. Check back soon for the upcoming 2015-2016 run.

## Past Talks

**Time**: Thu Oct 7st, 12:40 PM

**Speaker**: Jayadev Acharya

**Title**:

Introduction to Polar Codes

**Abstract**:

The goal of this talk is to just introduce the basics of polar codes, as well as their motivation. The abstract of the course and a summary of topics covered in the first lecture can be found in the link https://lids.mit.edu/news-and-events/events/short-course-polar-codes-1-4.

**Time**: Thu Oct 1st, 12:30 PM

**Speaker**: Polina Golland

**Title**:

Presenting theory results in CSAIL: Open discussion

**Abstract**:

I would be speaking to the students about the Research Highlight competition we hosted last spring, with the goal of figuring out a format that would work for theory results.

**Time**: Wed Sept 23th, 12:40 PM

**Speaker**: Tal Wagner

**Title**: High Dimensional Expanders and Property Testing

**Abstract: **I will give a very basic introduction to the recently emerging theory of high-dimensional expansion for simplicial complexes (or hypergraphs), and demonstrate how it solves the following natural property-testing problem on graphs: Given a graph G on n vertices, test whether G is a complete bipartite graph, i.e. isomorphic to K_{s,n-s} for some s=1,...,n-1.

The talk will be based mainly on the paper "High Dimensional Expanders and Property Testing" by Kaufman and Lubotzky (ITCS'14, arxiv.org/abs/1312.2367).

**Time**: Thu Sept 17th, 12:40 PM

**Speaker**: Pritish Kamath

**Title**: Kakeya sets over finite fields

**Abstract: **A Kakeya set in F_{q}^{n} (where F_{q} is a finite field with q elements) is a set that contains a line in every direction. In a breakthrough work, Dvir [2] proved a lower bound of q^{n}/n! on the size of Kakeya sets in F_{q}^{n}. The lower bounds were subsequently improved upon, in later works of Saraf-Sudan and Dvir-Kopparty-Saraf-Sudan.

In this talk, I will define Kakeya sets, and state the questions that are studied about them. I will give full details of Dvir's proof, which is only a paragraph long! If time remains, I will try to describe the key ideas in the subsequent improvements.

**Time**: Thu Sept 10th, 12:40 PM

**Speaker**: Jerry Li

**Title**: The DKW inequality via Dudley's entropy method

**Abstract: **The Kolmogorov distance is a weak, but fundamental measure of distance between two univariate distributions. The famous Dvoretzky–Kiefer–Wolfowitz (or DKW) inequality states that the Kolmogorov distance between a univariate distribution f and the empirical estimate of f given O(1 / eps^2) samples is at most eps. In this talk I will hopefully give a tight proof of this using Dudley's entropy method. On the way, I will discuss basic concepts related to VC theory. Given time, I will discuss how to generalize these arguments for more general measures of distance (so-called "A_k distances"), and how it relates to distribution estimation. Given even more time, I will discuss why in certain settings (though not in this one), Dudley's entropy method is still not tight, and how to improve it using the method of "generic chaining" (as Talagrand calls it), or "majorizing measures" (as I think most other people call it).

**Summer 2015**