# 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 $latex {\mathbf{NP}}&fg=000000$-completeness of a problem is in fact only a weak certificate of difficulty. Dynamic Programming Consider the problem $latex {\mathrm{PARTITION}}&fg=000000$ of the previous lecture (which is $latex {\mathbf{NP}}&fg=000000$-complete): given … Continue reading

## ORF523: P vs. NP, NP-completeness

We are now going to restrict our attention to Boolean functions $latex {f : \{0,1\}^* \rightarrow \{0,1\}}&fg=000000$. Computing a Boolean function is called a decision problem, since we need to decide for $latex {x \in \{0,1\}^*}&fg=000000$ whether or not it is … 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 $latex {O(n^4)}&fg=000000$, and we improved this bound with Interior Point Methods … Continue reading