Category Archives: Theoretical Computer Science

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 →