Category Archives: Theoretical Computer Science

First week of activity at the Simons Institute

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

Posted in Theoretical Computer Science | 4 Comments

Random-Approx 2013

Last week I attended the Random-Approx conference at Berkeley. I missed quite a few talks as I was also settling in my new office for the semester at the Simons Institute so I will just report on the three invited talks: Luca Trevisan gave a … Continue reading

Posted in Random graphs, Theoretical Computer Science | 2 Comments

Embeddings of finite metric spaces in Hilbert space

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

Posted in Theoretical Computer Science | Leave a comment

ORF523: Getting around NP-hardness

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

Posted in Theoretical Computer Science | Leave a comment

ORF523: P vs. NP, NP-completeness

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

Posted in Theoretical Computer Science | Leave a comment

ORF523: Turing Machines

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

Posted in Theoretical Computer Science | Leave a comment