Extremal combinatorics is one of the central branches of discrete mathematics that deals with the problem of estimating the maximum possible size of a combinatorial structure which satisfies certain restrictions. Often, such problems also have applications to other areas including theoretical computer science, additive number theory and information theory. In his talk, we will illustrate this fact using several closely related examples that focus on a recent work with Alon and Moitra.