2 Search Results for "Liu, Shu"


Document
Track A: Algorithms, Complexity and Games
List Decoding of Rank-Metric Codes with Row-To-Column Ratio Bigger Than 1/2

Authors: Shu Liu, Chaoping Xing, and Chen Yuan

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)


Abstract
Despite numerous results about the list decoding of Hamming-metric codes, development of list decoding on rank-metric codes is not as rapid as its counterpart. The bound of list decoding obeys the Gilbert-Varshamov bound in both the metrics. In the case of the Hamming-metric, the Gilbert-Varshamov bound is a trade-off among rate, decoding radius and alphabet size, while in the case of the rank-metric, the Gilbert-Varshamov bound is a trade-off among rate, decoding radius and column-to-row ratio (i.e., the ratio between the numbers of columns and rows). Hence, alphabet size and column-to-row ratio play a similar role for list decodability in each metric. In the case of the Hamming-metric, it is more challenging to list decode codes over smaller alphabets. In contrast, in the case of the rank-metric, it is more difficult to list decode codes with large column-to-row ratio. In particular, it is extremely difficult to list decode square matrix rank-metric codes (i.e., the column-to-row ratio is equal to 1). The main purpose of this paper is to explicitly construct a class of rank-metric codes 𝒞 of rate R with the column-to-row ratio up to 2/3 and efficiently list decode these codes with decoding radius beyond the decoding radius (1-R)/2 (note that (1-R)/2 is at least half of relative minimum distance δ). In literature, the largest column-to-row ratio of rank-metric codes that can be efficiently list decoded beyond half of minimum distance is 1/2. Thus, it is greatly desired to efficiently design list decoding algorithms for rank-metric codes with the column-to-row ratio bigger than 1/2 or even close to 1. Our key idea is to compress an element of the field F_qⁿ into a smaller F_q-subspace via a linearized polynomial. Thus, the column-to-row ratio gets increased at the price of reducing the code rate. Our result shows that the compression technique is powerful and it has not been employed in the topic of list decoding of both the Hamming and rank metrics. Apart from the above algebraic technique, we follow some standard techniques to prune down the list. The algebraic idea enables us to pin down the message into a structured subspace of dimension linear in the number n of columns. This "periodic" structure allows us to pre-encode the message to prune down the list.

Cite as

Shu Liu, Chaoping Xing, and Chen Yuan. List Decoding of Rank-Metric Codes with Row-To-Column Ratio Bigger Than 1/2. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 89:1-89:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ICALP.2023.89,
  author =	{Liu, Shu and Xing, Chaoping and Yuan, Chen},
  title =	{{List Decoding of Rank-Metric Codes with Row-To-Column Ratio Bigger Than 1/2}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{89:1--89:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.89},
  URN =		{urn:nbn:de:0030-drops-181416},
  doi =		{10.4230/LIPIcs.ICALP.2023.89},
  annote =	{Keywords: Coding theory, List-decoding, Rank-metric codes}
}
Document
Intensional Effect Polymorphism

Authors: Yuheng Long, Yu David Liu, and Hridesh Rajan

Published in: LIPIcs, Volume 37, 29th European Conference on Object-Oriented Programming (ECOOP 2015)


Abstract
Type-and-effect systems are a powerful tool for program construction and verification. We describe intensional effect polymorphism, a new foundation for effect systems that integrates static and dynamic effect checking. Our system allows the effect of polymorphic code to be intensionally inspected through a lightweight notion of dynamic typing. When coupled with parametric polymorphism, the powerful system utilizes runtime information to enable precise effect reasoning, while at the same time retains strong type safety guarantees. We build our ideas on top of an imperative core calculus with regions. The technical innovations of our design include a relational notion of effect checking, the use of bounded existential types to capture the subtle interactions between static typing and dynamic typing, and a differential alignment strategy to achieve efficiency in dynamic typing. We demonstrate the applications of intensional effect polymorphism in concurrent programming, security, graphical user interface access, and memoization.

Cite as

Yuheng Long, Yu David Liu, and Hridesh Rajan. Intensional Effect Polymorphism. In 29th European Conference on Object-Oriented Programming (ECOOP 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 37, pp. 346-370, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{long_et_al:LIPIcs.ECOOP.2015.346,
  author =	{Long, Yuheng and Liu, Yu David and Rajan, Hridesh},
  title =	{{Intensional Effect Polymorphism}},
  booktitle =	{29th European Conference on Object-Oriented Programming (ECOOP 2015)},
  pages =	{346--370},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-86-6},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{37},
  editor =	{Boyland, John Tang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2015.346},
  URN =		{urn:nbn:de:0030-drops-52213},
  doi =		{10.4230/LIPIcs.ECOOP.2015.346},
  annote =	{Keywords: intensional effect polymorphism, type system, hybrid typing}
}
  • Refine by Author
  • 1 Liu, Shu
  • 1 Liu, Yu David
  • 1 Long, Yuheng
  • 1 Rajan, Hridesh
  • 1 Xing, Chaoping
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Coding theory

  • Refine by Keyword
  • 1 Coding theory
  • 1 List-decoding
  • 1 Rank-metric codes
  • 1 hybrid typing
  • 1 intensional effect polymorphism
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2015
  • 1 2023

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