Category Archives: Theoretical Computer Science

If you work long enough in any mathematical science, at some point you will need to estimate an integral that does not have a simple closed form. Maybe your function is really complicated. Maybe it’s really high dimensional. Often you … Continue reading →

I just encountered an amazing number theoretic result. It is probably very well known, but for those who never saw it it’s quite something, so I thought I would share it. Let be a positive integer. A partition of is … Continue reading →

This first week at the Simons Institute was a lot of fun! I attended the first workshop in the Real Analysis program which was about Testing, Learning and Inapproximability. There was plenty of good talks and I learned a lot of … Continue reading →

In this post we discuss the following notion: Let and be two metric spaces, one says that embeds into with distortion if there exists and such that for any ,     We write this as . Note that if … Continue reading →

In this post I would like to argue that showing -completeness of a problem is in fact only a weak certificate of difficulty. Dynamic Programming Consider the problem of the previous lecture (which is -complete): given positive integers , does … Continue reading →

We are now going to restrict our attention to Boolean functions . Computing a Boolean function is called a decision problem, since we need to decide for whether or not it is in the set . We call such a set … Continue reading →

So far we have seen several algorithms to solve various optimization problems. For example for LPs we have seen that the ellipsoid method has a computational complexity of roughly , and we improved this bound with Interior Point Methods which … Continue reading →