What should I do with small research results in theoretical computer science?
In my opinion, nothing new is not publishable. Small results are not prestige-ly enough publishable, that's it.

So, if you want to publish this result, find a venue small enough for it and submit. Another issue, however, if your advisor tells you to wait, you should rather wait.

It might be, namely, that by combining this result with a minor further development, you might seriously bump up its "prestige", i.e. the possibility it gets accepted at a larger or more important venue. Advisors typically know this stuff better than PhD students.



To give you an example. I played once with PGP public keys and found a way to visualize them as a nice image. After a literature research I found that noone did it like this before. So, it was a new scientific result, but not very publishable, just as your issue. Then I thought a bit more, what properties does my visualization have. I found SHA1 collision data, applied my visualization, and saw that I can tell the two files with same hash apart with my approach. Now, this is quite big. (But little work for me.)

I further looked around where to publish it (Visualization or Security), it successfully landed at the Visual Computer.