Given a graph, the inverse isoperimetric problem concerns the structure of subsets $A$ of the vertices, with few edges between the set $A$ and its complement $A^c$. One well known problem in this direction is the Fourier-Entropy-Influence conjecture, which concerns the inverse isoperimetric problem in the Hamming cube. It has applications to PAC learning and also to other areas. In my talk I will discuss some progress towards the conjecture and also several other related inverse isoperimetric inequalities. Based on joint works with Evra, Kelman, Kindler, Keevash, Minzer, Safra.
18 сен 2024