Title: On the complexity of approximating vertex expansion.

 

Abstract:

In this work, we study the complexity of approximating the vertex expansion of graphs, in particular its connection to the problem of approximating small-set edge expansion. Our approach can be split in to four parts (some of which might be of independent interest):

 

1)  We define a functional on a graph that mimicks the ``degree-d vertex expansion" of the graph.  We show that approximating this functional is equivalent to approximating degree-d expansion on graphs (up to some loss on the degree).

 

2)  We show a gaussian isoperimetric statement associated with this functional.

 

3)  Using the invariance principle, we translate the gaussian isoperimetric result in to a corresponding statement on the value of the functional on product graphs. Specifically, we show a lower bound on the value of the functional ("degree-d vertex expansion")  for functions on product graphs that are far from dictators. This yields a dictatorship testing gadget.

 

4)  The dictatorship testing gadget is used in conjunction with the small set expansion problem to obtain the hardness result for vertex expansion.

 

Joint work with Santosh Vempala and Anand Louis.

 

 

 

Title: Entropy power inequality for the Renyi entropy.

 

Abstract. We will be discussing one natural extension of the entropy power inequality to the case of the Renyi entropy.