1 Search Results for "Narayanan, Hariharan"

Document

DOI: 10.4230/LIPIcs.ITCS.2022.108

A Spectral Approach to Polytope Diameter

Authors: Hariharan Narayanan, Rikhav Shah, and Nikhil Srivastava

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract

We prove upper bounds on the graph diameters of polytopes in two settings. The first is a worst-case bound for integer polytopes in terms of the length of the description of the polytope (in bits) and the minimum angle between facets of its polar. The second is a smoothed analysis bound: given an appropriately normalized polytope, we add small Gaussian noise to each constraint. We consider a natural geometric measure on the vertices of the perturbed polytope (corresponding to the mean curvature measure of its polar) and show that with high probability there exists a "giant component" of vertices, with measure 1-o(1) and polynomial diameter. Both bounds rely on spectral gaps - of a certain Schrödinger operator in the first case, and a certain continuous time Markov chain in the second - which arise from the log-concavity of the volume of a simple polytope in terms of its slack variables.

Cite as

Hariharan Narayanan, Rikhav Shah, and Nikhil Srivastava. A Spectral Approach to Polytope Diameter. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 108:1-108:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{narayanan_et_al:LIPIcs.ITCS.2022.108,
  author =	{Narayanan, Hariharan and Shah, Rikhav and Srivastava, Nikhil},
  title =	{{A Spectral Approach to Polytope Diameter}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{108:1--108:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.108},
  URN =		{urn:nbn:de:0030-drops-157044},
  doi =		{10.4230/LIPIcs.ITCS.2022.108},
  annote =	{Keywords: Polytope diameter, Markov Chain}
}

Refine by Author
1 Narayanan, Hariharan
1 Shah, Rikhav
1 Srivastava, Nikhil

Refine by Classification
1 Mathematics of computing → Mathematical optimization
1 Theory of computation → Random walks and Markov chains

Refine by Keyword
1 Markov Chain
1 Polytope diameter

Refine by Type
1 document

Refine by Publication Year
1 2022

1 Search Results for "Narayanan, Hariharan"

A Spectral Approach to Polytope Diameter

Abstract

Cite as

Thanks for your feedback!

Could not send message