License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2019.65
URN: urn:nbn:de:0030-drops-101588
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10158/
Go to the corresponding LIPIcs Volume Portal

Schild, Aaron

A Schur Complement Cheeger Inequality

pdf-format:
LIPIcs-ITCS-2019-65.pdf (0.6 MB)

Abstract

Cheeger's inequality shows that any undirected graph G with minimum normalized Laplacian eigenvalue lambda_G has a cut with conductance at most O(sqrt{lambda_G}). Qualitatively, Cheeger's inequality says that if the mixing time of a graph is high, there is a cut that certifies this. However, this relationship is not tight, as some graphs (like cycles) do not have cuts with conductance o(sqrt{lambda_G}).
To better approximate the mixing time of a graph, we consider a more general object. Specifically, instead of bounding the mixing time with cuts, we bound it with cuts in graphs obtained by Schur complementing out vertices from the graph G. Combinatorially, these Schur complements describe random walks in G restricted to a subset of its vertices. As a result, all Schur complement cuts have conductance at least Omega(lambda_G). We show that unlike with cuts, this inequality is tight up to a constant factor. Specifically, there is a Schur complement cut with conductance at most O(lambda_G).

BibTeX - Entry

@InProceedings{schild:LIPIcs:2018:10158,
  author =	{Aaron Schild},
  title =	{{A Schur Complement Cheeger Inequality}},
  booktitle =	{10th Innovations in Theoretical Computer Science  Conference (ITCS 2019)},
  pages =	{65:1--65:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{124},
  editor =	{Avrim Blum},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10158},
  URN =		{urn:nbn:de:0030-drops-101588},
  doi =		{10.4230/LIPIcs.ITCS.2019.65},
  annote =	{Keywords: electrical networks, Cheeger's inequality, mixing time, conductance, Schur complements}
}

Keywords: electrical networks, Cheeger's inequality, mixing time, conductance, Schur complements
Collection: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Issue Date: 2018
Date of publication: 08.01.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI