Search Results

Documents authored by Schild, Aaron

Document
DOI: 10.4230/LIPIcs.ITCS.2021.83
Sampling Arborescences in Parallel

Authors: Nima Anari, Nathan Hu, Amin Saberi, and Aaron Schild

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We study the problem of sampling a uniformly random directed rooted spanning tree, also known as an arborescence, from a possibly weighted directed graph. Classically, this problem has long been known to be polynomial-time solvable; the exact number of arborescences can be computed by a determinant [Tutte, 1948], and sampling can be reduced to counting [Jerrum et al., 1986; Jerrum and Sinclair, 1996]. However, the classic reduction from sampling to counting seems to be inherently sequential. This raises the question of designing efficient parallel algorithms for sampling. We show that sampling arborescences can be done in RNC. For several well-studied combinatorial structures, counting can be reduced to the computation of a determinant, which is known to be in NC [Csanky, 1975]. These include arborescences, planar graph perfect matchings, Eulerian tours in digraphs, and determinantal point processes. However, not much is known about efficient parallel sampling of these structures. Our work is a step towards resolving this mystery.
Cite as

Nima Anari, Nathan Hu, Amin Saberi, and Aaron Schild. Sampling Arborescences in Parallel. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 83:1-83:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{anari_et_al:LIPIcs.ITCS.2021.83,
  author =	{Anari, Nima and Hu, Nathan and Saberi, Amin and Schild, Aaron},
  title =	{{Sampling Arborescences in Parallel}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{83:1--83:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.83},
  URN =		{urn:nbn:de:0030-drops-136225},
  doi =		{10.4230/LIPIcs.ITCS.2021.83},
  annote =	{Keywords: parallel algorithms, arborescences, spanning trees, random sampling}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.35
Improved Distributed Approximations for Maximum Independent Set

Authors: Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild, and Gregory Schwartzman

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
We present improved results for approximating maximum-weight independent set (MaxIS) in the CONGEST and LOCAL models of distributed computing. Given an input graph, let n and Δ be the number of nodes and maximum degree, respectively, and let MIS(n,Δ) be the running time of finding a maximal independent set (MIS) in the CONGEST model. Bar-Yehuda et al. [PODC 2017] showed that there is an algorithm in the CONGEST model that finds a Δ-approximation for MaxIS in O(MIS(n,Δ)log W) rounds, where W is the maximum weight of a node in the graph, which can be as large as poly (n). Whether their algorithm is deterministic or randomized that succeeds with high probability depends on the MIS algorithm that is used as a black-box. Our results: 1) A deterministic O(MIS(n,Δ)/ε)-round algorithm that finds a (1+ε)Δ-approximation for MaxIS in the CONGEST model. 2) A randomized (poly(log log n)/ε)-round algorithm that finds, with high probability, a (1+ε)Δ-approximation for MaxIS in the CONGEST model. That is, by sacrificing only a tiny fraction of the approximation guarantee, we achieve an exponential speed-up in the running time over the previous best known result. 3) A randomized O(log n⋅ poly(log log n)/ε)-round algorithm that finds, with high probability, a 8(1+ε)α-approximation for MaxIS in the CONGEST model, where α is the arboricity of the graph. For graphs of arboricity α < Δ/(8(1+ε)), this result improves upon the previous best known result in both the approximation factor and the running time. One may wonder whether it is possible to approximate MaxIS with high probability in fewer than poly(log log n) rounds. Interestingly, a folklore randomized ranking algorithm by Boppana implies a single round algorithm that gives an expected Δ-approximation in the CONGEST model. However, it is unclear how to convert this algorithm to one that succeeds with high probability without sacrificing a large number of rounds. For unweighted graphs of maximum degree Δ ≤ n/log n, we show a new analysis of the randomized ranking algorithm, which we combine with the local-ratio technique, to provide a O(1/ε)-round algorithm in the CONGEST model that, with high probability, finds an independent set of size at least n/((1+ε)(Δ+1)). This result cannot be extended to very high degree graphs, as we show a lower bound of Ω(log^*n) rounds for any randomized algorithm that with probability at least 1-1/log n finds an independent set of size Ω(n/Δ). This lower bound holds even for the LOCAL model. The hard instances that we use to prove our lower bound are graphs of maximum degree Δ = Ω(n/log^*n).
Cite as

Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild, and Gregory Schwartzman. Improved Distributed Approximations for Maximum Independent Set. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kawarabayashi_et_al:LIPIcs.DISC.2020.35,
  author =	{Kawarabayashi, Ken-ichi and Khoury, Seri and Schild, Aaron and Schwartzman, Gregory},
  title =	{{Improved Distributed Approximations for Maximum Independent Set}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{35:1--35:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.35},
  URN =		{urn:nbn:de:0030-drops-131135},
  doi =		{10.4230/LIPIcs.DISC.2020.35},
  annote =	{Keywords: Distributed graph algorithms, Approximation algorithms, Lower bounds}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.50
Semi-Online Bipartite Matching

Authors: Ravi Kumar, Manish Purohit, Aaron Schild, Zoya Svitkina, and Erik Vee

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
In this paper we introduce the semi-online model that generalizes the classical online computational model. The semi-online model postulates that the unknown future has a predictable part and an adversarial part; these parts can be arbitrarily interleaved. An algorithm in this model operates as in the standard online model, i.e., makes an irrevocable decision at each step. We consider bipartite matching in the semi-online model. Our main contributions are competitive algorithms for this problem and a near-matching hardness bound. The competitive ratio of the algorithms nicely interpolates between the truly offline setting (i.e., no adversarial part) and the truly online setting (i.e., no predictable part).
Cite as

Ravi Kumar, Manish Purohit, Aaron Schild, Zoya Svitkina, and Erik Vee. Semi-Online Bipartite Matching. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.ITCS.2019.50,
  author =	{Kumar, Ravi and Purohit, Manish and Schild, Aaron and Svitkina, Zoya and Vee, Erik},
  title =	{{Semi-Online Bipartite Matching}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{50:1--50:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.50},
  URN =		{urn:nbn:de:0030-drops-101436},
  doi =		{10.4230/LIPIcs.ITCS.2019.50},
  annote =	{Keywords: Semi-Online Algorithms, Bipartite Matching}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.65
A Schur Complement Cheeger Inequality

Authors: Aaron Schild

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

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).
Cite as

Aaron Schild. A Schur Complement Cheeger Inequality. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 65:1-65:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{schild:LIPIcs.ITCS.2019.65,
  author =	{Schild, Aaron},
  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 =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.65},
  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}
}
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 About DROPS Imprint Privacy Contact