2 Search Results for "Shaydulin, Ruslan"

Document
DOI: 10.4230/LIPIcs.ITCS.2022.14
Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs

Authors: Boaz Barak and Kunal Marwaha

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

Abstract
We study the performance of local quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) for the maximum cut problem, and their relationship to that of randomized classical algorithms. 1) We prove that every (quantum or classical) one-local algorithm (where the value of a vertex only depends on its and its neighbors' state) achieves on D-regular graphs of girth > 5 a maximum cut of at most 1/2 + C/√D for C = 1/√2 ≈ 0.7071. This is the first such result showing that one-local algorithms achieve a value that is bounded away from the true optimum for random graphs, which is 1/2 + P_*/√D + o(1/√D) for P_* ≈ 0.7632 [Dembo et al., 2017]. 2) We show that there is a classical k-local algorithm that achieves a value of 1/2 + C/√D - O(1/√k) for D-regular graphs of girth > 2k+1, where C = 2/π ≈ 0.6366. This is an algorithmic version of the existential bound of [Lyons, 2017] and is related to the algorithm of [Aizenman et al., 1987] (ALR) for the Sherrington-Kirkpatrick model. This bound is better than that achieved by the one-local and two-local versions of QAOA on high-girth graphs [M. B. Hastings, 2019; Marwaha, 2021]. 3) Through computational experiments, we give evidence that the ALR algorithm achieves better performance than constant-locality QAOA for random D-regular graphs, as well as other natural instances, including graphs that do have short cycles. While our theoretical bounds require the locality and girth assumptions, our experimental work suggests that it could be possible to extend them beyond these constraints. This points at the tantalizing possibility that O(1)-local quantum maximum-cut algorithms might be pointwise dominated by polynomial-time classical algorithms, in the sense that there is a classical algorithm outputting cuts of equal or better quality on every possible instance. This is in contrast to the evidence that polynomial-time algorithms cannot simulate the probability distributions induced by local quantum algorithms.
Cite as

Boaz Barak and Kunal Marwaha. Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{barak_et_al:LIPIcs.ITCS.2022.14,
  author =	{Barak, Boaz and Marwaha, Kunal},
  title =	{{Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{14:1--14:21},
  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.14},
  URN =		{urn:nbn:de:0030-drops-156105},
  doi =		{10.4230/LIPIcs.ITCS.2022.14},
  annote =	{Keywords: approximation algorithms, QAOA, maximum cut, local distributions}
}
Document
DOI: 10.4230/LIPIcs.SEA.2018.2
Aggregative Coarsening for Multilevel Hypergraph Partitioning

Authors: Ruslan Shaydulin and Ilya Safro

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract
Algorithms for many hypergraph problems, including partitioning, utilize multilevel frameworks to achieve a good trade-off between the performance and the quality of results. In this paper we introduce two novel aggregative coarsening schemes and incorporate them within state-of-the-art hypergraph partitioner Zoltan. Our coarsening schemes are inspired by the algebraic multigrid and stable matching approaches. We demonstrate the effectiveness of the developed schemes as a part of multilevel hypergraph partitioning framework on a wide range of problems.
Cite as

Ruslan Shaydulin and Ilya Safro. Aggregative Coarsening for Multilevel Hypergraph Partitioning. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{shaydulin_et_al:LIPIcs.SEA.2018.2,
  author =	{Shaydulin, Ruslan and Safro, Ilya},
  title =	{{Aggregative Coarsening for Multilevel Hypergraph Partitioning}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{2:1--2:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.2},
  URN =		{urn:nbn:de:0030-drops-89371},
  doi =		{10.4230/LIPIcs.SEA.2018.2},
  annote =	{Keywords: hypergraph partitioning, multilevel algorithms, coarsening, matching, combinatorial scientific computing}
}
  • Refine by Author
  • 1 Barak, Boaz
  • 1 Marwaha, Kunal
  • 1 Safro, Ilya
  • 1 Shaydulin, Ruslan

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Hypergraphs
  • 1 Mathematics of computing → Matchings and factors
  • 1 Theory of computation → Approximation algorithms analysis

  • Refine by Keyword
  • 1 QAOA
  • 1 approximation algorithms
  • 1 coarsening
  • 1 combinatorial scientific computing
  • 1 hypergraph partitioning
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact