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

This webpage is for the academic year 2014-2015. Previous years: 2013-2014, 2012-2013.

Where: G5 Lounge, Stata Center.
When: Typically on Tue/Wed/Thu at lunch time. For exact dates and times,
* Sign up to the GITCS mailing list.
* Check out the MIT TCS calendar.
Organizers: Tal Wagner (talw@mit.edu) and Govind Ramnarayan (govind@mit.edu).
* 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

TitleIntroduction to Polar Codes

AbstractThe 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

TitlePresenting theory results in CSAIL: Open discussion

AbstractI 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

TitleHigh Dimensional Expanders and Property Testing

AbstractI 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

TitleKakeya sets over finite fields

AbstractA Kakeya set in Fqn (where Fq 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 qn/n! on the size of Kakeya sets in Fqn. 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.

[1] Wikipedia page on Kakeya Sets : https://en.wikipedia.org/wiki/Kakeya_set
[2] Dvir's paper : http://arxiv.org/abs/0803.2336

Time: Thu Sept 10th, 12:40 PM

Speaker: Jerry Li

TitleThe DKW inequality via Dudley's entropy method

AbstractThe 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

Spring 2015