My friend Wim van Dam asked me the following question:


* For every finite group $G$, does there exist a subset $S\subset G$ such that $\left|S\right| = O(\sqrt{\left|G\right|})$ and $S\times S = G$? Also, can we describe such an $S$ explicitly?


I believe it's not hard to show that if we choose $S$ uniformly at random, then $\left|S\right| = O(\sqrt{\left|G\right| \log \left|G\right| })$ suffices. But this still leaves the problems of giving an explicit construction and of removing the $\log \left|G\right|$ term.


Of course, if $G$ happens to have a subgroup $H$ of size $\approx \sqrt{\left|G\right|}$, then we just take the union of $H$ with a collection of coset representatives and are done. So, this suggests the possibility of a win-win analysis, where we identify the relatively rare finite groups that don't have a subgroup of the right size and handle them in a different way. Work on approximate subgroups might also be relevant.


In the likely event that this has already been solved, just a link to the paper would be great (a half hour of googling didn't succeed).



Decomposing a finite group as a product of subsets
It was brought to my attention by Noga Alon that my previous answer (which I keep to avoid any confusion) was in fact incorrect: the Rohrbach conjecture got solved completely by Finkelstein, Kleitman, and Leighton in 1988 ("[Applying the classification theorem for finite simple groups to minimize pin count in uniform permutation architectures](https://link.springer.com/chapter/10.1007/BFb0040392)"), and independently by Kozma and Lev in 1992 ("[Bases and decomposition numbers of finite groups](http://gadykozma.me.pn/site/lev1.pdf)"). 


Explicitly, there exists a subset $S\subseteq G$ of size $|S|\le(4/\sqrt 3)|G|^{1/2}$ such that every element of $G$ is representable as a product of two elements from $S$.


