Search Results

Documents authored by Ouyang, Minghui

Document
DOI: 10.4230/LIPIcs.ISAAC.2024.45
A Simple Distributed Algorithm for Sparse Fractional Covering and Packing Problems

Authors: Qian Li, Minghui Ouyang, and Yuyi Wang

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
This paper presents a distributed algorithm in the CONGEST model that achieves a (1+ε)-approximation for row-sparse fractional covering problems (RS-FCP) and the dual column-sparse fraction packing problems (CS-FPP). Compared with the best-known (1+ε)-approximation CONGEST algorithm for RS-FCP/CS-FPP developed by Kuhn, Moscibroda, and Wattenhofer (SODA'06), our algorithm is not only much simpler but also significantly improves the dependency on ε.
Cite as

Qian Li, Minghui Ouyang, and Yuyi Wang. A Simple Distributed Algorithm for Sparse Fractional Covering and Packing Problems. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 45:1-45:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ISAAC.2024.45,
  author =	{Li, Qian and Ouyang, Minghui and Wang, Yuyi},
  title =	{{A Simple Distributed Algorithm for Sparse Fractional Covering and Packing Problems}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{45:1--45:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.45},
  URN =		{urn:nbn:de:0030-drops-221726},
  doi =		{10.4230/LIPIcs.ISAAC.2024.45},
  annote =	{Keywords: CONGEST model, row-sparse fractional covering, column-sparse fractional packing, positive linear programming, simple algorithms}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.61
When Can an Expander Code Correct Ω(n) Errors in O(n) Time?

Authors: Kuan Cheng, Minghui Ouyang, Chong Shangguan, and Yuanting Shen

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
Tanner codes are graph-based linear codes whose parity-check matrices can be characterized by a bipartite graph G together with a linear inner code C₀. Expander codes are Tanner codes whose defining bipartite graph G has good expansion property. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that δ and d₀ must satisfy, so that every bipartite expander G with vertex expansion ratio δ and every linear inner code C₀ with minimum distance d₀ together define an expander code that corrects Ω(n) errors in O(n) time? For C₀ being the parity-check code, the landmark work of Sipser and Spielman (IEEE-TIT'96) showed that δ > 3/4 is sufficient; later Viderman (ACM-TOCT'13) improved this to δ > 2/3-Ω(1) and he also showed that δ > 1/2 is necessary. For general linear code C₀, the previously best-known result of Dowling and Gao (IEEE-TIT'18) showed that d₀ = Ω(cδ^{-2}) is sufficient, where c is the left-degree of G. In this paper, we give a near-optimal solution to the above question for general C₀ by showing that δ d₀ > 3 is sufficient and δ d₀ > 1 is necessary, thereby also significantly improving Dowling-Gao’s result. We present two novel algorithms for decoding expander codes, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius.
Cite as

Kuan Cheng, Minghui Ouyang, Chong Shangguan, and Yuanting Shen. When Can an Expander Code Correct Ω(n) Errors in O(n) Time?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 61:1-61:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.APPROX/RANDOM.2024.61,
  author =	{Cheng, Kuan and Ouyang, Minghui and Shangguan, Chong and Shen, Yuanting},
  title =	{{When Can an Expander Code Correct \Omega(n) Errors in O(n) Time?}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{61:1--61:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.61},
  URN =		{urn:nbn:de:0030-drops-210543},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.61},
  annote =	{Keywords: expander codes, expander graphs, linear-time decoding}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.43
Improved Decoding of Expander Codes

Authors: Xue Chen, Kuan Cheng, Xin Li, and Minghui Ouyang

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

Abstract
We study the classical expander codes, introduced by Sipser and Spielman [M. Sipser and D. A. Spielman, 1996]. Given any constants 0 < α, ε < 1/2, and an arbitrary bipartite graph with N vertices on the left, M < N vertices on the right, and left degree D such that any left subset S of size at most α N has at least (1-ε)|S|D neighbors, we show that the corresponding linear code given by parity checks on the right has distance at least roughly {α N}/{2 ε}. This is strictly better than the best known previous result of 2(1-ε) α N [Madhu Sudan, 2000; Viderman, 2013] whenever ε < 1/2, and improves the previous result significantly when ε is small. Furthermore, we show that this distance is tight in general, thus providing a complete characterization of the distance of general expander codes. Next, we provide several efficient decoding algorithms, which vastly improve previous results in terms of the fraction of errors corrected, whenever ε < 1/4. Finally, we also give a bound on the list-decoding radius of general expander codes, which beats the classical Johnson bound in certain situations (e.g., when the graph is almost regular and the code has a high rate). Our techniques exploit novel combinatorial properties of bipartite expander graphs. In particular, we establish a new size-expansion tradeoff, which may be of independent interests.
Cite as

Xue Chen, Kuan Cheng, Xin Li, and Minghui Ouyang. Improved Decoding of Expander Codes. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 43:1-43:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ITCS.2022.43,
  author =	{Chen, Xue and Cheng, Kuan and Li, Xin and Ouyang, Minghui},
  title =	{{Improved Decoding of Expander Codes}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{43:1--43:3},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.43},
  URN =		{urn:nbn:de:0030-drops-156394},
  doi =		{10.4230/LIPIcs.ITCS.2022.43},
  annote =	{Keywords: Expander Code, Decoding}
}
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