Search | arXiv e-print repository

<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"/> <meta name="viewport" content="width=device-width, initial-scale=1"/>  <link rel="apple-touch-icon" sizes="180x180" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/apple-touch-icon.png"> <link rel="icon" type="image/png" sizes="32x32" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon-32x32.png"> <link rel="icon" type="image/png" sizes="16x16" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon-16x16.png"> <link rel="manifest" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/site.webmanifest"> <link rel="mask-icon" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/safari-pinned-tab.svg" color="#b31b1b"> <link rel="shortcut icon" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon.ico"> <meta name="msapplication-TileColor" content="#b31b1b"> <meta name="msapplication-config" content="images/icons/browserconfig.xml"> <meta name="theme-color" content="#b31b1b">  <title>Search | arXiv e-print repository</title> <script defer src="https://static.arxiv.org/static/base/1.0.0a5/fontawesome-free-5.11.2-web/js/all.js"></script> <link rel="stylesheet" href="https://static.arxiv.org/static/base/1.0.0a5/css/arxivstyle.css" /> <script type="text/x-mathjax-config"> MathJax.Hub.Config({ messageStyle: "none", extensions: ["tex2jax.js"], jax: ["input/TeX", "output/HTML-CSS"], tex2jax: { inlineMath: [ ['$','$'], ["\$","\$"] ], displayMath: [ ['$$','$$'], ["\\[","\\]"] ], processEscapes: true, ignoreClass: '.*', processClass: 'mathjax.*' }, TeX: { extensions: ["AMSmath.js", "AMSsymbols.js", "noErrors.js"], noErrors: { inlineDelimiters: ["$","$"], multiLine: false, style: { "font-size": "normal", "border": "" } } }, "HTML-CSS": { availableFonts: ["TeX"] } }); </script> <script src='//static.arxiv.org/MathJax-2.7.3/MathJax.js'></script> <script src="https://static.arxiv.org/static/base/1.0.0a5/js/notification.js"></script> <link rel="stylesheet" href="https://static.arxiv.org/static/search/0.5.6/css/bulma-tooltip.min.css" /> <link rel="stylesheet" href="https://static.arxiv.org/static/search/0.5.6/css/search.css" /> <script src="https://code.jquery.com/jquery-3.2.1.slim.min.js" integrity="sha256-k2WSCIexGzOj3Euiig+TlR8gA0EmPjuc79OEeY5L45g=" crossorigin="anonymous"></script> <script src="https://static.arxiv.org/static/search/0.5.6/js/fieldset.js"></script> <style> radio#cf-customfield_11400 { display: none; } </style> </head> <body> <header><a href="#main-container" class="is-sr-only">Skip to main content</a>  <div class="attribution level is-marginless" role="banner"> <div class="level-left"> <a class="level-item" href="https://cornell.edu/"><img src="https://static.arxiv.org/static/base/1.0.0a5/images/cornell-reduced-white-SMALL.svg" alt="Cornell University" width="200" aria-label="logo" /></a> </div> <div class="level-right is-marginless"><p class="sponsors level-item is-marginless"><span id="support-ack-url">We gratefully acknowledge support from<br /> the Simons Foundation, <a href="https://info.arxiv.org/about/ourmembers.html">member institutions</a>, and all contributors. <a href="https://info.arxiv.org/about/donate.html">Donate</a></span></p></div> </div>  <div class="identity level is-marginless"> <div class="level-left"> <div class="level-item"> <a class="arxiv" href="https://arxiv.org/" aria-label="arxiv-logo"> <img src="https://static.arxiv.org/static/base/1.0.0a5/images/arxiv-logo-one-color-white.svg" aria-label="logo" alt="arxiv logo" width="85" style="width:85px;"/> </a> </div> </div> <div class="search-block level-right"> <form class="level-item mini-search" method="GET" action="https://arxiv.org/search"> <div class="field has-addons"> <div class="control"> <input class="input is-small" type="text" name="query" placeholder="Search..." aria-label="Search term or terms" /> <p class="help"><a href="https://info.arxiv.org/help">Help</a> | <a href="https://arxiv.org/search/advanced">Advanced Search</a></p> </div> <div class="control"> <div class="select is-small"> <select name="searchtype" aria-label="Field to search"> <option value="all" selected="selected">All fields</option> <option value="title">Title</option> <option value="author">Author</option> <option value="abstract">Abstract</option> <option value="comments">Comments</option> <option value="journal_ref">Journal reference</option> <option value="acm_class">ACM classification</option> <option value="msc_class">MSC classification</option> <option value="report_num">Report number</option> <option value="paper_id">arXiv identifier</option> <option value="doi">DOI</option> <option value="orcid">ORCID</option> <option value="author_id">arXiv author ID</option> <option value="help">Help pages</option> <option value="full_text">Full text</option> </select> </div> </div> <input type="hidden" name="source" value="header"> <button class="button is-small is-cul-darker">Search</button> </div> </form> </div> </div>  <div class="container"> <div class="user-tools is-size-7 has-text-right has-text-weight-bold" role="navigation" aria-label="User menu"> <a href="https://arxiv.org/login">Login</a> </div> </div> </header> <main class="container" id="main-container"> <div class="level is-marginless"> <div class="level-left"> <h1 class="title is-clearfix"> Showing 1–50 of 67 results for author: <span class="mathjax">Kiah, H M</span> </h1> </div> <div class="level-right is-hidden-mobile">  <span class="help" style="display: inline-block;"><a href="https://github.com/arXiv/arxiv-search/releases">Search v0.5.6 released 2020-02-24</a>  </span> </div> </div> <div class="content"> <form method="GET" action="/search/" aria-role="search"> <div class="field has-addons-tablet"> <div class="control is-expanded"> <label for="query" class="hidden-label">Search term or terms</label> <input class="input is-medium" id="query" name="query" placeholder="Search term..." type="text" value="Kiah, H M"> </div> <div class="select control is-medium"> <label class="is-hidden" for="searchtype">Field</label> <select class="is-medium" id="searchtype" name="searchtype"><option value="all">All fields</option><option value="title">Title</option><option selected value="author">Author(s)</option><option value="abstract">Abstract</option><option value="comments">Comments</option><option value="journal_ref">Journal reference</option><option value="acm_class">ACM classification</option><option value="msc_class">MSC classification</option><option value="report_num">Report number</option><option value="paper_id">arXiv identifier</option><option value="doi">DOI</option><option value="orcid">ORCID</option><option value="license">License (URI)</option><option value="author_id">arXiv author ID</option><option value="help">Help pages</option><option value="full_text">Full text</option></select> </div> <div class="control"> <button class="button is-link is-medium">Search</button> </div> </div> <div class="field"> <div class="control is-size-7"> <label class="radio"> <input checked id="abstracts-0" name="abstracts" type="radio" value="show"> Show abstracts </label> <label class="radio"> <input id="abstracts-1" name="abstracts" type="radio" value="hide"> Hide abstracts </label> </div> </div> <div class="is-clearfix" style="height: 2.5em"> <div class="is-pulled-right"> <a href="/search/advanced?terms-0-term=Kiah%2C+H+M&terms-0-field=author&size=50&order=-announced_date_first">Advanced Search</a> </div> </div> <input type="hidden" name="order" value="-announced_date_first"> <input type="hidden" name="size" value="50"> </form> <div class="level breathe-horizontal"> <div class="level-left"> <form method="GET" action="/search/"> <div style="display: none;"> <select id="searchtype" name="searchtype"><option value="all">All fields</option><option value="title">Title</option><option selected value="author">Author(s)</option><option value="abstract">Abstract</option><option value="comments">Comments</option><option value="journal_ref">Journal reference</option><option value="acm_class">ACM classification</option><option value="msc_class">MSC classification</option><option value="report_num">Report number</option><option value="paper_id">arXiv identifier</option><option value="doi">DOI</option><option value="orcid">ORCID</option><option value="license">License (URI)</option><option value="author_id">arXiv author ID</option><option value="help">Help pages</option><option value="full_text">Full text</option></select> <input id="query" name="query" type="text" value="Kiah, H M"> <ul id="abstracts"><li><input checked id="abstracts-0" name="abstracts" type="radio" value="show"> <label for="abstracts-0">Show abstracts</label></li><li><input id="abstracts-1" name="abstracts" type="radio" value="hide"> <label for="abstracts-1">Hide abstracts</label></li></ul> </div> <div class="box field is-grouped is-grouped-multiline level-item"> <div class="control"> <span class="select is-small"> <select id="size" name="size"><option value="25">25</option><option selected value="50">50</option><option value="100">100</option><option value="200">200</option></select> </span> <label for="size">results per page</label>. </div> <div class="control"> <label for="order">Sort results by</label> <span class="select is-small"> <select id="order" name="order"><option selected value="-announced_date_first">Announcement date (newest first)</option><option value="announced_date_first">Announcement date (oldest first)</option><option value="-submitted_date">Submission date (newest first)</option><option value="submitted_date">Submission date (oldest first)</option><option value="">Relevance</option></select> </span> </div> <div class="control"> <button class="button is-small is-link">Go</button> </div> </div> </form> </div> </div> <nav class="pagination is-small is-centered breathe-horizontal" role="navigation" aria-label="pagination"> <a href="" class="pagination-previous is-invisible">Previous </a> <a href="/search/?searchtype=author&query=Kiah%2C+H+M&start=50" class="pagination-next" >Next </a> <ul class="pagination-list"> <li> <a href="/search/?searchtype=author&query=Kiah%2C+H+M&start=0" class="pagination-link is-current" aria-label="Goto page 1">1 </a> </li> <li> <a href="/search/?searchtype=author&query=Kiah%2C+H+M&start=50" class="pagination-link " aria-label="Page 2" aria-current="page">2 </a> </li> </ul> </nav> <ol class="breathe-horizontal" start="1"> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2410.14417">arXiv:2410.14417</a> <span> [<a href="https://arxiv.org/pdf/2410.14417">pdf</a>, <a href="https://arxiv.org/ps/2410.14417">ps</a>, <a href="https://arxiv.org/format/2410.14417">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> </div> </div> <p class="title is-5 mathjax"> Pairs in Nested Steiner Quadruple Systems </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Chee%2C+Y+M">Yeow Meng Chee</a>, <a href="/search/?searchtype=author&query=Dau%2C+S+H">Son Hoang Dau</a>, <a href="/search/?searchtype=author&query=Etzion%2C+T">Tuvi Etzion</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Zhang%2C+W">Wenqin Zhang</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2410.14417v1-abstract-short" style="display: inline;"> Motivated by a repair problem for fractional repetition codes in distributed storage, each block of any Steiner quadruple system (SQS) of order $v$ is partitioned into two pairs. Each pair in such a partition is called a nested design pair and its multiplicity is the number of times it is a pair in this partition. Such a partition of each block is considered as a new block design called a nested S… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2410.14417v1-abstract-full').style.display = 'inline'; document.getElementById('2410.14417v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2410.14417v1-abstract-full" style="display: none;"> Motivated by a repair problem for fractional repetition codes in distributed storage, each block of any Steiner quadruple system (SQS) of order $v$ is partitioned into two pairs. Each pair in such a partition is called a nested design pair and its multiplicity is the number of times it is a pair in this partition. Such a partition of each block is considered as a new block design called a nested Steiner quadruple system. Several related questions on this type of design are considered in this paper: What is the maximum multiplicity of the nested design pair with minimum multiplicity? What is the minimum multiplicity of the nested design pair with maximum multiplicity? Are there nested quadruple systems in which all the nested design pairs have the same multiplicity? Of special interest are nested quadruple systems in which all the $\binom{v}{2}$ pairs are nested design pairs with the same multiplicity. Several constructions of nested quadruple systems are considered and in particular classic constructions of SQS are examined. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2410.14417v1-abstract-full').style.display = 'none'; document.getElementById('2410.14417v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 18 October, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2405.07180">arXiv:2405.07180</a> <span> [<a href="https://arxiv.org/pdf/2405.07180">pdf</a>, <a href="https://arxiv.org/format/2405.07180">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Repairing Reed-Solomon Codes with Side Information </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Dinh%2C+T+X">Thi Xinh Dinh</a>, <a href="/search/?searchtype=author&query=Le%2C+B+T">Ba Thong Le</a>, <a href="/search/?searchtype=author&query=Dau%2C+S+H">Son Hoang Dau</a>, <a href="/search/?searchtype=author&query=Boztas%2C+S">Serdar Boztas</a>, <a href="/search/?searchtype=author&query=Kruglik%2C+S">Stanislav Kruglik</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Viterbo%2C+E">Emanuele Viterbo</a>, <a href="/search/?searchtype=author&query=Etzion%2C+T">Tuvi Etzion</a>, <a href="/search/?searchtype=author&query=Chee%2C+Y+M">Yeow Meng Chee</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2405.07180v1-abstract-short" style="display: inline;"> We generalize the problem of recovering a lost/erased symbol in a Reed-Solomon code to the scenario in which some side information about the lost symbol is known. The side information is represented as a set $S$ of linearly independent combinations of the sub-symbols of the lost symbol. When $S = \varnothing$, this reduces to the standard problem of repairing a single codeword symbol. When $S$ is… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.07180v1-abstract-full').style.display = 'inline'; document.getElementById('2405.07180v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2405.07180v1-abstract-full" style="display: none;"> We generalize the problem of recovering a lost/erased symbol in a Reed-Solomon code to the scenario in which some side information about the lost symbol is known. The side information is represented as a set $S$ of linearly independent combinations of the sub-symbols of the lost symbol. When $S = \varnothing$, this reduces to the standard problem of repairing a single codeword symbol. When $S$ is a set of sub-symbols of the erased one, this becomes the repair problem with partially lost/erased symbol. We first establish that the minimum repair bandwidth depends on $|S|$ and not the content of $S$ and construct a lower bound on the repair bandwidth of a linear repair scheme with side information $S$. We then consider the well-known subspace-polynomial repair schemes and show that their repair bandwidths can be optimized by choosing the right subspaces. Finally, we demonstrate several parameter regimes where the optimal bandwidths can be achieved for full-length Reed-Solomon codes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.07180v1-abstract-full').style.display = 'none'; document.getElementById('2405.07180v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 12 May, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 94B05; 94B60 <span class="has-text-black-bis has-text-weight-semibold">ACM Class:</span> E.4 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2405.06870">arXiv:2405.06870</a> <span> [<a href="https://arxiv.org/pdf/2405.06870">pdf</a>, <a href="https://arxiv.org/format/2405.06870">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Noise-Tolerant Codebooks for Semi-Quantitative Group Testing: Application to Spatial Genomics </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Chen%2C+K+H">Kok Hao Chen</a>, <a href="/search/?searchtype=author&query=Dao%2C+D+T">Duc Tu Dao</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Pham%2C+V+L+P">Van Long Phuoc Pham</a>, <a href="/search/?searchtype=author&query=Yaakobi%2C+E">Eitan Yaakobi</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2405.06870v1-abstract-short" style="display: inline;"> Motivated by applications in spatial genomics, we revisit group testing (Dorfman~1943) and propose the class of $位$-{\sf ADD}-codes, studying such codes with certain distance $d$ and codelength $n$. When $d$ is constant, we provide explicit code constructions with rates close to $1/2$. When $d$ is proportional to $n$, we provide a GV-type lower bound whose rates are efficiently computable. Upper b… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.06870v1-abstract-full').style.display = 'inline'; document.getElementById('2405.06870v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2405.06870v1-abstract-full" style="display: none;"> Motivated by applications in spatial genomics, we revisit group testing (Dorfman~1943) and propose the class of $位$-{\sf ADD}-codes, studying such codes with certain distance $d$ and codelength $n$. When $d$ is constant, we provide explicit code constructions with rates close to $1/2$. When $d$ is proportional to $n$, we provide a GV-type lower bound whose rates are efficiently computable. Upper bounds for such codes are also studied. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.06870v1-abstract-full').style.display = 'none'; document.getElementById('2405.06870v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 10 May, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">To appear in ISIT 2024 Proceedings</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2405.06583">arXiv:2405.06583</a> <span> [<a href="https://arxiv.org/pdf/2405.06583">pdf</a>, <a href="https://arxiv.org/format/2405.06583">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Private Repair of a Single Erasure in Reed-Solomon Codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Kruglik%2C+S">Stanislav Kruglik</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Dau%2C+S+H">Son Hoang Dau</a>, <a href="/search/?searchtype=author&query=Yaakobi%2C+E">Eitan Yaakobi</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2405.06583v1-abstract-short" style="display: inline;"> We investigate the problem of privately recovering a single erasure for Reed-Solomon codes with low communication bandwidths. For an $[n,k]_{q^\ell}$ code with $n-k\geq q^{m}+t-1$, we construct a repair scheme that allows a client to recover an arbitrary codeword symbol without leaking its index to any set of $t$ colluding helper nodes at a repair bandwidth of $(n-1)(\ell-m)$ sub-symbols in… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.06583v1-abstract-full').style.display = 'inline'; document.getElementById('2405.06583v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2405.06583v1-abstract-full" style="display: none;"> We investigate the problem of privately recovering a single erasure for Reed-Solomon codes with low communication bandwidths. For an $[n,k]_{q^\ell}$ code with $n-k\geq q^{m}+t-1$, we construct a repair scheme that allows a client to recover an arbitrary codeword symbol without leaking its index to any set of $t$ colluding helper nodes at a repair bandwidth of $(n-1)(\ell-m)$ sub-symbols in $\mathbb{F}_q$. When $t=1$, this reduces to the bandwidth of existing repair schemes based on subspace polynomials. We prove the optimality of the proposed scheme when $n=q^\ell$ under a reasonable assumption about the schemes being used. Our private repair scheme can also be transformed into a private retrieval scheme for data encoded by Reed-Solomon codes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.06583v1-abstract-full').style.display = 'none'; document.getElementById('2405.06583v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 10 May, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Full version of the paper accepted for the 2024 IEEE International Symposium on Information Theory (ISIT)</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2405.03614">arXiv:2405.03614</a> <span> [<a href="https://arxiv.org/pdf/2405.03614">pdf</a>, <a href="https://arxiv.org/ps/2405.03614">ps</a>, <a href="https://arxiv.org/format/2405.03614">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Repairing with Zero Skip Cost </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Zhang%2C+W">Wenqin Zhang</a>, <a href="/search/?searchtype=author&query=Chee%2C+Y+M">Yeow Meng Chee</a>, <a href="/search/?searchtype=author&query=Dau%2C+S+H">Son Hoang Dau</a>, <a href="/search/?searchtype=author&query=Etzion%2C+T">Tuvi Etzion</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Luo%2C+Y">Yuan Luo</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2405.03614v1-abstract-short" style="display: inline;"> To measure repair latency at helper nodes, we introduce a new metric called skip cost that quantifies the number of contiguous sections accessed on a disk. We provide explicit constructions of zigzag codes and fractional repetition codes that incur zero skip cost </span> <span class="abstract-full has-text-grey-dark mathjax" id="2405.03614v1-abstract-full" style="display: none;"> To measure repair latency at helper nodes, we introduce a new metric called skip cost that quantifies the number of contiguous sections accessed on a disk. We provide explicit constructions of zigzag codes and fractional repetition codes that incur zero skip cost <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.03614v1-abstract-full').style.display = 'none'; document.getElementById('2405.03614v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 6 May, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2405.02080">arXiv:2405.02080</a> <span> [<a href="https://arxiv.org/pdf/2405.02080">pdf</a>, <a href="https://arxiv.org/ps/2405.02080">ps</a>, <a href="https://arxiv.org/format/2405.02080">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Coding for Synthesis Defects </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Lu%2C+Z">Ziyang Lu</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Zhang%2C+Y">Yiwei Zhang</a>, <a href="/search/?searchtype=author&query=Grass%2C+R+N">Robert N. Grass</a>, <a href="/search/?searchtype=author&query=Yaakobi%2C+E">Eitan Yaakobi</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2405.02080v1-abstract-short" style="display: inline;"> Motivated by DNA based data storage system, we investigate the errors that occur when synthesizing DNA strands in parallel, where each strand is appended one nucleotide at a time by the machine according to a template supersequence. If there is a cycle such that the machine fails, then the strands meant to be appended at this cycle will not be appended, and we refer to this as a synthesis defect.… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.02080v1-abstract-full').style.display = 'inline'; document.getElementById('2405.02080v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2405.02080v1-abstract-full" style="display: none;"> Motivated by DNA based data storage system, we investigate the errors that occur when synthesizing DNA strands in parallel, where each strand is appended one nucleotide at a time by the machine according to a template supersequence. If there is a cycle such that the machine fails, then the strands meant to be appended at this cycle will not be appended, and we refer to this as a synthesis defect. In this paper, we present two families of codes correcting synthesis defects, which are t-known-synthesis-defect correcting codes and t-synthesis-defect correcting codes. For the first one, it is assumed that the defective cycles are known, and each of the codeword is a quaternary sequence. We provide constructions for this family of codes for t = 1, 2, with redundancy log 4 and log n+18 log 3, respectively. For the second one, the codeword is a set of M ordered sequences, and we give constructions for t = 1, 2 to show a strategy for constructing this family of codes. Finally, we derive a lower bound on the redundancy for single-known-synthesis-defect correcting codes, which assures that our construction is almost optimal. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.02080v1-abstract-full').style.display = 'none'; document.getElementById('2405.02080v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 3 May, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2403.20170">arXiv:2403.20170</a> <span> [<a href="https://arxiv.org/pdf/2403.20170">pdf</a>, <a href="https://arxiv.org/ps/2403.20170">ps</a>, <a href="https://arxiv.org/format/2403.20170">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Recovery Sets of Subspaces from a Simplex Code </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Chee%2C+Y+M">Yeow Meng Chee</a>, <a href="/search/?searchtype=author&query=Etzion%2C+T">Tuvi Etzion</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Zhang%2C+H">Hui Zhang</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2403.20170v1-abstract-short" style="display: inline;"> Recovery sets for vectors and subspaces are important in the construction of distributed storage system codes. These concepts are also interesting in their own right. In this paper, we consider the following very basic recovery question: what is the maximum number of possible pairwise disjoint recovery sets for each recovered element? The recovered elements in this work are d-dimensional subspaces… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2403.20170v1-abstract-full').style.display = 'inline'; document.getElementById('2403.20170v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2403.20170v1-abstract-full" style="display: none;"> Recovery sets for vectors and subspaces are important in the construction of distributed storage system codes. These concepts are also interesting in their own right. In this paper, we consider the following very basic recovery question: what is the maximum number of possible pairwise disjoint recovery sets for each recovered element? The recovered elements in this work are d-dimensional subspaces of a $k$-dimensional vector space over GF(q). Each server stores one representative for each distinct one-dimensional subspace of the k-dimensional vector space, or equivalently a distinct point of PG(k-1,q). As column vectors, the associated vectors of the stored one-dimensional subspaces form the generator matrix of the $[(q^k -1)/(q-1),k,q^{k-1}]$ simplex code over GF(q). Lower bounds and upper bounds on the maximum number of such recovery sets are provided. It is shown that generally, these bounds are either tight or very close to being tight. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2403.20170v1-abstract-full').style.display = 'none'; document.getElementById('2403.20170v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 29 March, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2403.15827">arXiv:2403.15827</a> <span> [<a href="https://arxiv.org/pdf/2403.15827">pdf</a>, <a href="https://arxiv.org/ps/2403.15827">ps</a>, <a href="https://arxiv.org/format/2403.15827">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Permutation Recovery Problem against Deletion Errors for DNA Data Storage </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Singhvi%2C+S">Shubhransh Singhvi</a>, <a href="/search/?searchtype=author&query=Gupta%2C+C">Charchit Gupta</a>, <a href="/search/?searchtype=author&query=Boruchovsky%2C+A">Avital Boruchovsky</a>, <a href="/search/?searchtype=author&query=Goldberg%2C+Y">Yuval Goldberg</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Yaakobi%2C+E">Eitan Yaakobi</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2403.15827v1-abstract-short" style="display: inline;"> Owing to its immense storage density and durability, DNA has emerged as a promising storage medium. However, due to technological constraints, data can only be written onto many short DNA molecules called data blocks that are stored in an unordered way. To handle the unordered nature of DNA data storage systems, a unique address is typically prepended to each data block to form a DNA strand. Howev… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2403.15827v1-abstract-full').style.display = 'inline'; document.getElementById('2403.15827v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2403.15827v1-abstract-full" style="display: none;"> Owing to its immense storage density and durability, DNA has emerged as a promising storage medium. However, due to technological constraints, data can only be written onto many short DNA molecules called data blocks that are stored in an unordered way. To handle the unordered nature of DNA data storage systems, a unique address is typically prepended to each data block to form a DNA strand. However, DNA storage systems are prone to errors and generate multiple noisy copies of each strand called DNA reads. Thus, we study the permutation recovery problem against deletions errors for DNA data storage. The permutation recovery problem for DNA data storage requires one to reconstruct the addresses or in other words to uniquely identify the noisy reads. By successfully reconstructing the addresses, one can essentially determine the correct order of the data blocks, effectively solving the clustering problem. We first show that we can almost surely identify all the noisy reads under certain mild assumptions. We then propose a permutation recovery procedure and analyze its complexity. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2403.15827v1-abstract-full').style.display = 'none'; document.getElementById('2403.15827v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 23 March, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">arXiv admin note: substantial text overlap with arXiv:2305.04597</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2403.07754">arXiv:2403.07754</a> <span> [<a href="https://arxiv.org/pdf/2403.07754">pdf</a>, <a href="https://arxiv.org/format/2403.07754">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> An Optimal Sequence Reconstruction Algorithm for Reed-Solomon Codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Singhvi%2C+S">Shubhransh Singhvi</a>, <a href="/search/?searchtype=author&query=Con%2C+R">Roni Con</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Yaakobi%2C+E">Eitan Yaakobi</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2403.07754v1-abstract-short" style="display: inline;"> The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a scenario where the sender transmits a codeword from some codebook, and the receiver obtains $N$ noisy outputs of the codeword. We study the problem of efficient reconstruction using $N$ outputs that are each corrupted by at most $t$ substitutions. Specifically, for the ubiquitous Reed-Solomon codes, we adapt the Ko… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2403.07754v1-abstract-full').style.display = 'inline'; document.getElementById('2403.07754v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2403.07754v1-abstract-full" style="display: none;"> The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a scenario where the sender transmits a codeword from some codebook, and the receiver obtains $N$ noisy outputs of the codeword. We study the problem of efficient reconstruction using $N$ outputs that are each corrupted by at most $t$ substitutions. Specifically, for the ubiquitous Reed-Solomon codes, we adapt the Koetter-Vardy soft-decoding algorithm, presenting a reconstruction algorithm capable of correcting beyond Johnson radius. Furthermore, the algorithm uses $\mathcal{O}(nN)$ field operations, where $n$ is the codeword length. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2403.07754v1-abstract-full').style.display = 'none'; document.getElementById('2403.07754v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 12 March, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Submitted to IEEE ISIT 2024</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2402.18869">arXiv:2402.18869</a> <span> [<a href="https://arxiv.org/pdf/2402.18869">pdf</a>, <a href="https://arxiv.org/format/2402.18869">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> </div> </div> <p class="title is-5 mathjax"> Evaluating the Gilbert-Varshamov Bound for Constrained Systems </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Goyal%2C+K">Keshav Goyal</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2402.18869v1-abstract-short" style="display: inline;"> We revisit the well-known Gilbert-Varshamov (GV) bound for constrained systems. In 1991, Kolesnik and Krachkovsky showed that GV bound can be determined via the solution of some optimization problem. Later, Marcus and Roth (1992) modified the optimization problem and improved the GV bound in many instances. In this work, we provide explicit numerical procedures to solve these two optimization prob… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2402.18869v1-abstract-full').style.display = 'inline'; document.getElementById('2402.18869v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2402.18869v1-abstract-full" style="display: none;"> We revisit the well-known Gilbert-Varshamov (GV) bound for constrained systems. In 1991, Kolesnik and Krachkovsky showed that GV bound can be determined via the solution of some optimization problem. Later, Marcus and Roth (1992) modified the optimization problem and improved the GV bound in many instances. In this work, we provide explicit numerical procedures to solve these two optimization problems and hence, compute the bounds. We then show the procedures can be further simplified when we plot the respective curves. In the case where the graph presentation comprise a single state, we provide explicit formulas for both bounds. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2402.18869v1-abstract-full').style.display = 'none'; document.getElementById('2402.18869v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 29 February, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">27 Pages, 5 figures, submitted to Entropy</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2402.14712">arXiv:2402.14712</a> <span> [<a href="https://arxiv.org/pdf/2402.14712">pdf</a>, <a href="https://arxiv.org/format/2402.14712">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1109/TIT.2024.3483303">10.1109/TIT.2024.3483303 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Gilbert-Varshamov Bound for Codes in $L_1$ Metric using Multivariate Analytic Combinatorics </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Goyal%2C+K">Keshav Goyal</a>, <a href="/search/?searchtype=author&query=Dao%2C+D+T">Duc Tu Dao</a>, <a href="/search/?searchtype=author&query=Kova%C4%8Devi%C4%87%2C+M">Mladen Kova膷evi膰</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2402.14712v1-abstract-short" style="display: inline;"> Analytic combinatorics in several variables refers to a suite of tools that provide sharp asymptotic estimates for certain combinatorial quantities. In this paper, we apply these tools to determine the Gilbert--Varshamov lower bound on the rate of optimal codes in $L_1$ metric. Several different code spaces are analyzed, including the simplex and the hypercube in $\mathbb{Z^n}$, all of which are i… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2402.14712v1-abstract-full').style.display = 'inline'; document.getElementById('2402.14712v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2402.14712v1-abstract-full" style="display: none;"> Analytic combinatorics in several variables refers to a suite of tools that provide sharp asymptotic estimates for certain combinatorial quantities. In this paper, we apply these tools to determine the Gilbert--Varshamov lower bound on the rate of optimal codes in $L_1$ metric. Several different code spaces are analyzed, including the simplex and the hypercube in $\mathbb{Z^n}$, all of which are inspired by concrete data storage and transmission models such as the sticky insertion channel, the permutation channel, the adjacent transposition (bit-shift) channel, the multilevel flash memory channel, etc. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2402.14712v1-abstract-full').style.display = 'none'; document.getElementById('2402.14712v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 22 February, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">33 pages, 3 figures, submitted to IEEE Transactions on Information Theory</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> IEEE Trans. Inform. Theory, vol. 71, no. 1, pp. 244-262, 2025 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2305.07274">arXiv:2305.07274</a> <span> [<a href="https://arxiv.org/pdf/2305.07274">pdf</a>, <a href="https://arxiv.org/format/2305.07274">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Deletion Correcting Codes for Efficient DNA Synthesis </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Chrisnata%2C+J">Johan Chrisnata</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Pham%2C+V+L+P">Van Long Phuoc Pham</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2305.07274v1-abstract-short" style="display: inline;"> The synthesis of DNA strands remains the most costly part of the DNA storage system. Thus, to make DNA storage system more practical, the time and materials used in the synthesis process have to be optimized. We consider the most common type of synthesis process where multiple DNA strands are synthesized in parallel from a common alternating supersequence, one nucleotide at a time. The synthesis t… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.07274v1-abstract-full').style.display = 'inline'; document.getElementById('2305.07274v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2305.07274v1-abstract-full" style="display: none;"> The synthesis of DNA strands remains the most costly part of the DNA storage system. Thus, to make DNA storage system more practical, the time and materials used in the synthesis process have to be optimized. We consider the most common type of synthesis process where multiple DNA strands are synthesized in parallel from a common alternating supersequence, one nucleotide at a time. The synthesis time or the number of synthesis cycles is then determined by the length of this common supersequence. In this model, we design quaternary codes that minimizes synthesis time that can correct deletions or insertions, which are the most prevalent types of error in array-based synthesis. We also propose polynomial-time algorithms that encode binary strings into these codes and show that the rate is close to capacity. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.07274v1-abstract-full').style.display = 'none'; document.getElementById('2305.07274v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 12 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">A shorter version of this paper will be presented in in ISIT 2023</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2305.04597">arXiv:2305.04597</a> <span> [<a href="https://arxiv.org/pdf/2305.04597">pdf</a>, <a href="https://arxiv.org/format/2305.04597">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Data-Driven Bee Identification for DNA Strands </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Singhvi%2C+S">Shubhransh Singhvi</a>, <a href="/search/?searchtype=author&query=Boruchovsky%2C+A">Avital Boruchovsky</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Yaakobi%2C+E">Eitan Yaakobi</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2305.04597v1-abstract-short" style="display: inline;"> We study a data-driven approach to the bee identification problem for DNA strands. The bee-identification problem, introduced by Tandon et al. (2019), requires one to identify $M$ bees, each tagged by a unique barcode, via a set of $M$ noisy measurements. Later, Chrisnata et al. (2022) extended the model to case where one observes $N$ noisy measurements of each bee, and applied the model to addres… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.04597v1-abstract-full').style.display = 'inline'; document.getElementById('2305.04597v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2305.04597v1-abstract-full" style="display: none;"> We study a data-driven approach to the bee identification problem for DNA strands. The bee-identification problem, introduced by Tandon et al. (2019), requires one to identify $M$ bees, each tagged by a unique barcode, via a set of $M$ noisy measurements. Later, Chrisnata et al. (2022) extended the model to case where one observes $N$ noisy measurements of each bee, and applied the model to address the unordered nature of DNA storage systems. In such systems, a unique address is typically prepended to each DNA data block to form a DNA strand, but the address may possibly be corrupted. While clustering is usually used to identify the address of a DNA strand, this requires $\mathcal{M}^2$ data comparisons (when $\mathcal{M}$ is the number of reads). In contrast, the approach of Chrisnata et al. (2022) avoids data comparisons completely. In this work, we study an intermediate, data-driven approach to this identification task. For the binary erasure channel, we first show that we can almost surely correctly identify all DNA strands under certain mild assumptions. Then we propose a data-driven pruning procedure and demonstrate that on average the procedure uses only a fraction of $\mathcal{M}^2$ data comparisons. Specifically, for $\mathcal{M}= 2^n$ and erasure probability $p$, the expected number of data comparisons performed by the procedure is $魏\mathcal{M}^2$, where $\left(\frac{1+2p-p^2}{2}\right)^n \leq 魏\leq \left(\frac{1+p}{2}\right)^n $. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.04597v1-abstract-full').style.display = 'none'; document.getElementById('2305.04597v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 8 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Conference paper accepted at ISIT 2023</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2305.04439">arXiv:2305.04439</a> <span> [<a href="https://arxiv.org/pdf/2305.04439">pdf</a>, <a href="https://arxiv.org/format/2305.04439">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1109/ISIT54713.2023.10206902">10.1109/ISIT54713.2023.10206902 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Evaluation of the Gilbert-Varshamov Bound using Multivariate Analytic Combinatorics </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Keshav%2C+G">Goyal Keshav</a>, <a href="/search/?searchtype=author&query=Dao%2C+D+T">Duc Tu Dao</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Kovacevic%2C+M">Mladen Kovacevic</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2305.04439v1-abstract-short" style="display: inline;"> Analytic combinatorics in several variables refers to a suite of tools that provide sharp asymptotic estimates for certain combinatorial quantities. In this paper, we apply these tools to determine the Gilbert-Varshamov (GV) bound for the sticky insertion and the constrained-synthesis channel. </span> <span class="abstract-full has-text-grey-dark mathjax" id="2305.04439v1-abstract-full" style="display: none;"> Analytic combinatorics in several variables refers to a suite of tools that provide sharp asymptotic estimates for certain combinatorial quantities. In this paper, we apply these tools to determine the Gilbert-Varshamov (GV) bound for the sticky insertion and the constrained-synthesis channel. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.04439v1-abstract-full').style.display = 'none'; document.getElementById('2305.04439v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 7 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2305.03442">arXiv:2305.03442</a> <span> [<a href="https://arxiv.org/pdf/2305.03442">pdf</a>, <a href="https://arxiv.org/format/2305.03442">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Repair of Reed-Solomon Codes in the Presence of Erroneous Nodes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Kruglik%2C+S">Stanislav Kruglik</a>, <a href="/search/?searchtype=author&query=Luo%2C+G">Gaojun Luo</a>, <a href="/search/?searchtype=author&query=Kim%2C+W">Wilton Kim</a>, <a href="/search/?searchtype=author&query=Singhvi%2C+S">Shubhransh Singhvi</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Ling%2C+S">San Ling</a>, <a href="/search/?searchtype=author&query=Wang%2C+H">Huaxiong Wang</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2305.03442v1-abstract-short" style="display: inline;"> We consider the repair scheme of Guruswami-Wootters for the Reed-Solomon code and ask: can we correctly repair a failed node in the presence of erroneous nodes? Equivalently, we consider the collection of downloaded traces as a code and investigate its code-distance properties. We propose three lower bounds on its minimum distance and study methods to efficiently correct errors close to these boun… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.03442v1-abstract-full').style.display = 'inline'; document.getElementById('2305.03442v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2305.03442v1-abstract-full" style="display: none;"> We consider the repair scheme of Guruswami-Wootters for the Reed-Solomon code and ask: can we correctly repair a failed node in the presence of erroneous nodes? Equivalently, we consider the collection of downloaded traces as a code and investigate its code-distance properties. We propose three lower bounds on its minimum distance and study methods to efficiently correct errors close to these bounds. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.03442v1-abstract-full').style.display = 'none'; document.getElementById('2305.03442v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 5 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Accepted to IEEE International Symposium on Information Theory 2023</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2302.13714">arXiv:2302.13714</a> <span> [<a href="https://arxiv.org/pdf/2302.13714">pdf</a>, <a href="https://arxiv.org/format/2302.13714">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> </div> </div> <p class="title is-5 mathjax"> On the Design of Codes for DNA Computing: Secondary Structure Avoidance Codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Nguyen%2C+T+T">Tuan Thanh Nguyen</a>, <a href="/search/?searchtype=author&query=Cai%2C+K">Kui Cai</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Dao%2C+D+T">Duc Tu Dao</a>, <a href="/search/?searchtype=author&query=Immink%2C+K+A+S">Kees A. Schouhamer Immink</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2302.13714v1-abstract-short" style="display: inline;"> In this work, we investigate a challenging problem, which has been considered to be an important criterion in designing codewords for DNA computing purposes, namely secondary structure avoidance in single-stranded DNA molecules. In short, secondary structure refers to the tendency of a single-stranded DNA sequence to fold back upon itself, thus becoming inactive in the computation process. While s… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.13714v1-abstract-full').style.display = 'inline'; document.getElementById('2302.13714v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2302.13714v1-abstract-full" style="display: none;"> In this work, we investigate a challenging problem, which has been considered to be an important criterion in designing codewords for DNA computing purposes, namely secondary structure avoidance in single-stranded DNA molecules. In short, secondary structure refers to the tendency of a single-stranded DNA sequence to fold back upon itself, thus becoming inactive in the computation process. While some design criteria that reduces the possibility of secondary structure formation has been proposed by Milenkovic and Kashyap (2006), the main contribution of this work is to provide an explicit construction of DNA codes that completely avoid secondary structure of arbitrary stem length. Formally, given codeword length n and arbitrary integer m>=2, we provide efficient methods to construct DNA codes of length n that avoid secondary structure of any stem length more than or equal to m. Particularly, when m = 3, our constructions yield a family of DNA codes of rate 1.3031 bits/nt, while the highest rate found in the prior art was 1.1609 bits/nt. In addition, for m>=3log n + 4, we provide an efficient encoder that incurs only one redundant symbol. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.13714v1-abstract-full').style.display = 'none'; document.getElementById('2302.13714v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 27 February, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2302.02230">arXiv:2302.02230</a> <span> [<a href="https://arxiv.org/pdf/2302.02230">pdf</a>, <a href="https://arxiv.org/ps/2302.02230">ps</a>, <a href="https://arxiv.org/format/2302.02230">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Cryptography and Security">cs.CR</span> </div> </div> <p class="title is-5 mathjax"> $k$-server Byzantine-Resistant PIR Scheme with Optimal Download Rate and Optimal File Size </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Kruglik%2C+S">Stanislav Kruglik</a>, <a href="/search/?searchtype=author&query=Dau%2C+S+H">Son Hoang Dau</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Wang%2C+H">Huaxiong Wang</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2302.02230v2-abstract-short" style="display: inline;"> We consider the problem of designing a Private Information Retrieval (PIR) scheme on $m$ files replicated on $k$ servers that can collude or, even worse, can return incorrect answers. Our goal is to correctly retrieve a specific message while keeping its identity private from the database servers. We consider the asymptotic information-theoretic capacity of this problem defined as the maximum rati… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.02230v2-abstract-full').style.display = 'inline'; document.getElementById('2302.02230v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2302.02230v2-abstract-full" style="display: none;"> We consider the problem of designing a Private Information Retrieval (PIR) scheme on $m$ files replicated on $k$ servers that can collude or, even worse, can return incorrect answers. Our goal is to correctly retrieve a specific message while keeping its identity private from the database servers. We consider the asymptotic information-theoretic capacity of this problem defined as the maximum ratio of the number of correctly retrieved symbols to the downloaded one for a large enough number of stored files. We propose an achievable scheme with a small file size and prove that such a file size is minimal for the fixed number of retrieved symbols, solving the problem pointed out by Banawan and Ulukus. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.02230v2-abstract-full').style.display = 'none'; document.getElementById('2302.02230v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 5 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 4 February, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Accepted to IEEE International Symposium on Information Theory 2023</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2302.01733">arXiv:2302.01733</a> <span> [<a href="https://arxiv.org/pdf/2302.01733">pdf</a>, <a href="https://arxiv.org/format/2302.01733">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Cryptography and Security">cs.CR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Databases">cs.DB</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Information Retrieval">cs.IR</span> </div> </div> <p class="title is-5 mathjax"> Committed Private Information Retrieval </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Cao%2C+Q">Quang Cao</a>, <a href="/search/?searchtype=author&query=Tran%2C+H+Y">Hong Yen Tran</a>, <a href="/search/?searchtype=author&query=Dau%2C+S+H">Son Hoang Dau</a>, <a href="/search/?searchtype=author&query=Yi%2C+X">Xun Yi</a>, <a href="/search/?searchtype=author&query=Viterbo%2C+E">Emanuele Viterbo</a>, <a href="/search/?searchtype=author&query=Feng%2C+C">Chen Feng</a>, <a href="/search/?searchtype=author&query=Huang%2C+Y">Yu-Chih Huang</a>, <a href="/search/?searchtype=author&query=Zhu%2C+J">Jingge Zhu</a>, <a href="/search/?searchtype=author&query=Kruglik%2C+S">Stanislav Kruglik</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2302.01733v3-abstract-short" style="display: inline;"> A private information retrieval (PIR) scheme allows a client to retrieve a data item $x_i$ among $n$ items $x_1,x_2,\ldots,x_n$ from $k$ servers, without revealing what $i$ is even when $t < k$ servers collude and try to learn $i$. Such a PIR scheme is said to be $t$-private. A PIR scheme is $v$-verifiable if the client can verify the correctness of the retrieved $x_i$ even when $v \leq k$ servers… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.01733v3-abstract-full').style.display = 'inline'; document.getElementById('2302.01733v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2302.01733v3-abstract-full" style="display: none;"> A private information retrieval (PIR) scheme allows a client to retrieve a data item $x_i$ among $n$ items $x_1,x_2,\ldots,x_n$ from $k$ servers, without revealing what $i$ is even when $t < k$ servers collude and try to learn $i$. Such a PIR scheme is said to be $t$-private. A PIR scheme is $v$-verifiable if the client can verify the correctness of the retrieved $x_i$ even when $v \leq k$ servers collude and try to fool the client by sending manipulated data. Most of the previous works in the literature on PIR assumed that $v < k$, leaving the case of all-colluding servers open. We propose a generic construction that combines a linear map commitment (LMC) and an arbitrary linear PIR scheme to produce a $k$-verifiable PIR scheme, termed a committed PIR scheme. Such a scheme guarantees that even in the worst scenario, when all servers are under the control of an attacker, although the privacy is unavoidably lost, the client won't be fooled into accepting an incorrect $x_i$. We demonstrate the practicality of our proposal by implementing the committed PIR schemes based on the Lai-Malavolta LMC and three well-known PIR schemes using the GMP library and blst, the current fastest C library for elliptic curve pairings. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.01733v3-abstract-full').style.display = 'none'; document.getElementById('2302.01733v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 25 September, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 3 February, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Accepted at ESORICS 2023</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2301.11730">arXiv:2301.11730</a> <span> [<a href="https://arxiv.org/pdf/2301.11730">pdf</a>, <a href="https://arxiv.org/ps/2301.11730">ps</a>, <a href="https://arxiv.org/format/2301.11730">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Cryptography and Security">cs.CR</span> </div> </div> <p class="title is-5 mathjax"> Two-Server Private Information Retrieval with Optimized Download Rate and Result Verification </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Kruglik%2C+S">Stanislav Kruglik</a>, <a href="/search/?searchtype=author&query=Dau%2C+S+H">Son Hoang Dau</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Wang%2C+H">Huaxiong Wang</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2301.11730v3-abstract-short" style="display: inline;"> Private Information Retrieval (PIR) schemes allow a client to retrieve any file of interest, while hiding the file identity from the database servers. In contrast to most existing PIR schemes that assume honest-but-curious servers, we study the case of dishonest servers. The latter provide incorrect answers and try to persuade the client to output the wrong result. We introduce several PIR schemes… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2301.11730v3-abstract-full').style.display = 'inline'; document.getElementById('2301.11730v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2301.11730v3-abstract-full" style="display: none;"> Private Information Retrieval (PIR) schemes allow a client to retrieve any file of interest, while hiding the file identity from the database servers. In contrast to most existing PIR schemes that assume honest-but-curious servers, we study the case of dishonest servers. The latter provide incorrect answers and try to persuade the client to output the wrong result. We introduce several PIR schemes with information-theoretic privacy and result verification for the case of two servers. Security guarantees can be information-theoretical or computational, and the verification keys can be public or private. In this work, our main performance metric is the download rate. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2301.11730v3-abstract-full').style.display = 'none'; document.getElementById('2301.11730v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 8 June, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 27 January, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Accepted to IEEE International Symposium on Information Theory 2023</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2212.09952">arXiv:2212.09952</a> <span> [<a href="https://arxiv.org/pdf/2212.09952">pdf</a>, <a href="https://arxiv.org/format/2212.09952">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Efficient Algorithms for the Bee-Identification Problem </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Vardy%2C+A">Alexander Vardy</a>, <a href="/search/?searchtype=author&query=Yao%2C+H">Hanwen Yao</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2212.09952v1-abstract-short" style="display: inline;"> The bee-identification problem, formally defined by Tandon, Tan and Varshney (2019), requires the receiver to identify "bees" using a set of unordered noisy measurements. In this previous work, Tandon, Tan, and Varshney studied error exponents and showed that decoding the measurements jointly results in a significantly smaller error exponent. In this work, we study algorithms related to this joi… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2212.09952v1-abstract-full').style.display = 'inline'; document.getElementById('2212.09952v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2212.09952v1-abstract-full" style="display: none;"> The bee-identification problem, formally defined by Tandon, Tan and Varshney (2019), requires the receiver to identify "bees" using a set of unordered noisy measurements. In this previous work, Tandon, Tan, and Varshney studied error exponents and showed that decoding the measurements jointly results in a significantly smaller error exponent. In this work, we study algorithms related to this joint decoder. First, we demonstrate how to perform joint decoding efficiently. By reducing to the problem of finding perfect matching and minimum-cost matchings, we obtain joint decoders that run in time quadratic and cubic in the number of "bees" for the binary erasure (BEC) and binary symmetric channels (BSC), respectively. Next, by studying the matching algorithms in the context of channel coding, we further reduce the running times by using classical tools like peeling decoders and list-decoders. In particular, we show that our identifier algorithms when used with Reed-Muller codes terminate in almost linear and quadratic time for BEC and BSC, respectively. Finally, for explicit codebooks, we study when these joint decoders fail to identify the "bees" correctly. Specifically, we provide practical methods of estimating the probability of erroneous identification for given codebooks. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2212.09952v1-abstract-full').style.display = 'none'; document.getElementById('2212.09952v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 19 December, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2022. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 94B99 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2212.07091">arXiv:2212.07091</a> <span> [<a href="https://arxiv.org/pdf/2212.07091">pdf</a>, <a href="https://arxiv.org/format/2212.07091">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Verifiable Coded Computation of Multiple Functions </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Kim%2C+W">Wilton Kim</a>, <a href="/search/?searchtype=author&query=Kruglik%2C+S">Stanislav Kruglik</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2212.07091v2-abstract-short" style="display: inline;"> We consider the problem of evaluating distinct multivariate polynomials over several massive datasets in a distributed computing system with a single master node and multiple worker nodes. We focus on the general case when each multivariate polynomial is evaluated over its corresponding dataset and propose a generalization of the Lagrange Coded Computing framework (Yu et al. 2019) to perform all c… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2212.07091v2-abstract-full').style.display = 'inline'; document.getElementById('2212.07091v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2212.07091v2-abstract-full" style="display: none;"> We consider the problem of evaluating distinct multivariate polynomials over several massive datasets in a distributed computing system with a single master node and multiple worker nodes. We focus on the general case when each multivariate polynomial is evaluated over its corresponding dataset and propose a generalization of the Lagrange Coded Computing framework (Yu et al. 2019) to perform all computations simultaneously while providing robustness against stragglers who do not respond in time, adversarial workers who respond with wrong computation and information-theoretic security of dataset against colluding workers. Our scheme introduces a small computation overhead which results in a reduction in download cost and also offers comparable resistance to stragglers over existing solutions. On top of it, we also propose two verification schemes to detect the presence of adversaries, which leads to incorrect results, without involving additional nodes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2212.07091v2-abstract-full').style.display = 'none'; document.getElementById('2212.07091v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 22 August, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 14 December, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2022. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">13 pages, 1 figure, 2 tables</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2209.03251">arXiv:2209.03251</a> <span> [<a href="https://arxiv.org/pdf/2209.03251">pdf</a>, <a href="https://arxiv.org/format/2209.03251">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Explicit Low-Bandwidth Evaluation Schemes for Weighted Sums of Reed-Solomon-Coded Symbols </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Kim%2C+W">Wilton Kim</a>, <a href="/search/?searchtype=author&query=Kruglik%2C+S">Stanislav Kruglik</a>, <a href="/search/?searchtype=author&query=Ling%2C+S">San Ling</a>, <a href="/search/?searchtype=author&query=Wang%2C+H">Huaxiong Wang</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2209.03251v3-abstract-short" style="display: inline;"> Motivated by applications in distributed storage, distributed computing, and homomorphic secret sharing, we study communication-efficient schemes for computing linear combinations of coded symbols. Specifically, we design low-bandwidth schemes that evaluate the weighted sum of $\ell$ coded symbols in a codeword $\pmb{c}\in\mathbb{F}^n$, when we are given access to $d$ of the remaining components i… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2209.03251v3-abstract-full').style.display = 'inline'; document.getElementById('2209.03251v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2209.03251v3-abstract-full" style="display: none;"> Motivated by applications in distributed storage, distributed computing, and homomorphic secret sharing, we study communication-efficient schemes for computing linear combinations of coded symbols. Specifically, we design low-bandwidth schemes that evaluate the weighted sum of $\ell$ coded symbols in a codeword $\pmb{c}\in\mathbb{F}^n$, when we are given access to $d$ of the remaining components in $\pmb{c}$. Formally, suppose that $\mathbb{F}$ is a field extension of $\mathbb{B}$ of degree $t$. Let $\pmb{c}$ be a codeword in a Reed-Solomon code of dimension $k$ and our task is to compute the weighted sum of $\ell$ coded symbols. In this paper, for some $s<t$, we provide an explicit scheme that performs this task by downloading $d(t-s)$ sub-symbols in $\mathbb{B}$ from $d$ available nodes, whenever $d\geq \ell|\mathbb{B}|^s-\ell+k$. In many cases, our scheme outperforms previous schemes in the literature. Furthermore, we provide a characterization of evaluation schemes for general linear codes. Then in the special case of Reed-Solomon codes, we use this characterization to derive a lower bound for the evaluation bandwidth. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2209.03251v3-abstract-full').style.display = 'none'; document.getElementById('2209.03251v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 7 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 7 September, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2022. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Accepted to 2023 IEEE International Symposium on Information Theory</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2208.09138">arXiv:2208.09138</a> <span> [<a href="https://arxiv.org/pdf/2208.09138">pdf</a>, <a href="https://arxiv.org/ps/2208.09138">ps</a>, <a href="https://arxiv.org/format/2208.09138">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Two dimensional RC/Subarray Constrained Codes: Bounded Weight and Almost Balanced Weight </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Nguyen%2C+T+T">Tuan Thanh Nguyen</a>, <a href="/search/?searchtype=author&query=Cai%2C+K">Kui Cai</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Immink%2C+K+A+S">Kees A. Schouhamer Immink</a>, <a href="/search/?searchtype=author&query=Chee%2C+Y+M">Yeow Meng Chee</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2208.09138v1-abstract-short" style="display: inline;"> In this work, we study two types of constraints on two-dimensional binary arrays. In particular, given $p,蔚>0$, we study (i) The $p$-bounded constraint: a binary vector of size $m$ is said to be $p$-bounded if its weight is at most $pm$, and (ii) The $蔚$-balanced constraint: a binary vector of size $m$ is said to be $蔚$-balanced if its weight is within $[(0.5-蔚)*m,(0.5+蔚)*m]$. Such constraints are… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2208.09138v1-abstract-full').style.display = 'inline'; document.getElementById('2208.09138v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2208.09138v1-abstract-full" style="display: none;"> In this work, we study two types of constraints on two-dimensional binary arrays. In particular, given $p,蔚>0$, we study (i) The $p$-bounded constraint: a binary vector of size $m$ is said to be $p$-bounded if its weight is at most $pm$, and (ii) The $蔚$-balanced constraint: a binary vector of size $m$ is said to be $蔚$-balanced if its weight is within $[(0.5-蔚)*m,(0.5+蔚)*m]$. Such constraints are crucial in several data storage systems, those regard the information data as two-dimensional (2D) instead of one-dimensional (1D), such as the crossbar resistive memory arrays and the holographic data storage. In this work, efficient encoding/decoding algorithms are presented for binary arrays so that the weight constraint (either $p$-bounded constraint or $蔚$-balanced constraint) is enforced over every row and every column, regarded as 2D row-column (RC) constrained codes; or over every subarray, regarded as 2D subarray constrained codes. While low-complexity designs have been proposed in the literature, mostly focusing on 2D RC constrained codes where $p = 1/2$ and $蔚= 0$, this work provides efficient coding methods that work for both 2D RC constrained codes and 2D subarray constrained codes, and more importantly, the methods are applicable for arbitrary values of $p$ and $蔚$. Furthermore, for certain values of $p$ and $蔚$, we show that, for sufficiently large array size, there exists linear-time encoding/decoding algorithm that incurs at most one redundant bit. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2208.09138v1-abstract-full').style.display = 'none'; document.getElementById('2208.09138v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 18 August, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 2022. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2204.13831">arXiv:2204.13831</a> <span> [<a href="https://arxiv.org/pdf/2204.13831">pdf</a>, <a href="https://arxiv.org/format/2204.13831">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> </div> </div> <p class="title is-5 mathjax"> Average Redundancy of Variable-Length Balancing Schemes 脿 la Knuth </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Dao%2C+D+T">Duc Tu Dao</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Nguyen%2C+T+T">Tuan Thanh Nguyen</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2204.13831v2-abstract-short" style="display: inline;"> We study and propose schemes that map messages onto constant-weight codewords using variable-length prefixes. We provide polynomial-time computable formulas that estimate the average number of redundant bits incurred by our schemes. In addition to the exact formulas, we also perform an asymptotic analysis and demonstrate that our scheme uses $\frac12 \log n+O(1)$ redundant bits to encode messages… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2204.13831v2-abstract-full').style.display = 'inline'; document.getElementById('2204.13831v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2204.13831v2-abstract-full" style="display: none;"> We study and propose schemes that map messages onto constant-weight codewords using variable-length prefixes. We provide polynomial-time computable formulas that estimate the average number of redundant bits incurred by our schemes. In addition to the exact formulas, we also perform an asymptotic analysis and demonstrate that our scheme uses $\frac12 \log n+O(1)$ redundant bits to encode messages into length-$n$ words with weight $(n/2)+{\sf q}$ for constant ${\sf q}$. We also propose schemes that map messages into balanced codebooks with error-correcting capabilities. For such schemes, we provide methods to enumerate the average number of redundant bits. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2204.13831v2-abstract-full').style.display = 'none'; document.getElementById('2204.13831v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 3 July, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 28 April, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2022. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Extended version with new results</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2111.04255">arXiv:2111.04255</a> <span> [<a href="https://arxiv.org/pdf/2111.04255">pdf</a>, <a href="https://arxiv.org/ps/2111.04255">ps</a>, <a href="https://arxiv.org/format/2111.04255">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> </div> </div> <p class="title is-5 mathjax"> Sequence Reconstruction Problem for Deletion Channels: A Complete Asymptotic Solution </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Pham%2C+V+L+P">Van Long Phuoc Pham</a>, <a href="/search/?searchtype=author&query=Goyal%2C+K">Keshav Goyal</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2111.04255v1-abstract-short" style="display: inline;"> Transmit a codeword $x$, that belongs to an $(\ell-1)$-deletion-correcting code of length $n$, over a $t$-deletion channel for some $1\le \ell\le t<n$. Levenshtein, in 2001, proposed the problem of determining $N(n,\ell,t)+1$, the minimum number of distinct channel outputs required to uniquely reconstruct $x$. Prior to this work, $N(n,\ell,t)$ is known only when $\ell\in\{1,2\}$. Here, we provide… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2111.04255v1-abstract-full').style.display = 'inline'; document.getElementById('2111.04255v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2111.04255v1-abstract-full" style="display: none;"> Transmit a codeword $x$, that belongs to an $(\ell-1)$-deletion-correcting code of length $n$, over a $t$-deletion channel for some $1\le \ell\le t<n$. Levenshtein, in 2001, proposed the problem of determining $N(n,\ell,t)+1$, the minimum number of distinct channel outputs required to uniquely reconstruct $x$. Prior to this work, $N(n,\ell,t)$ is known only when $\ell\in\{1,2\}$. Here, we provide an asymptotically exact solution for all values of $\ell$ and $t$. Specifically, we show that $N(n,\ell,t)=\binom{2\ell}{\ell}/(t-\ell)! n^{t-\ell} - O(n^{t-\ell-1})$ and in the special instance where $\ell=t$, we show that $N(n,\ell,\ell)=\binom{2\ell}{\ell}$. We also provide a conjecture on the exact value of $N(n,\ell,t)$ for all values of $n$, $\ell$, and $t$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2111.04255v1-abstract-full').style.display = 'none'; document.getElementById('2111.04255v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 7 November, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2021. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 94B99 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2107.07377">arXiv:2107.07377</a> <span> [<a href="https://arxiv.org/pdf/2107.07377">pdf</a>, <a href="https://arxiv.org/format/2107.07377">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> </div> </div> <p class="title is-5 mathjax"> Computing Permanents on a Trellis </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Vardy%2C+A">Alexander Vardy</a>, <a href="/search/?searchtype=author&query=Yao%2C+H">Hanwen Yao</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2107.07377v1-abstract-short" style="display: inline;"> The problem of computing the permanent of a matrix has attracted interest since the work of Ryser(1963) and Valiant(1979). On the other hand, trellises were extensively studied in coding theory since the 1960s. In this work, we establish a connection between the two domains. We introduce the canonical trellis $T_n$ that represents all permutations, and show that the permanent of a $n$ by $n$ matri… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2107.07377v1-abstract-full').style.display = 'inline'; document.getElementById('2107.07377v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2107.07377v1-abstract-full" style="display: none;"> The problem of computing the permanent of a matrix has attracted interest since the work of Ryser(1963) and Valiant(1979). On the other hand, trellises were extensively studied in coding theory since the 1960s. In this work, we establish a connection between the two domains. We introduce the canonical trellis $T_n$ that represents all permutations, and show that the permanent of a $n$ by $n$ matrix $A$ can be computed as a flow on this trellis. Under certain normalization, the trellis-based method invokes slightly less operations than best known exact methods. Moreover, if $A$ has structure, then $T_n$ becomes amenable to vertex merging, thereby significantly reducing its complexity. - Repeated rows: Suppose $A$ has only $t<n$ distinct rows. The best known method to compute $per(A)$, due to Clifford and Clifford (2020), has complexity $O(n^{t+1})$. Merging vertices in $T_n$, we obtain a reduced trellis that has complexity $O(n^t)$. - Order statistics: Using trellises, we compute the joint distribution of $t$ order statistics of $n$ independent, but not identically distributed, random variables in time $O(n^{t+1})$. Previously, polynomial-time methods were known only when the variables are drawn from two non-identical distributions. - Sparse matrices: Suppose each entry in $A$ is nonzero with probability $d/n$ with $d$ is constant. We show that $T_n$ can be pruned to exponentially fewer vertices, resulting in complexity $O(蠁^n)$ with $蠁<2$. - TSP: Intersecting $T_n$ with another trellis that represents walks, we obtain a trellis that represents circular permutations. Using the latter trellis to solve the traveling salesperson problem recovers the well-known Held-Karp algorithm. Notably, in all cases, the reduced trellis are obtained using known techniques in trellis theory. We expect other trellis-theoretic results to apply to other structured matrices. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2107.07377v1-abstract-full').style.display = 'none'; document.getElementById('2107.07377v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 15 July, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2021. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2007.15253">arXiv:2007.15253</a> <span> [<a href="https://arxiv.org/pdf/2007.15253">pdf</a>, <a href="https://arxiv.org/format/2007.15253">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Repairing Reed-Solomon Codes via Subspace Polynomials </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Dau%2C+H">Hoang Dau</a>, <a href="/search/?searchtype=author&query=Xinh%2C+D+T">Dinh Thi Xinh</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Luong%2C+T+T">Tran Thi Luong</a>, <a href="/search/?searchtype=author&query=Milenkovic%2C+O">Olgica Milenkovic</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2007.15253v1-abstract-short" style="display: inline;"> We propose new repair schemes for Reed-Solomon codes that use subspace polynomials and hence generalize previous works in the literature that employ trace polynomials. The Reed-Solomon codes are over $\mathbb{F}_{q^\ell}$ and have redundancy $r = n-k \geq q^m$, $1\leq m\leq \ell$, where $n$ and $k$ are the code length and dimension, respectively. In particular, for one erasure, we show that our sc… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2007.15253v1-abstract-full').style.display = 'inline'; document.getElementById('2007.15253v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2007.15253v1-abstract-full" style="display: none;"> We propose new repair schemes for Reed-Solomon codes that use subspace polynomials and hence generalize previous works in the literature that employ trace polynomials. The Reed-Solomon codes are over $\mathbb{F}_{q^\ell}$ and have redundancy $r = n-k \geq q^m$, $1\leq m\leq \ell$, where $n$ and $k$ are the code length and dimension, respectively. In particular, for one erasure, we show that our schemes can achieve optimal repair bandwidths whenever $n=q^\ell$ and $r = q^m,$ for all $1 \leq m \leq \ell$. For two erasures, our schemes use the same bandwidth per erasure as the single erasure schemes, for $\ell/m$ is a power of $q$, and for $\ell=q^a$, $m=q^b-1>1$ ($a \geq b \geq 1$), and for $m\geq \ell/2$ when $\ell$ is even and $q$ is a power of two. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2007.15253v1-abstract-full').style.display = 'none'; document.getElementById('2007.15253v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 30 July, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2020. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2007.11626">arXiv:2007.11626</a> <span> [<a href="https://arxiv.org/pdf/2007.11626">pdf</a>, <a href="https://arxiv.org/ps/2007.11626">ps</a>, <a href="https://arxiv.org/format/2007.11626">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> </div> </div> <p class="title is-5 mathjax"> Explicit Baranyai Partitions for Quadruples, Part I: Quadrupling Constructions </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Chee%2C+Y+M">Yeow Meng Chee</a>, <a href="/search/?searchtype=author&query=Etzion%2C+T">Tuvi Etzion</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Vardy%2C+A">Alexander Vardy</a>, <a href="/search/?searchtype=author&query=Wang%2C+C">Chengmin Wang</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2007.11626v1-abstract-short" style="display: inline;"> It is well known that, whenever $k$ divides $n$, the complete $k$-uniform hypergraph on $n$ vertices can be partitioned into disjoint perfect matchings. Equivalently, the set of $k$-subsets of an $n$-set can be partitioned into parallel classes so that each parallel class is a partition of the $n$-set. This result is known as Baranyai's theorem, which guarantees the existence of \emph{Baranyai par… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2007.11626v1-abstract-full').style.display = 'inline'; document.getElementById('2007.11626v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2007.11626v1-abstract-full" style="display: none;"> It is well known that, whenever $k$ divides $n$, the complete $k$-uniform hypergraph on $n$ vertices can be partitioned into disjoint perfect matchings. Equivalently, the set of $k$-subsets of an $n$-set can be partitioned into parallel classes so that each parallel class is a partition of the $n$-set. This result is known as Baranyai's theorem, which guarantees the existence of \emph{Baranyai partitions}. Unfortunately, the proof of Baranyai's theorem uses network flow arguments, making this result non-explicit. In particular, there is no known method to produce Baranyai partitions in time and space that scale linearly with the number of hyperedges in the hypergraph. It is desirable for certain applications to have an explicit construction that generates Baranyai partitions in linear time. Such an efficient construction is known for $k=2$ and $k=3$. In this paper, we present an explicit recursive quadrupling construction for $k=4$ and $n=4t$, where $t \equiv 0,3,4,6,8,9 ~(\text{mod}~12)$. In a follow-up paper (Part II), the other values of~$t$, namely $t \equiv 1,2,5,7,10,11 ~(\text{mod}~12)$, will be considered. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2007.11626v1-abstract-full').style.display = 'none'; document.getElementById('2007.11626v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 22 July, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2020. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2005.03102">arXiv:2005.03102</a> <span> [<a href="https://arxiv.org/pdf/2005.03102">pdf</a>, <a href="https://arxiv.org/ps/2005.03102">ps</a>, <a href="https://arxiv.org/format/2005.03102">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Constrained de Bruijn Codes: Properties, Enumeration, Constructions, and Applications </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Chee%2C+Y+M">Yeow Meng Chee</a>, <a href="/search/?searchtype=author&query=Etzion%2C+T">Tuvi Etzion</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Vardy%2C+A">Alexander Vardy</a>, <a href="/search/?searchtype=author&query=Vu%2C+V+K">Van Khu Vu</a>, <a href="/search/?searchtype=author&query=yaakobi%2C+E">Eitan yaakobi</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2005.03102v1-abstract-short" style="display: inline;"> The de Bruijn graph, its sequences, and their various generalizations, have found many applications in information theory, including many new ones in the last decade. In this paper, motivated by a coding problem for emerging memory technologies, a set of sequences which generalize sequences in the de Bruijn graph are defined. These sequences can be also defined and viewed as constrained sequences.… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2005.03102v1-abstract-full').style.display = 'inline'; document.getElementById('2005.03102v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2005.03102v1-abstract-full" style="display: none;"> The de Bruijn graph, its sequences, and their various generalizations, have found many applications in information theory, including many new ones in the last decade. In this paper, motivated by a coding problem for emerging memory technologies, a set of sequences which generalize sequences in the de Bruijn graph are defined. These sequences can be also defined and viewed as constrained sequences. Hence, they will be called constrained de Bruijn sequences and a set of such sequences will be called a constrained de Bruijn code. Several properties and alternative definitions for such codes are examined and they are analyzed as generalized sequences in the de Bruijn graph (and its generalization) and as constrained sequences. Various enumeration techniques are used to compute the total number of sequences for any given set of parameters. A construction method of such codes from the theory of shift-register sequences is proposed. Finally, we show how these constrained de Bruijn sequences and codes can be applied in constructions of codes for correcting synchronization errors in the $\ell$-symbol read channel and in the racetrack memory channel. For this purpose, these codes are superior in their size on previously known codes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2005.03102v1-abstract-full').style.display = 'none'; document.getElementById('2005.03102v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 6 May, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2020. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2004.06032">arXiv:2004.06032</a> <span> [<a href="https://arxiv.org/pdf/2004.06032">pdf</a>, <a href="https://arxiv.org/ps/2004.06032">ps</a>, <a href="https://arxiv.org/format/2004.06032">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Optimal Reconstruction Codes for Deletion Channels </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Chrisnata%2C+J">Johan Chrisnata</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Yaakobi%2C+E">Eitan Yaakobi</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2004.06032v1-abstract-short" style="display: inline;"> The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication scenario where the sender transmits a codeword from some codebook and the receiver obtains multiple noisy reads of the codeword. Motivated by modern storage devices, we introduced a variant of the problem where the number of noisy reads $N$ is fixed (Kiah et al. 2020). Of significance, for the single-… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2004.06032v1-abstract-full').style.display = 'inline'; document.getElementById('2004.06032v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2004.06032v1-abstract-full" style="display: none;"> The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication scenario where the sender transmits a codeword from some codebook and the receiver obtains multiple noisy reads of the codeword. Motivated by modern storage devices, we introduced a variant of the problem where the number of noisy reads $N$ is fixed (Kiah et al. 2020). Of significance, for the single-deletion channel, using $\log_2\log_2 n +O(1)$ redundant bits, we designed a reconstruction code of length $n$ that reconstructs codewords from two distinct noisy reads. In this work, we show that $\log_2\log_2 n -O(1)$ redundant bits are necessary for such reconstruction codes, thereby, demonstrating the optimality of our previous construction. Furthermore, we show that these reconstruction codes can be used in $t$-deletion channels (with $t\ge 2$) to uniquely reconstruct codewords from $n^{t-1}+O\left(n^{t-2}\right)$ distinct noisy reads. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2004.06032v1-abstract-full').style.display = 'none'; document.getElementById('2004.06032v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 13 April, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2020. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2001.02839">arXiv:2001.02839</a> <span> [<a href="https://arxiv.org/pdf/2001.02839">pdf</a>, <a href="https://arxiv.org/format/2001.02839">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Capacity-Approaching Constrained Codes with Error Correction for DNA-Based Data Storage </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Nguyen%2C+T+T">Tuan Thanh Nguyen</a>, <a href="/search/?searchtype=author&query=Cai%2C+K">Kui Cai</a>, <a href="/search/?searchtype=author&query=Immink%2C+K+A+S">Kees A. Schouhamer Immink</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2001.02839v1-abstract-short" style="display: inline;"> We propose coding techniques that limit the length of homopolymers runs, ensure the GC-content constraint, and are capable of correcting a single edit error in strands of nucleotides in DNA-based data storage systems. In particular, for given $\ell, 蔚 > 0$, we propose simple and efficient encoders/decoders that transform binary sequences into DNA base sequences (codewords), namely sequences of the… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2001.02839v1-abstract-full').style.display = 'inline'; document.getElementById('2001.02839v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2001.02839v1-abstract-full" style="display: none;"> We propose coding techniques that limit the length of homopolymers runs, ensure the GC-content constraint, and are capable of correcting a single edit error in strands of nucleotides in DNA-based data storage systems. In particular, for given $\ell, 蔚 > 0$, we propose simple and efficient encoders/decoders that transform binary sequences into DNA base sequences (codewords), namely sequences of the symbols A, T, C and G, that satisfy the following properties: (i) Runlength constraint: the maximum homopolymer run in each codeword is at most $\ell$, (ii) GC-content constraint: the GC-content of each codeword is within $[0.5-蔚, 0.5+蔚]$, (iii) Error-correction: each codeword is capable of correcting a single deletion, or single insertion, or single substitution error. For practical values of $\ell$ and $蔚$, we show that our encoders achieve much higher rates than existing results in the literature and approach the capacity. Our methods have low encoding/decoding complexity and limited error propagation. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2001.02839v1-abstract-full').style.display = 'none'; document.getElementById('2001.02839v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 8 January, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2020. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2001.01376">arXiv:2001.01376</a> <span> [<a href="https://arxiv.org/pdf/2001.01376">pdf</a>, <a href="https://arxiv.org/format/2001.01376">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Coding for Sequence Reconstruction for Single Edits </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Cai%2C+K">Kui Cai</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Nguyen%2C+T+T">Tuan Thanh Nguyen</a>, <a href="/search/?searchtype=author&query=Yaakobi%2C+E">Eitan Yaakobi</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2001.01376v2-abstract-short" style="display: inline;"> The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication scenario where the sender transmits a codeword from some codebook and the receiver obtains multiple noisy reads of the codeword. The common setup assumes the codebook to be the entire space and the problem is to determine the minimum number of distinct reads that is required to reconstruct the transmi… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2001.01376v2-abstract-full').style.display = 'inline'; document.getElementById('2001.01376v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2001.01376v2-abstract-full" style="display: none;"> The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication scenario where the sender transmits a codeword from some codebook and the receiver obtains multiple noisy reads of the codeword. The common setup assumes the codebook to be the entire space and the problem is to determine the minimum number of distinct reads that is required to reconstruct the transmitted codeword. Motivated by modern storage devices, we study a variant of the problem where the number of noisy reads $N$ is fixed. Specifically, we design reconstruction codes that reconstruct a codeword from $N$ distinct noisy reads. We focus on channels that introduce single edit error (i.e. a single substitution, insertion, or deletion) and their variants, and design reconstruction codes for all values of $N$. In particular, for the case of a single edit, we show that as the number of noisy reads increases, the number of redundant bits required can be gracefully reduced from $\log n+O(1)$ to $\log \log n+O(1)$, and then to $O(1)$, where $n$ denotes the length of a codeword. We also show that the redundancy of certain reconstruction codes is within one bit of optimality. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2001.01376v2-abstract-full').style.display = 'none'; document.getElementById('2001.01376v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 14 June, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 5 January, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2020. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1912.13301">arXiv:1912.13301</a> <span> [<a href="https://arxiv.org/pdf/1912.13301">pdf</a>, <a href="https://arxiv.org/format/1912.13301">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Robust Positioning Patterns with Low Redundancy </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Chee%2C+Y+M">Yeow Meng Chee</a>, <a href="/search/?searchtype=author&query=Dao%2C+D+T">Duc Tu Dao</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Ling%2C+S">San Ling</a>, <a href="/search/?searchtype=author&query=Wei%2C+H">Hengjia Wei</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1912.13301v1-abstract-short" style="display: inline;"> A robust positioning pattern is a large array that allows a mobile device to locate its position by reading a possibly corrupted small window around it. In this paper, we provide constructions of binary positioning patterns, equipped with efficient locating algorithms, that are robust to a constant number of errors and have redundancy within a constant factor of optimality. Furthermore, we modify… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1912.13301v1-abstract-full').style.display = 'inline'; document.getElementById('1912.13301v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1912.13301v1-abstract-full" style="display: none;"> A robust positioning pattern is a large array that allows a mobile device to locate its position by reading a possibly corrupted small window around it. In this paper, we provide constructions of binary positioning patterns, equipped with efficient locating algorithms, that are robust to a constant number of errors and have redundancy within a constant factor of optimality. Furthermore, we modify our constructions to correct rank errors and obtain binary positioning patterns robust to any errors of rank less than a constant number. Additionally, we construct $q$-ary robust positioning sequences robust to a large number of errors, some of which have length attaining the upper bound. Our construction of binary positioning sequences that are robust to a constant number of errors has the least known redundancy amongst those explicit constructions with efficient locating algorithms. On the other hand, for binary robust positioning arrays, our construction is the first explicit construction whose redundancy is within a constant factor of optimality. The locating algorithms accompanying both constructions run in time cubic in sequence length or array dimension. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1912.13301v1-abstract-full').style.display = 'none'; document.getElementById('1912.13301v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 31 December, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2019. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Extended Version of SODA 2019 Paper</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 05B30; 94C30 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1912.11617">arXiv:1912.11617</a> <span> [<a href="https://arxiv.org/pdf/1912.11617">pdf</a>, <a href="https://arxiv.org/ps/1912.11617">ps</a>, <a href="https://arxiv.org/format/1912.11617">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Cryptography and Security">cs.CR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Symbolic Computation">cs.SC</span> </div> </div> <p class="title is-5 mathjax"> Efficient Algorithm for the Linear Complexity of Sequences and Some Related Consequences </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Chee%2C+Y+M">Yeow Meng Chee</a>, <a href="/search/?searchtype=author&query=Chrisnata%2C+J">Johan Chrisnata</a>, <a href="/search/?searchtype=author&query=Etzion%2C+T">Tuvi Etzion</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1912.11617v1-abstract-short" style="display: inline;"> The linear complexity of a sequence $s$ is one of the measures of its predictability. It represents the smallest degree of a linear recursion which the sequence satisfies. There are several algorithms to find the linear complexity of a periodic sequence $s$ of length $N$ (where $N$ is of some given form) over a finite field $F_q$ in $O(N)$ symbol field operations. The first such algorithm is The G… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1912.11617v1-abstract-full').style.display = 'inline'; document.getElementById('1912.11617v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1912.11617v1-abstract-full" style="display: none;"> The linear complexity of a sequence $s$ is one of the measures of its predictability. It represents the smallest degree of a linear recursion which the sequence satisfies. There are several algorithms to find the linear complexity of a periodic sequence $s$ of length $N$ (where $N$ is of some given form) over a finite field $F_q$ in $O(N)$ symbol field operations. The first such algorithm is The Games-Chan Algorithm which considers binary sequences of period $2^n$, and is known for its extreme simplicity. We generalize this algorithm and apply it efficiently for several families of binary sequences. Our algorithm is very simple, it requires $尾N$ bit operations for a small constant $尾$, where $N$ is the period of the sequence. We make an analysis on the number of bit operations required by the algorithm and compare it with previous algorithms. In the process, the algorithm also finds the recursion for the shortest linear feedback shift-register which generates the sequence. Some other interesting properties related to shift-register sequences, which might not be too surprising but generally unnoted, are also consequences of our exposition. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1912.11617v1-abstract-full').style.display = 'none'; document.getElementById('1912.11617v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 25 December, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2019. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1910.06501">arXiv:1910.06501</a> <span> [<a href="https://arxiv.org/pdf/1910.06501">pdf</a>, <a href="https://arxiv.org/ps/1910.06501">ps</a>, <a href="https://arxiv.org/format/1910.06501">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Optimal Codes Correcting a Single Indel / Edit for DNA-Based Data Storage </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Cai%2C+K">Kui Cai</a>, <a href="/search/?searchtype=author&query=Chee%2C+Y+M">Yeow Meng Chee</a>, <a href="/search/?searchtype=author&query=Gabrys%2C+R">Ryan Gabrys</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Nguyen%2C+T+T">Tuan Thanh Nguyen</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1910.06501v1-abstract-short" style="display: inline;"> An indel refers to a single insertion or deletion, while an edit refers to a single insertion, deletion or substitution. In this paper, we investigate codes that combat either a single indel or a single edit and provide linear-time algorithms that encode binary messages into these codes of length n. Over the quaternary alphabet, we provide two linear-time encoders. One corrects a single edit with… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1910.06501v1-abstract-full').style.display = 'inline'; document.getElementById('1910.06501v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1910.06501v1-abstract-full" style="display: none;"> An indel refers to a single insertion or deletion, while an edit refers to a single insertion, deletion or substitution. In this paper, we investigate codes that combat either a single indel or a single edit and provide linear-time algorithms that encode binary messages into these codes of length n. Over the quaternary alphabet, we provide two linear-time encoders. One corrects a single edit with log n + O(log log n) redundancy bits, while the other corrects a single indel with log n + 2 redundant bits. These two encoders are order-optimal. The former encoder is the first known order-optimal encoder that corrects a single edit, while the latter encoder (that corrects a single indel) reduces the redundancy of the best known encoder of Tenengolts (1984) by at least four bits. Over the DNA alphabet, we impose an additional constraint: the GC-balanced constraint and require that exactly half of the symbols of any DNA codeword to be either C or G. In particular, via a modification of Knuth's balancing technique, we provide a linear-time map that translates binary messages into GC-balanced codewords and the resulting codebook is able to correct a single indel or a single edit. These are the first known constructions of GC-balanced codes that correct a single indel or a single edit. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1910.06501v1-abstract-full').style.display = 'none'; document.getElementById('1910.06501v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 14 October, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2019. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">15 pages</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1907.02944">arXiv:1907.02944</a> <span> [<a href="https://arxiv.org/pdf/1907.02944">pdf</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Proceedings of the 11th Asia-Europe Workshop on Concepts in Information Theory </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Vinck%2C+A+J+H">A. J. Han Vinck</a>, <a href="/search/?searchtype=author&query=Immink%2C+K+A+S">Kees A. Schouhamer Immink</a>, <a href="/search/?searchtype=author&query=Wadayama%2C+T">Tadashi Wadayama</a>, <a href="/search/?searchtype=author&query=Vu%2C+V+K">Van Khu Vu</a>, <a href="/search/?searchtype=author&query=Manada%2C+A">Akiko Manada</a>, <a href="/search/?searchtype=author&query=Cai%2C+K">Kui Cai</a>, <a href="/search/?searchtype=author&query=Horii%2C+S">Shunsuke Horii</a>, <a href="/search/?searchtype=author&query=Abe%2C+Y">Yoshiki Abe</a>, <a href="/search/?searchtype=author&query=Iwamoto%2C+M">Mitsugu Iwamoto</a>, <a href="/search/?searchtype=author&query=Ohta%2C+K">Kazuo Ohta</a>, <a href="/search/?searchtype=author&query=Zhong%2C+X">Xingwei Zhong</a>, <a href="/search/?searchtype=author&query=Mei%2C+Z">Zhen Mei</a>, <a href="/search/?searchtype=author&query=Bu%2C+R">Renfei Bu</a>, <a href="/search/?searchtype=author&query=Weber%2C+J+H">J. H. Weber</a>, <a href="/search/?searchtype=author&query=Skachek%2C+V">Vitaly Skachek</a>, <a href="/search/?searchtype=author&query=Morita%2C+H">Hiroyoshi Morita</a>, <a href="/search/?searchtype=author&query=Hovhannisyan%2C+N">N. Hovhannisyan</a>, <a href="/search/?searchtype=author&query=Kamabe%2C+H">Hiroshi Kamabe</a>, <a href="/search/?searchtype=author&query=Lu%2C+S">Shan Lu</a>, <a href="/search/?searchtype=author&query=Yamamoto%2C+H">Hirosuke Yamamoto</a>, <a href="/search/?searchtype=author&query=Hasimoto%2C+K">Kengo Hasimoto</a>, <a href="/search/?searchtype=author&query=Ytrehus%2C+O">O. Ytrehus</a>, <a href="/search/?searchtype=author&query=Kuzuoaka%2C+S">Shigeaki Kuzuoaka</a>, <a href="/search/?searchtype=author&query=Nishiara%2C+M">Mikihiko Nishiara</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a> , et al. (2 additional authors not shown) </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1907.02944v1-abstract-short" style="display: inline;"> This year, 2019 we celebrate 30 years of our friendship between Asian and European scientists at the AEW11 in Rotterdam, the Netherlands. Many of the 1989 participants are also present at the 2019 event. This year we have many participants from different parts of Asia and Europe. It shows the importance of this event. It is a good tradition to pay a tribute to a special lecturer in our community.… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1907.02944v1-abstract-full').style.display = 'inline'; document.getElementById('1907.02944v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1907.02944v1-abstract-full" style="display: none;"> This year, 2019 we celebrate 30 years of our friendship between Asian and European scientists at the AEW11 in Rotterdam, the Netherlands. Many of the 1989 participants are also present at the 2019 event. This year we have many participants from different parts of Asia and Europe. It shows the importance of this event. It is a good tradition to pay a tribute to a special lecturer in our community. This year we selected Hiroyoshi Morita, who is a well known information theorist with many original contributions. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1907.02944v1-abstract-full').style.display = 'none'; document.getElementById('1907.02944v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 26 June, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2019. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1901.01023">arXiv:1901.01023</a> <span> [<a href="https://arxiv.org/pdf/1901.01023">pdf</a>, <a href="https://arxiv.org/ps/1901.01023">ps</a>, <a href="https://arxiv.org/format/1901.01023">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> </div> </div> <p class="title is-5 mathjax"> Efficient and Explicit Balanced Primer Codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Chee%2C+Y+M">Yeow Meng Chee</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Wei%2C+H">Hengjia Wei</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1901.01023v1-abstract-short" style="display: inline;"> To equip DNA-based data storage with random-access capabilities, Yazdi et al. (2018) prepended DNA strands with specially chosen address sequences called primers and provided certain design criteria for these primers. We provide explicit constructions of error-correcting codes that are suitable as primer addresses and equip these constructions with efficient encoding algorithms. Specifically, ou… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1901.01023v1-abstract-full').style.display = 'inline'; document.getElementById('1901.01023v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1901.01023v1-abstract-full" style="display: none;"> To equip DNA-based data storage with random-access capabilities, Yazdi et al. (2018) prepended DNA strands with specially chosen address sequences called primers and provided certain design criteria for these primers. We provide explicit constructions of error-correcting codes that are suitable as primer addresses and equip these constructions with efficient encoding algorithms. Specifically, our constructions take cyclic or linear codes as inputs and produce sets of primers with similar error-correcting capabilities. Using certain classes of BCH codes, we obtain infinite families of primer sets of length $n$, minimum distance $d$ with $(d + 1) \log_4 n + O(1)$ redundant symbols. Our techniques involve reversible cyclic codes (1964), an encoding method of Tavares et al. (1971) and Knuth's balancing technique (1986). In our investigation, we also construct efficient and explicit binary balanced error-correcting codes and codes for DNA computing. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1901.01023v1-abstract-full').style.display = 'none'; document.getElementById('1901.01023v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 4 January, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2019. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1901.00387">arXiv:1901.00387</a> <span> [<a href="https://arxiv.org/pdf/1901.00387">pdf</a>, <a href="https://arxiv.org/ps/1901.00387">ps</a>, <a href="https://arxiv.org/format/1901.00387">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Generalized Sphere-Packing Bound for Subblock-Constrained Codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Tandon%2C+A">Anshoo Tandon</a>, <a href="/search/?searchtype=author&query=Motani%2C+M">Mehul Motani</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1901.00387v1-abstract-short" style="display: inline;"> We apply the generalized sphere-packing bound to two classes of subblock-constrained codes. A la Fazeli et al. (2015), we made use of automorphism to significantly reduce the number of variables in the associated linear programming problem. In particular, we study binary constant subblock-composition codes (CSCCs), characterized by the property that the number of ones in each subblock is constant,… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1901.00387v1-abstract-full').style.display = 'inline'; document.getElementById('1901.00387v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1901.00387v1-abstract-full" style="display: none;"> We apply the generalized sphere-packing bound to two classes of subblock-constrained codes. A la Fazeli et al. (2015), we made use of automorphism to significantly reduce the number of variables in the associated linear programming problem. In particular, we study binary constant subblock-composition codes (CSCCs), characterized by the property that the number of ones in each subblock is constant, and binary subblock energy-constrained codes (SECCs), characterized by the property that the number of ones in each subblock exceeds a certain threshold. For CSCCs, we show that the optimization problem is equivalent to finding the minimum of $N$ variables, where $N$ is independent of the number of subblocks. We then provide closed-form solutions for the generalized sphere-packing bounds for single- and double-error correcting CSCCs. For SECCs, we provide closed-form solutions for the generalized sphere-packing bounds for single errors in certain special cases. We also obtain improved bounds on the optimal asymptotic rate for CSCCs and SECCs, and provide numerical examples to highlight the improvement. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1901.00387v1-abstract-full').style.display = 'none'; document.getElementById('1901.00387v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 2 January, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2019. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1808.09535">arXiv:1808.09535</a> <span> [<a href="https://arxiv.org/pdf/1808.09535">pdf</a>, <a href="https://arxiv.org/ps/1808.09535">ps</a>, <a href="https://arxiv.org/format/1808.09535">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Low-Power Cooling Codes with Efficient Encoding and Decoding </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Chee%2C+Y+M">Yeow Meng Chee</a>, <a href="/search/?searchtype=author&query=Etzion%2C+T">Tuvi Etzion</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Vardy%2C+A">Alexander Vardy</a>, <a href="/search/?searchtype=author&query=Wei%2C+H">Hengjia Wei</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1808.09535v2-abstract-short" style="display: inline;"> A class of low-power cooling (LPC) codes, to control simultaneously both the peak temperature and the average power consumption of interconnects, was introduced recently. An $(n,t,w)$-LPC code is a coding scheme over $n$ wires that (A) avoids state transitions on the $t$ hottest wires (cooling), and (B) limits the number of transitions to $w$ in each transmission (low-power). A few constructions… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1808.09535v2-abstract-full').style.display = 'inline'; document.getElementById('1808.09535v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1808.09535v2-abstract-full" style="display: none;"> A class of low-power cooling (LPC) codes, to control simultaneously both the peak temperature and the average power consumption of interconnects, was introduced recently. An $(n,t,w)$-LPC code is a coding scheme over $n$ wires that (A) avoids state transitions on the $t$ hottest wires (cooling), and (B) limits the number of transitions to $w$ in each transmission (low-power). A few constructions for large LPC codes that have efficient encoding and decoding schemes, are given. In particular, when $w$ is fixed, we construct LPC codes of size $(n/w)^{w-1}$ and show that these LPC codes can be modified to correct errors efficiently. We further present a construction for large LPC codes based on a mapping from cooling codes to LPC codes. The efficiency of the encoding/decoding for the constructed LPC codes depends on the efficiency of the decoding/encoding for the related cooling codes and the ones for the mapping. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1808.09535v2-abstract-full').style.display = 'none'; document.getElementById('1808.09535v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 19 March, 2019; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 16 August, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 2018. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1807.10954">arXiv:1807.10954</a> <span> [<a href="https://arxiv.org/pdf/1807.10954">pdf</a>, <a href="https://arxiv.org/format/1807.10954">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> </div> </div> <p class="title is-5 mathjax"> Domination Mappings into the Hamming Ball: Existence, Constructions, and Algorithms </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Chee%2C+Y+M">Yeow Meng Chee</a>, <a href="/search/?searchtype=author&query=Etzion%2C+T">Tuvi Etzion</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Vardy%2C+A">Alexander Vardy</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1807.10954v1-abstract-short" style="display: inline;"> The Hamming ball of radius $w$ in $\{0,1\}^n$ is the set ${\cal B}(n,w)$ of all binary words of length $n$ and Hamming weight at most $w$. We consider injective mappings $\varphi: \{0,1\}^m \to {\cal B}(n,w)$ with the following domination property: every position $j \in [n]$ is dominated by some position $i \in [m]$, in the sense that "switching off" position $i$ in $x \in \{0,1\}^m$ necessarily s… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1807.10954v1-abstract-full').style.display = 'inline'; document.getElementById('1807.10954v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1807.10954v1-abstract-full" style="display: none;"> The Hamming ball of radius $w$ in $\{0,1\}^n$ is the set ${\cal B}(n,w)$ of all binary words of length $n$ and Hamming weight at most $w$. We consider injective mappings $\varphi: \{0,1\}^m \to {\cal B}(n,w)$ with the following domination property: every position $j \in [n]$ is dominated by some position $i \in [m]$, in the sense that "switching off" position $i$ in $x \in \{0,1\}^m$ necessarily switches off position $j$ in its image $\varphi(x)$. This property may be described more precisely in terms of a bipartite \emph{domination graph} $G = ([m] \cup [n], E)$ with no isolated vertices, for all $(i,j) \in E$ and all $x \in \{0,1\}^m$, we require that $x_i = 0$ implies $y_j = 0$, where $y = \varphi(x)$. Although such domination mappings recently found applications in the context of coding for high-performance interconnects, to the best of our knowledge, they were not previously studied. In this paper, we begin with simple necessary conditions for the existence of an $(m,n,w)$-domination mapping $\varphi: \{0,1\}^m \to {\cal B}(n,w)$. We then provide several explicit constructions of such mappings, which show that the necessary conditions are also sufficient when $w=1$, when $w=2$ and $m$ is odd, or when $m \le 3w$. One of our main results herein is a proof that the trivial necessary condition $|{\cal B}(n,w)| \ge 2^m$ for the existence of an injection is, in fact, sufficient for the existence of an $(m,n,w)$-domination mapping whenever $m$ is sufficiently large. We also present a polynomial-time algorithm that, given any $m$, $n$, and $w$, determines whether an $(m,n,w)$-domination mapping exists for a domination graph with an equitable degree distribution. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1807.10954v1-abstract-full').style.display = 'none'; document.getElementById('1807.10954v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 28 July, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2018. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1801.02310">arXiv:1801.02310</a> <span> [<a href="https://arxiv.org/pdf/1801.02310">pdf</a>, <a href="https://arxiv.org/ps/1801.02310">ps</a>, <a href="https://arxiv.org/format/1801.02310">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Efficient Encoding/Decoding of Irreducible Words for Codes Correcting Tandem Duplications </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Chee%2C+Y+M">Yeow Meng Chee</a>, <a href="/search/?searchtype=author&query=Chrisnata%2C+J">Johan Chrisnata</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Nguyen%2C+T+T">Tuan Thanh Nguyen</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1801.02310v1-abstract-short" style="display: inline;"> Tandem duplication is the process of inserting a copy of a segment of DNA adjacent to the original position. Motivated by applications that store data in living organisms, Jain et al. (2017) proposed the study of codes that correct tandem duplications. Known code constructions are based on {\em irreducible words}. We study efficient encoding/decoding methods for irreducible words. First, we desc… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1801.02310v1-abstract-full').style.display = 'inline'; document.getElementById('1801.02310v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1801.02310v1-abstract-full" style="display: none;"> Tandem duplication is the process of inserting a copy of a segment of DNA adjacent to the original position. Motivated by applications that store data in living organisms, Jain et al. (2017) proposed the study of codes that correct tandem duplications. Known code constructions are based on {\em irreducible words}. We study efficient encoding/decoding methods for irreducible words. First, we describe an $(\ell,m)$-finite state encoder and show that when $m=螛(1/蔚)$ and $\ell=螛(1/蔚)$, the encoder achieves rate that is $蔚$ away from the optimal. Next, we provide ranking/unranking algorithms for irreducible words and modify the algorithms to reduce the space requirements for the finite state encoder. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1801.02310v1-abstract-full').style.display = 'none'; document.getElementById('1801.02310v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 8 January, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2018. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1709.05214">arXiv:1709.05214</a> <span> [<a href="https://arxiv.org/pdf/1709.05214">pdf</a>, <a href="https://arxiv.org/format/1709.05214">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Mutually Uncorrelated Primers for DNA-Based Data Storage </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Yazdi%2C+S+M+H+T">S. M. Hossein Tabatabaei Yazdi</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Gabrys%2C+R">Ryan Gabrys</a>, <a href="/search/?searchtype=author&query=Milenkovic%2C+O">Olgica Milenkovic</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1709.05214v1-abstract-short" style="display: inline;"> We introduce the notion of weakly mutually uncorrelated (WMU) sequences, motivated by applications in DNA-based data storage systems and for synchronization of communication devices. WMU sequences are characterized by the property that no sufficiently long suffix of one sequence is the prefix of the same or another sequence. WMU sequences used for primer design in DNA-based data storage systems ar… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1709.05214v1-abstract-full').style.display = 'inline'; document.getElementById('1709.05214v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1709.05214v1-abstract-full" style="display: none;"> We introduce the notion of weakly mutually uncorrelated (WMU) sequences, motivated by applications in DNA-based data storage systems and for synchronization of communication devices. WMU sequences are characterized by the property that no sufficiently long suffix of one sequence is the prefix of the same or another sequence. WMU sequences used for primer design in DNA-based data storage systems are also required to be at large mutual Hamming distance from each other, have balanced compositions of symbols, and avoid primer-dimer byproducts. We derive bounds on the size of WMU and various constrained WMU codes and present a number of constructions for balanced, error-correcting, primer-dimer free WMU codes using Dyck paths, prefix-synchronized and cyclic codes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1709.05214v1-abstract-full').style.display = 'none'; document.getElementById('1709.05214v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 13 September, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2017. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">14 pages, 3 figures, 1 Table. arXiv admin note: text overlap with arXiv:1601.08176</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1707.03956">arXiv:1707.03956</a> <span> [<a href="https://arxiv.org/pdf/1707.03956">pdf</a>, <a href="https://arxiv.org/format/1707.03956">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> </div> </div> <p class="title is-5 mathjax"> Deciding the Confusability of Words under Tandem Repeats </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Chee%2C+Y+M">Yeow Meng Chee</a>, <a href="/search/?searchtype=author&query=Chrisnata%2C+J">Johan Chrisnata</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Nguyen%2C+T+T">Tuan Thanh Nguyen</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1707.03956v2-abstract-short" style="display: inline;"> Tandem duplication in DNA is the process of inserting a copy of a segment of DNA adjacent to the original position. Motivated by applications that store data in living organisms, Jain {\em et al.} (2016) proposed the study of codes that correct tandem duplications to improve the reliability of data storage. We investigate algorithms associated with the study of these codes. Two words are said to… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1707.03956v2-abstract-full').style.display = 'inline'; document.getElementById('1707.03956v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1707.03956v2-abstract-full" style="display: none;"> Tandem duplication in DNA is the process of inserting a copy of a segment of DNA adjacent to the original position. Motivated by applications that store data in living organisms, Jain {\em et al.} (2016) proposed the study of codes that correct tandem duplications to improve the reliability of data storage. We investigate algorithms associated with the study of these codes. Two words are said to be ${\le}k$-confusable if there exists two sequences of tandem duplications of lengths at most $k$ such that the resulting words are equal. We demonstrate that the problem of deciding whether two words is ${\le}k$-confusable is linear-time solvable through a characterisation that can be checked efficiently for $k=3$. Combining with previous results, the decision problem is linear-time solvable for $k\le 3$. We conjecture that this problem is undecidable for $k>3$. Using insights gained from the algorithm, we study the size of tandem-duplication codes. We improve the previous known upper bound and then construct codes with larger sizes as compared to the previous constructions. We determine the sizes of optimal tandem-duplication codes for lengths up to twenty, develop recursive methods to construct tandem-duplication codes for all word lengths, and compute explicit lower bounds for the size of optimal tandem-duplication codes for lengths from 21 to 30. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1707.03956v2-abstract-full').style.display = 'none'; document.getElementById('1707.03956v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 17 November, 2017; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 12 July, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2017. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1701.07872">arXiv:1701.07872</a> <span> [<a href="https://arxiv.org/pdf/1701.07872">pdf</a>, <a href="https://arxiv.org/format/1701.07872">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Cooling Codes: Thermal-Management Coding for High-Performance Interconnects </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Chee%2C+Y+M">Yeow Meng Chee</a>, <a href="/search/?searchtype=author&query=Etzion%2C+T">Tuvi Etzion</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Vardy%2C+A">Alexander Vardy</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1701.07872v2-abstract-short" style="display: inline;"> High temperatures have dramatic negative effects on interconnect performance and, hence, numerous techniques have been proposed to reduce the power consumption of on-chip buses. However, existing methods fall short of fully addressing the thermal challenges posed by high-performance interconnects. In this paper, we introduce new efficient coding schemes that make it possible to directly control th… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1701.07872v2-abstract-full').style.display = 'inline'; document.getElementById('1701.07872v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1701.07872v2-abstract-full" style="display: none;"> High temperatures have dramatic negative effects on interconnect performance and, hence, numerous techniques have been proposed to reduce the power consumption of on-chip buses. However, existing methods fall short of fully addressing the thermal challenges posed by high-performance interconnects. In this paper, we introduce new efficient coding schemes that make it possible to directly control the peak temperature of a bus by effectively cooling its hottest wires. This is achieved by avoiding state transitions on the hottest wires for as long as necessary until their temperature drops off. We also reduce the average power consumption by making sure that the total number of state transitions on all the wires is below a prescribed threshold. We show how each of these two features can be coded for separately or, alternatively, how both can be achieved at the same time. In addition, error-correction for the transmitted information can be provided while controlling the peak temperature and/or the average power consumption. In general, our cooling codes use $n > k$ wires to encode a given $k$-bit bus. One of our goals herein is to determine the minimum possible number of wires $n$ needed to encode $k$ bits while satisfying any combination of the three desired properties. We provide full theoretical analysis in each case. In particular, we show that $n = k+t+1$ suffices to cool the $t$ hottest wires, and this is the best possible. Moreover, although the proposed coding schemes make use of sophisticated tools from combinatorics, discrete geometry, linear algebra, and coding theory, the resulting encoders and decoders are fully practical. They do not require significant computational overhead and can be implemented without sacrificing a large circuit area. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1701.07872v2-abstract-full').style.display = 'none'; document.getElementById('1701.07872v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 23 October, 2017; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 26 January, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2017. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1701.07118">arXiv:1701.07118</a> <span> [<a href="https://arxiv.org/pdf/1701.07118">pdf</a>, <a href="https://arxiv.org/format/1701.07118">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Repairing Reed-Solomon Codes With Two Erasures </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Dau%2C+H">Hoang Dau</a>, <a href="/search/?searchtype=author&query=Duursma%2C+I">Iwan Duursma</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Milenkovic%2C+O">Olgica Milenkovic</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1701.07118v2-abstract-short" style="display: inline;"> Despite their exceptional error-correcting properties, Reed-Solomon (RS) codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth: A naive repair approach would require the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC'16) proposed a single-erasur… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1701.07118v2-abstract-full').style.display = 'inline'; document.getElementById('1701.07118v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1701.07118v2-abstract-full" style="display: none;"> Despite their exceptional error-correcting properties, Reed-Solomon (RS) codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth: A naive repair approach would require the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC'16) proposed a single-erasure repair method for RS codes that achieves the optimal repair bandwidth amongst all linear encoding schemes. We extend their trace collection technique to cope with two erasures. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1701.07118v2-abstract-full').style.display = 'none'; document.getElementById('1701.07118v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 14 May, 2017; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 24 January, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2017. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">ISIT'17 (accepted), 5 pages. arXiv admin note: substantial text overlap with arXiv:1612.01361</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1701.06874">arXiv:1701.06874</a> <span> [<a href="https://arxiv.org/pdf/1701.06874">pdf</a>, <a href="https://arxiv.org/ps/1701.06874">ps</a>, <a href="https://arxiv.org/format/1701.06874">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Coding for Racetrack Memories </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Chee%2C+Y+M">Yeow Meng Chee</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Vardy%2C+A">Alexander Vardy</a>, <a href="/search/?searchtype=author&query=Vu%2C+V+K">Van Khu Vu</a>, <a href="/search/?searchtype=author&query=Yaakobi%2C+E">Eitan Yaakobi</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1701.06874v1-abstract-short" style="display: inline;"> Racetrack memory is a new technology which utilizes magnetic domains along a nanoscopic wire in order to obtain extremely high storage density. In racetrack memory, each magnetic domain can store a single bit of information, which can be sensed by a reading port (head). The memory has a tape-like structure which supports a shift operation that moves the domains to be read sequentially by the head.… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1701.06874v1-abstract-full').style.display = 'inline'; document.getElementById('1701.06874v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1701.06874v1-abstract-full" style="display: none;"> Racetrack memory is a new technology which utilizes magnetic domains along a nanoscopic wire in order to obtain extremely high storage density. In racetrack memory, each magnetic domain can store a single bit of information, which can be sensed by a reading port (head). The memory has a tape-like structure which supports a shift operation that moves the domains to be read sequentially by the head. In order to increase the memory's speed, prior work studied how to minimize the latency of the shift operation, while the no less important reliability of this operation has received only a little attention. In this work we design codes which combat shift errors in racetrack memory, called position errors. Namely, shifting the domains is not an error-free operation and the domains may be over-shifted or are not shifted, which can be modeled as deletions and sticky insertions. While it is possible to use conventional deletion and insertion-correcting codes, we tackle this problem with the special structure of racetrack memory, where the domains can be read by multiple heads. Each head outputs a noisy version of the stored data and the multiple outputs are combined in order to reconstruct the data. Under this paradigm, we will show that it is possible to correct, with at most a single bit of redundancy, $d$ deletions with $d+1$ heads if the heads are well-separated. Similar results are provided for burst of deletions, sticky insertions and combinations of both deletions and sticky insertions. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1701.06874v1-abstract-full').style.display = 'none'; document.getElementById('1701.06874v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 24 January, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2017. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1701.04954">arXiv:1701.04954</a> <span> [<a href="https://arxiv.org/pdf/1701.04954">pdf</a>, <a href="https://arxiv.org/ps/1701.04954">ps</a>, <a href="https://arxiv.org/format/1701.04954">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Bounds on the Size and Asymptotic Rate of Subblock-Constrained Codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Tandon%2C+A">Anshoo Tandon</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Motani%2C+M">Mehul Motani</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1701.04954v1-abstract-short" style="display: inline;"> The study of subblock-constrained codes has recently gained attention due to their application in diverse fields. We present bounds on the size and asymptotic rate for two classes of subblock-constrained codes. The first class is binary constant subblock-composition codes (CSCCs), where each codeword is partitioned into equal sized subblocks, and every subblock has the same fixed weight. The secon… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1701.04954v1-abstract-full').style.display = 'inline'; document.getElementById('1701.04954v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1701.04954v1-abstract-full" style="display: none;"> The study of subblock-constrained codes has recently gained attention due to their application in diverse fields. We present bounds on the size and asymptotic rate for two classes of subblock-constrained codes. The first class is binary constant subblock-composition codes (CSCCs), where each codeword is partitioned into equal sized subblocks, and every subblock has the same fixed weight. The second class is binary subblock energy-constrained codes (SECCs), where the weight of every subblock exceeds a given threshold. We present novel upper and lower bounds on the code sizes and asymptotic rates for binary CSCCs and SECCs. For a fixed subblock length and small relative distance, we show that the asymptotic rate for CSCCs (resp. SECCs) is strictly lower than the corresponding rate for constant weight codes (CWCs) (resp. heavy weight codes (HWCs)). Further, for codes with high weight and low relative distance, we show that the asymptotic rates for CSCCs is strictly lower than that of SECCs, which contrasts that the asymptotic rate for CWCs is equal to that of HWCs. We also provide a correction to an earlier result by Chee et al. (2014) on the asymptotic CSCC rate. Additionally, we present several numerical examples comparing the rates for CSCCs and SECCs with those for constant weight codes and heavy weight codes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1701.04954v1-abstract-full').style.display = 'none'; document.getElementById('1701.04954v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 18 January, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2017. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1612.01361">arXiv:1612.01361</a> <span> [<a href="https://arxiv.org/pdf/1612.01361">pdf</a>, <a href="https://arxiv.org/format/1612.01361">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1109/TIT.2018.2827942">10.1109/TIT.2018.2827942 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Repairing Reed-Solomon Codes With Multiple Erasures </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Dau%2C+H">Hoang Dau</a>, <a href="/search/?searchtype=author&query=Duursma%2C+I">Iwan Duursma</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Milenkovic%2C+O">Olgica Milenkovic</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1612.01361v2-abstract-short" style="display: inline;"> Despite their exceptional error-correcting properties, Reed-Solomon codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth: A naive repair approach would require the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC'16) proposed a single-erasure rep… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1612.01361v2-abstract-full').style.display = 'inline'; document.getElementById('1612.01361v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1612.01361v2-abstract-full" style="display: none;"> Despite their exceptional error-correcting properties, Reed-Solomon codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth: A naive repair approach would require the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC'16) proposed a single-erasure repair method for Reed-Solomon codes that achieves the optimal repair bandwidth amongst all linear encoding schemes. Their key idea is to recover the erased symbol by collecting a sufficiently large number of its traces, each of which can be constructed from a number of traces of other symbols. We extend the trace collection technique to cope with two and three erasures. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1612.01361v2-abstract-full').style.display = 'none'; document.getElementById('1612.01361v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 2 May, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 28 November, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2016. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">15 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> IEEE Transactions on Information Theory (2018) 64(10) 6567-6582 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1607.02279">arXiv:1607.02279</a> <span> [<a href="https://arxiv.org/pdf/1607.02279">pdf</a>, <a href="https://arxiv.org/format/1607.02279">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> </div> </div> <p class="title is-5 mathjax"> Rates of DNA Sequence Profiles for Practical Values of Read Lengths </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Chang%2C+Z">Zuling Chang</a>, <a href="/search/?searchtype=author&query=Chrisnata%2C+J">Johan Chrisnata</a>, <a href="/search/?searchtype=author&query=Ezerman%2C+M+F">Martianus Frederic Ezerman</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1607.02279v1-abstract-short" style="display: inline;"> A recent study by one of the authors has demonstrated the importance of profile vectors in DNA-based data storage. We provide exact values and lower bounds on the number of profile vectors for finite values of alphabet size $q$, read length $\ell$, and word length $n$.Consequently, we demonstrate that for $q\ge 2$ and $n\le q^{\ell/2-1}$, the number of profile vectors is at least $q^{魏n}$ with… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1607.02279v1-abstract-full').style.display = 'inline'; document.getElementById('1607.02279v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1607.02279v1-abstract-full" style="display: none;"> A recent study by one of the authors has demonstrated the importance of profile vectors in DNA-based data storage. We provide exact values and lower bounds on the number of profile vectors for finite values of alphabet size $q$, read length $\ell$, and word length $n$.Consequently, we demonstrate that for $q\ge 2$ and $n\le q^{\ell/2-1}$, the number of profile vectors is at least $q^{魏n}$ with $魏$ very close to one.In addition to enumeration results, we provide a set of efficient encoding and decoding algorithms for each of two particular families of profile vectors. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1607.02279v1-abstract-full').style.display = 'none'; document.getElementById('1607.02279v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 8 July, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2016. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1601.08176">arXiv:1601.08176</a> <span> [<a href="https://arxiv.org/pdf/1601.08176">pdf</a>, <a href="https://arxiv.org/ps/1601.08176">ps</a>, <a href="https://arxiv.org/format/1601.08176">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Weakly Mutually Uncorrelated Codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/?searchtype=author&query=Yazdi%2C+S+M+H+T">S. M. Hossein Tabatabaei Yazdi</a>, <a href="/search/?searchtype=author&query=Kiah%2C+H+M">Han Mao Kiah</a>, <a href="/search/?searchtype=author&query=Milenkovic%2C+O">Olgica Milenkovic</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1601.08176v1-abstract-short" style="display: inline;"> We introduce the notion of weakly mutually uncorrelated (WMU) sequences, motivated by applications in DNA-based storage systems and synchronization protocols. WMU sequences are characterized by the property that no sufficiently long suffix of one sequence is the prefix of the same or another sequence. In addition, WMU sequences used in DNA-based storage systems are required to have balanced compos… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1601.08176v1-abstract-full').style.display = 'inline'; document.getElementById('1601.08176v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1601.08176v1-abstract-full" style="display: none;"> We introduce the notion of weakly mutually uncorrelated (WMU) sequences, motivated by applications in DNA-based storage systems and synchronization protocols. WMU sequences are characterized by the property that no sufficiently long suffix of one sequence is the prefix of the same or another sequence. In addition, WMU sequences used in DNA-based storage systems are required to have balanced compositions of symbols and to be at large mutual Hamming distance from each other. We present a number of constructions for balanced, error-correcting WMU codes using Dyck paths, Knuth's balancing principle, prefix synchronized and cyclic codes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1601.08176v1-abstract-full').style.display = 'none'; document.getElementById('1601.08176v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 29 January, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2016. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">1 table</span> </p> </li> </ol> <nav class="pagination is-small is-centered breathe-horizontal" role="navigation" aria-label="pagination"> <a href="" class="pagination-previous is-invisible">Previous </a> <a href="/search/?searchtype=author&query=Kiah%2C+H+M&start=50" class="pagination-next" >Next </a> <ul class="pagination-list"> <li> <a href="/search/?searchtype=author&query=Kiah%2C+H+M&start=0" class="pagination-link is-current" aria-label="Goto page 1">1 </a> </li> <li> <a href="/search/?searchtype=author&query=Kiah%2C+H+M&start=50" class="pagination-link " aria-label="Page 2" aria-current="page">2 </a> </li> </ul> </nav> <div class="is-hidden-tablet">  <span class="help" style="display: inline-block;"><a href="https://github.com/arXiv/arxiv-search/releases">Search v0.5.6 released 2020-02-24</a>  </span> </div> </div> </main> <footer> <div class="columns is-desktop" role="navigation" aria-label="Secondary">  <div class="column"> <div class="columns"> <div class="column"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/about">About</a></li> <li><a href="https://info.arxiv.org/help">Help</a></li> </ul> </div> <div class="column"> <ul class="nav-spaced"> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>contact arXiv</title><desc>Click here to contact arXiv</desc><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg> <a href="https://info.arxiv.org/help/contact.html"> Contact</a> </li> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>subscribe to arXiv mailings</title><desc>Click here to subscribe</desc><path d="M476 3.2L12.5 270.6c-18.1 10.4-15.8 35.6 2.2 43.2L121 358.4l287.3-253.2c5.5-4.9 13.3 2.6 8.6 8.3L176 407v80.5c0 23.6 28.5 32.9 42.5 15.8L282 426l124.6 52.2c14.2 6 30.4-2.9 33-18.2l72-432C515 7.8 493.3-6.8 476 3.2z"/></svg> <a href="https://info.arxiv.org/help/subscribe"> Subscribe</a> </li> </ul> </div> </div> </div>   <div class="column"> <div class="columns"> <div class="column"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/help/license/index.html">Copyright</a></li> <li><a href="https://info.arxiv.org/help/policies/privacy_policy.html">Privacy Policy</a></li> </ul> </div> <div class="column sorry-app-links"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/help/web_accessibility.html">Web Accessibility Assistance</a></li> <li> <p class="help"> <a class="a11y-main-link" href="https://status.arxiv.org" target="_blank">arXiv Operational Status <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 256 512" class="icon filter-dark_grey" role="presentation"><path d="M224.3 273l-136 136c-9.4 9.4-24.6 9.4-33.9 0l-22.6-22.6c-9.4-9.4-9.4-24.6 0-33.9l96.4-96.4-96.4-96.4c-9.4-9.4-9.4-24.6 0-33.9L54.3 103c9.4-9.4 24.6-9.4 33.9 0l136 136c9.5 9.4 9.5 24.6.1 34z"/></svg></a><br> Get status notifications via <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/email/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg>email</a> or <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/slack/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512" class="icon filter-black" role="presentation"><path d="M94.12 315.1c0 25.9-21.16 47.06-47.06 47.06S0 341 0 315.1c0-25.9 21.16-47.06 47.06-47.06h47.06v47.06zm23.72 0c0-25.9 21.16-47.06 47.06-47.06s47.06 21.16 47.06 47.06v117.84c0 25.9-21.16 47.06-47.06 47.06s-47.06-21.16-47.06-47.06V315.1zm47.06-188.98c-25.9 0-47.06-21.16-47.06-47.06S139 32 164.9 32s47.06 21.16 47.06 47.06v47.06H164.9zm0 23.72c25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06H47.06C21.16 243.96 0 222.8 0 196.9s21.16-47.06 47.06-47.06H164.9zm188.98 47.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06h-47.06V196.9zm-23.72 0c0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06V79.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06V196.9zM283.1 385.88c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06v-47.06h47.06zm0-23.72c-25.9 0-47.06-21.16-47.06-47.06 0-25.9 21.16-47.06 47.06-47.06h117.84c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06H283.1z"/></svg>slack</a> </p> </li> </ul> </div> </div> </div>  </div> </footer> <script src="https://static.arxiv.org/static/base/1.0.0a5/js/member_acknowledgement.js"></script> </body> </html>

CINXE.COM

Search | arXiv e-print repository