Welcome to Not So Great Ideas in Theoretical Computer Science (notsogitcs), the blog of the Theory of Computation group at MIT! Here, we hope to give you a glimpse of the exciting world of theoretical computer science through the eyes of those working in its trenches – the students (graduate and undergraduate), the postdocs, and maybe even some of the faculty. What can you expect from us here? Well, in addition to lengthy technical discussions on the latest and greatest in approximation algorithms and complexity lower bounds and algorithmic game theory — those will come, don’t worry — we also plan to share different aspects of Theory at MIT, from the annual “CornFest”, the student theory retreat, to our “Not so Great Ideas in Theoretical Computer Science” tradition! Coming soon:
- Student theory retreat: Aloni and Themis‘s tale, through words and pictures, of upstate New York, 5 minute research introduction madness, and an unconventional way of learning random matrix theory.
- FOCS 2013 recaps: highlights of the most recent Foundations of Computer Science conference, held at Berkeley, CA (part 1, part 2).
- Better algorithms for Approximate Nearest Neighbor: Ilya‘s synopsis of their exciting paper in SODA 2014.
- A Fountain of Randomness: Henry on an Infinite Randomness Expansion Machine.
- …and more!