Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Separations:
TR15-164 | 13th October 2015
Pavel Hrubes, Amir Yehudayoff

On isoperimetric profiles and computational complexity

The isoperimetric profile of a graph is a function that measures, for an integer $k$, the size of the smallest edge boundary over all sets of vertices of size $k$. We observe a connection between isoperimetric profiles and computational complexity. We illustrate this connection by an example from communication complexity, ... more >>>

ISSN 1433-8092 | Imprint