Category Archives: Theoretical Computer Science
Kernel-based methods for bandit convex optimization, part 1
A month ago Ronen Eldan, Yin Tat Lee and myself posted our latest work on bandit convex optimization. I’m quite happy with the result (first polynomial time method with poly(dimension)-regret) but I’m even more excited by the techniques we developed. Next … Continue reading
Guest post by Sasho Nikolov: Beating Monte Carlo
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
Komlos conjecture, Gaussian correlation conjecture, and a bit of machine learning
Today I would like to talk (somewhat indirectly) about a beautiful COLT 2014 paper by Nick Harvey and Samira Samadi. The problem studied in this paper goes as follows: imagine that you have a bunch of data points in with a certain … Continue reading
A zest of number theory
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
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
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
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
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
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
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