### Abstract

We give a new (1 + ε)-approximation for SPARSEST CUT problem on graphs where small sets expand significantly more than the sparsest cut (expansion of sets of size n/r exceeds that of the sparsest cut by a factor √ log n log r, for some small r; this condition holds for many natural graph families). We give two different algorithms. One involves Guruswami-Sinop rounding on the level-r Lasserre relaxation. The other is combinatorial and involves a new notion called Small Set Expander Flows (inspired by the expander flows of [1]) which we show exists in the input graph. Both algorithms run in time 2O(r)poly(n). We also show similar approximation algorithms in graphs with genus g with an analogous local expansion condition. This is the first algorithm we know of that achieves (1 + ε)-approximation on such general family of graphs.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 |

Pages | 270-279 |

Number of pages | 10 |

DOIs | |

State | Published - Dec 1 2013 |

Event | 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 - Berkeley, CA, United States Duration: Oct 27 2013 → Oct 29 2013 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

ISSN (Print) | 0272-5428 |

### Other

Other | 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 |
---|---|

Country | United States |

City | Berkeley, CA |

Period | 10/27/13 → 10/29/13 |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)

## Fingerprint Dive into the research topics of 'Towards a better approximation for SPARSEST CUT?'. Together they form a unique fingerprint.

## Cite this

*Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013*(pp. 270-279). [6686163] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2013.37