3 Search Results for "He, Yuan"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.98
Construction of Optimal Locally Recoverable Codes and Connection with Hypergraph

Authors: Chaoping Xing and Chen Yuan

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Locally recoverable codes are a class of block codes with an additional property called locality. A locally recoverable code with locality r can recover a symbol by reading at most r other symbols. Recently, it was discovered by several authors that a q-ary optimal locally recoverable code, i.e., a locally recoverable code achieving the Singleton-type bound, can have length much bigger than q+1. In this paper, we present both the upper bound and the lower bound on the length of optimal locally recoverable codes. Our lower bound improves the best known result in [Yuan Luo et al., 2018] for all distance d >= 7. This result is built on the observation of the parity-check matrix equipped with the Vandermonde structure. It turns out that a parity-check matrix with the Vandermonde structure produces an optimal locally recoverable code if it satisfies a certain expansion property for subsets of F_q. To our surprise, this expansion property is then shown to be equivalent to a well-studied problem in extremal graph theory. Our upper bound is derived by an refined analysis of the arguments of Theorem 3.3 in [Venkatesan Guruswami et al., 2018].
Cite as

Chaoping Xing and Chen Yuan. Construction of Optimal Locally Recoverable Codes and Connection with Hypergraph. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 98:1-98:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{xing_et_al:LIPIcs.ICALP.2019.98,
  author =	{Xing, Chaoping and Yuan, Chen},
  title =	{{Construction of Optimal Locally Recoverable Codes and Connection with Hypergraph}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{98:1--98:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.98},
  URN =		{urn:nbn:de:0030-drops-106745},
  doi =		{10.4230/LIPIcs.ICALP.2019.98},
  annote =	{Keywords: Locally Repairable Codes, Hypergraph}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2017.56
Brief Announcement: Compact Topology of Shared-Memory Adversaries

Authors: Petr Kuznetsov, Thibault Rieutord, and Yuan He

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
The paper proposes a simple topological characterization of a large class of adversarial distributed-computing models via affine tasks: sub-complexes of the second iteration of the standard chromatic subdivision. We show that the task computability of a model in the class is precisely captured by iterations of the corresponding affine task. While an adversary is in general defined as a non-compact set of infinite runs, its affine task is just a finite subset of runs of the 2-round iterated immediate snapshot (IIS) model. Our results generalize and improve all previously derived topological characterizations of distributed-computing models.
Cite as

Petr Kuznetsov, Thibault Rieutord, and Yuan He. Brief Announcement: Compact Topology of Shared-Memory Adversaries. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 56:1-56:4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kuznetsov_et_al:LIPIcs.DISC.2017.56,
  author =	{Kuznetsov, Petr and Rieutord, Thibault and He, Yuan},
  title =	{{Brief Announcement: Compact Topology of Shared-Memory Adversaries}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{56:1--56:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.56},
  URN =		{urn:nbn:de:0030-drops-80108},
  doi =		{10.4230/LIPIcs.DISC.2017.56},
  annote =	{Keywords: Adversarial models, Affine tasks, Topological characterization}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.6
Read-Write Memory and k-Set Consensus as an Affine Task

Authors: Eli Gafni, Yuan He, Petr Kuznetsov, and Thibault Rieutord

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
The wait-free read-write memory model has been characterized as an iterated Immediate Snapshot (IS) task. The IS task is affine — it can be defined as a (sub)set of simplices of the standard chromatic subdivision. In this paper, we highlight the phenomenon of a "natural" model that can be captured by an iterated affine task and, thus, by a subset of runs of the iterated immediate snapshot model. We show that the read-write memory model in which, additionally, k-set-consensus objects can be used is "natural" by presenting the corresponding simple affine task captured by a subset of 2-round IS runs. As an "unnatural" example, the model using the abstraction of Weak Symmetry Breaking (WSB) cannot be captured by a set of IS runs and, thus, cannot be represented as an affine task. Our results imply the first combinatorial characterization of models equipped with abstractions other than read-write memory that applies to generic tasks.
Cite as

Eli Gafni, Yuan He, Petr Kuznetsov, and Thibault Rieutord. Read-Write Memory and k-Set Consensus as an Affine Task. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 6:1-6:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gafni_et_al:LIPIcs.OPODIS.2016.6,
  author =	{Gafni, Eli and He, Yuan and Kuznetsov, Petr and Rieutord, Thibault},
  title =	{{Read-Write Memory and k-Set Consensus as an Affine Task}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.6},
  URN =		{urn:nbn:de:0030-drops-70759},
  doi =		{10.4230/LIPIcs.OPODIS.2016.6},
  annote =	{Keywords: iterated affine tasks, k-set consensus, k-concurrency, simplicial complexes, immediate snapshot}
}
  • Refine by Author
  • 2 He, Yuan
  • 2 Kuznetsov, Petr
  • 2 Rieutord, Thibault
  • 1 Gafni, Eli
  • 1 Xing, Chaoping
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Error-correcting codes

  • Refine by Keyword
  • 1 Adversarial models
  • 1 Affine tasks
  • 1 Hypergraph
  • 1 Locally Repairable Codes
  • 1 Topological characterization
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2017
  • 1 2019

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact