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–36 of 36 results for author: <span class="mathjax">Vorobyev, I</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/cs" aria-role="search"> Searching in archive <strong>cs</strong>. <a href="/search/?searchtype=author&query=Vorobyev%2C+I">Search in all archives.</a> <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="Vorobyev, I"> </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=Vorobyev%2C+I&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="Vorobyev, I"> <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> <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/2404.02723">arXiv:2404.02723</a> <span> [<a href="https://arxiv.org/pdf/2404.02723">pdf</a>, <a href="https://arxiv.org/ps/2404.02723">ps</a>, <a href="https://arxiv.org/format/2404.02723">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"> Deterministic Identification Codes for Fading Channels </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</a>, <a href="/search/cs?searchtype=author&query=Deppe%2C+C">Christian Deppe</a>, <a href="/search/cs?searchtype=author&query=Boche%2C+H">Holger Boche</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="2404.02723v3-abstract-short" style="display: inline;"> Many communication applications incorporate event-triggered behavior, where the conventional Shannon capacity may not effectively gauge performance. Consequently, we advocate for the concept of identification capacity as a more suitable metric for assessing these systems. We consider deterministic identification codes for the Gaussian AWGN, the slow fading, and the fast fading channels with power… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2404.02723v3-abstract-full').style.display = 'inline'; document.getElementById('2404.02723v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2404.02723v3-abstract-full" style="display: none;"> Many communication applications incorporate event-triggered behavior, where the conventional Shannon capacity may not effectively gauge performance. Consequently, we advocate for the concept of identification capacity as a more suitable metric for assessing these systems. We consider deterministic identification codes for the Gaussian AWGN, the slow fading, and the fast fading channels with power constraints. We prove lower bounds on capacities for the slow and the fast fading channels with side information for a wide range of fading distributions. Additionally, we present the code construction with efficient encoding which achieves the lower bound on capacity both for the slow and the fast fading channels. At last, we prove the same lower bound on the capacity of the fast fading channel without side information, i.e., the same lower bound holds even when the receiver does not know the fading coefficients. As a result we show that compared with Shannon's message transmission paradigm we achieved completely different capacity scaling for deterministic identification codes for all relevant fading channels. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2404.02723v3-abstract-full').style.display = 'none'; document.getElementById('2404.02723v3-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 February, 2025; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 3 April, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 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">Simplified proofs, extended presentation, minor corrections</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2401.16540">arXiv:2401.16540</a> <span> [<a href="https://arxiv.org/pdf/2401.16540">pdf</a>, <a href="https://arxiv.org/ps/2401.16540">ps</a>, <a href="https://arxiv.org/format/2401.16540">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 Combinatorial Group Testing: Bridging the Gap between Union-Free and Disjunctive Codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Goshkoder%2C+D">Daniil Goshkoder</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N">Nikita Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</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="2401.16540v1-abstract-short" style="display: inline;"> This work focuses on non-adaptive group testing, with a primary goal of efficiently identifying a set of at most $d$ defective elements among a given set of elements using the fewest possible number of tests. Non-adaptive combinatorial group testing often employs disjunctive codes and union-free codes. This paper discusses union-free codes with fast decoding (UFFD codes), a recently introduced cla… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2401.16540v1-abstract-full').style.display = 'inline'; document.getElementById('2401.16540v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2401.16540v1-abstract-full" style="display: none;"> This work focuses on non-adaptive group testing, with a primary goal of efficiently identifying a set of at most $d$ defective elements among a given set of elements using the fewest possible number of tests. Non-adaptive combinatorial group testing often employs disjunctive codes and union-free codes. This paper discusses union-free codes with fast decoding (UFFD codes), a recently introduced class of union-free codes that combine the best of both worlds -- the linear complexity decoding of disjunctive codes and the fewest number of tests of union-free codes. In our study, we distinguish two subclasses of these codes -- one subclass, denoted as $(=d)$-UFFD codes, can be used when the number of defectives $d$ is a priori known, whereas $(\le d)$-UFFD codes works for any subset of at most $d$ defectives. Previous studies have established a lower bound on the rate of these codes for $d=2$. Our contribution lies in deriving new lower bounds on the rate for both $(=d)$- and $(\le d)$-UFFD codes for an arbitrary number $d \ge 2$ of defectives. Our results show that for $d\to\infty$, the rate of $(=d)$-UFFD codes is twice as large as the best-known lower bound on the rate of $d$-disjunctive codes. In addition, the rate of $(\le d)$-UFFD code is shown to be better than the known lower bound on the rate of $d$-disjunctive codes for small values of $d$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2401.16540v1-abstract-full').style.display = 'none'; document.getElementById('2401.16540v1-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, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2305.06691">arXiv:2305.06691</a> <span> [<a href="https://arxiv.org/pdf/2305.06691">pdf</a>, <a href="https://arxiv.org/ps/2305.06691">ps</a>, <a href="https://arxiv.org/format/2305.06691">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"> Correcting One Error in Non-Binary Channels with Feedback </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</a>, <a href="/search/cs?searchtype=author&query=Lebedev%2C+V">Vladimir Lebedev</a>, <a href="/search/cs?searchtype=author&query=Lebedev%2C+A">Alexey Lebedev</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.06691v1-abstract-short" style="display: inline;"> In this paper, the problem of correction of a single error in $q$-ary symmetric channel with noiseless feedback is considered. We propose an algorithm to construct codes with feedback inductively. For all prime power $q$ we prove that two instances of feedback are sufficient to transmit over the $q$-ary symmetric channel the same number of messages as in the case of complete feedback. Our other co… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.06691v1-abstract-full').style.display = 'inline'; document.getElementById('2305.06691v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2305.06691v1-abstract-full" style="display: none;"> In this paper, the problem of correction of a single error in $q$-ary symmetric channel with noiseless feedback is considered. We propose an algorithm to construct codes with feedback inductively. For all prime power $q$ we prove that two instances of feedback are sufficient to transmit over the $q$-ary symmetric channel the same number of messages as in the case of complete feedback. Our other contribution is the construction of codes with one-time feedback with the same parameters as Hamming codes for $q$ that is not a prime power. We also construct single-error-correcting codes with one-time feedback of size $q^{n-2}$ for arbitrary $q$ and $n\leq q+1$, which can be seen as an analog for Reed-Solomon codes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.06691v1-abstract-full').style.display = 'none'; document.getElementById('2305.06691v1-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> 11 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/2304.12399">arXiv:2304.12399</a> <span> [<a href="https://arxiv.org/pdf/2304.12399">pdf</a>, <a href="https://arxiv.org/format/2304.12399">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"> Codes Correcting a Single Long Duplication Error </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Goshkoder%2C+D">Daniil Goshkoder</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N">Nikita Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</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="2304.12399v1-abstract-short" style="display: inline;"> We consider the problem of constructing a code capable of correcting a single long tandem duplication error of variable length. As the main contribution of this paper, we present a $q$-ary efficiently encodable code of length $n+1$ and redundancy $1$ that can correct a single duplication of length at least $K=4\cdot\lceil \log_q n\rceil +1$. The complexity of encoding is $O(\frac{n^2}{\log n})$ an… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2304.12399v1-abstract-full').style.display = 'inline'; document.getElementById('2304.12399v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2304.12399v1-abstract-full" style="display: none;"> We consider the problem of constructing a code capable of correcting a single long tandem duplication error of variable length. As the main contribution of this paper, we present a $q$-ary efficiently encodable code of length $n+1$ and redundancy $1$ that can correct a single duplication of length at least $K=4\cdot\lceil \log_q n\rceil +1$. The complexity of encoding is $O(\frac{n^2}{\log n})$ and the complexity of decoding is $O(n)$. We also present a $q$-ary non-efficient code of length $n+1$ correcting single long duplication of length at least $K = \lceil \log_q n\rceil +蠁(n)$, where $蠁(n)\rightarrow{\infty}$ as $n\rightarrow{\infty}$. This code has redundancy less than $1$ for sufficiently large $n$. Moreover, we show that in the class of codes correcting a single long duplication with redundancy $1$, the value $K$ in our constructions is order-optimal. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2304.12399v1-abstract-full').style.display = 'none'; document.getElementById('2304.12399v1-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 April, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 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.02414">arXiv:2302.02414</a> <span> [<a href="https://arxiv.org/pdf/2302.02414">pdf</a>, <a href="https://arxiv.org/ps/2302.02414">ps</a>, <a href="https://arxiv.org/format/2302.02414">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> <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"> Secure Codes with List Decoding </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Gu%2C+Y">Yujie Gu</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</a>, <a href="/search/cs?searchtype=author&query=Miao%2C+Y">Ying Miao</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.02414v1-abstract-short" style="display: inline;"> In this paper we consider combinatorial secure codes in traitor tracing for protecting copyright of multimedia content. First, we introduce a new notion of secure codes with list decoding (SCLDs) for collusion-resistant multimedia fingerprinting, which includes many existing types of fingerprinting codes as special cases. Next, we build efficient identifying algorithms for SCLDs with complete trac… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.02414v1-abstract-full').style.display = 'inline'; document.getElementById('2302.02414v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2302.02414v1-abstract-full" style="display: none;"> In this paper we consider combinatorial secure codes in traitor tracing for protecting copyright of multimedia content. First, we introduce a new notion of secure codes with list decoding (SCLDs) for collusion-resistant multimedia fingerprinting, which includes many existing types of fingerprinting codes as special cases. Next, we build efficient identifying algorithms for SCLDs with complete traceability and establish bounds on its largest possible code rate. In comparison with the existing fingerprinting codes, it is shown that SCLDs have not only much more efficient traceability than separable codes but also a much larger code rate than frameproof codes. As a byproduct, new bounds on the largest code rate of binary separable codes are established as well. Furthermore, a two-stage dynamic traitor tracing framework is proposed for multimedia fingerprinting in the dynamic scenario, which could not only efficiently achieve the complete traceability but also provide a much larger capacity than the static scenario. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.02414v1-abstract-full').style.display = 'none'; document.getElementById('2302.02414v1-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 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">20 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/2301.01848">arXiv:2301.01848</a> <span> [<a href="https://arxiv.org/pdf/2301.01848">pdf</a>, <a href="https://arxiv.org/ps/2301.01848">ps</a>, <a href="https://arxiv.org/format/2301.01848">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"> Correcting one error in channels with feedback </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</a>, <a href="/search/cs?searchtype=author&query=Lebedev%2C+A">Alexey Lebedev</a>, <a href="/search/cs?searchtype=author&query=Lebedev%2C+V">Vladimir Lebedev</a>, <a href="/search/cs?searchtype=author&query=Deppe%2C+C">Christian Deppe</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.01848v1-abstract-short" style="display: inline;"> We address the problem of correcting a single error in an arbitrary discrete memoryless channel with error-free instantaneous feedback. For the case of a one-time feedback, we propose a method for constructing optimal transmission strategies. The obtained result allows us to prove that for a binary channel, two feedbacks are sufficient to transmit the same number of messages as in the case of comp… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2301.01848v1-abstract-full').style.display = 'inline'; document.getElementById('2301.01848v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2301.01848v1-abstract-full" style="display: none;"> We address the problem of correcting a single error in an arbitrary discrete memoryless channel with error-free instantaneous feedback. For the case of a one-time feedback, we propose a method for constructing optimal transmission strategies. The obtained result allows us to prove that for a binary channel, two feedbacks are sufficient to transmit the same number of messages as in the case of complete feedback. We also apply the developed techniques to a binary asymmetric channel to construct transmission strategies for small lengths. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2301.01848v1-abstract-full').style.display = 'none'; document.getElementById('2301.01848v1-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, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2211.04264">arXiv:2211.04264</a> <span> [<a href="https://arxiv.org/pdf/2211.04264">pdf</a>, <a href="https://arxiv.org/ps/2211.04264">ps</a>, <a href="https://arxiv.org/format/2211.04264">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"> Note on generalized group testing </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</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="2211.04264v1-abstract-short" style="display: inline;"> In this note, we present a new adaptive algorithm for generalized group testing, which is asymptotically optimal if $d=o(\log_2|E|)$, $E$ is a set of potentially contaminated sets, $d$ is a maximal size of elements of $E$. Also, we design a 3-stage algorithm, which is asymptotically optimal for $d=2$. </span> <span class="abstract-full has-text-grey-dark mathjax" id="2211.04264v1-abstract-full" style="display: none;"> In this note, we present a new adaptive algorithm for generalized group testing, which is asymptotically optimal if $d=o(\log_2|E|)$, $E$ is a set of potentially contaminated sets, $d$ is a maximal size of elements of $E$. Also, we design a 3-stage algorithm, which is asymptotically optimal for $d=2$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2211.04264v1-abstract-full').style.display = 'none'; document.getElementById('2211.04264v1-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 November, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2022. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2202.00136">arXiv:2202.00136</a> <span> [<a href="https://arxiv.org/pdf/2202.00136">pdf</a>, <a href="https://arxiv.org/ps/2202.00136">ps</a>, <a href="https://arxiv.org/format/2202.00136">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"> Non-adaptive and two-stage coding over the Z-channel </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Lebedev%2C+A">Alexey Lebedev</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</a>, <a href="/search/cs?searchtype=author&query=Lebedev%2C+V">Vladimir Lebedev</a>, <a href="/search/cs?searchtype=author&query=Deppe%2C+C">Christian Deppe</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="2202.00136v2-abstract-short" style="display: inline;"> In this paper, we developed new coding strategies for the Z-channel. In particular, we look at the case with two-stage encoding. In this case, the encoder uses noiseless feedback once and adjusts the further encoding strategy based on the previous partial output of the channel. Nevertheless, the developed codes improve the known results with full feedback for small length and 1 error. A tool for t… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2202.00136v2-abstract-full').style.display = 'inline'; document.getElementById('2202.00136v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2202.00136v2-abstract-full" style="display: none;"> In this paper, we developed new coding strategies for the Z-channel. In particular, we look at the case with two-stage encoding. In this case, the encoder uses noiseless feedback once and adjusts the further encoding strategy based on the previous partial output of the channel. Nevertheless, the developed codes improve the known results with full feedback for small length and 1 error. A tool for the two-stage strategy is the development of a new optimality condition for non-adaptive codes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2202.00136v2-abstract-full').style.display = 'none'; document.getElementById('2202.00136v2-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 September, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 31 January, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 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">Some references and known results, which were missed in the previous version, have been added</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2110.02008">arXiv:2110.02008</a> <span> [<a href="https://arxiv.org/pdf/2110.02008">pdf</a>, <a href="https://arxiv.org/ps/2110.02008">ps</a>, <a href="https://arxiv.org/format/2110.02008">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"> Lifted Reed-Solomon Codes and Lifted Multiplicity Codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Holzbaur%2C+L">Lukas Holzbaur</a>, <a href="/search/cs?searchtype=author&query=Polyanskaya%2C+R">Rina Polyanskaya</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N">Nikita Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</a>, <a href="/search/cs?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="2110.02008v2-abstract-short" style="display: inline;"> Lifted Reed-Solomon and multiplicity codes are classes of codes, constructed from specific sets of $m$-variate polynomials. These codes allow for the design of high-rate codes that can recover every codeword or information symbol from many disjoint sets. Recently, the underlying approaches have been combined for the bi-variate case to construct lifted multiplicity codes, a generalization of lifted… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2110.02008v2-abstract-full').style.display = 'inline'; document.getElementById('2110.02008v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2110.02008v2-abstract-full" style="display: none;"> Lifted Reed-Solomon and multiplicity codes are classes of codes, constructed from specific sets of $m$-variate polynomials. These codes allow for the design of high-rate codes that can recover every codeword or information symbol from many disjoint sets. Recently, the underlying approaches have been combined for the bi-variate case to construct lifted multiplicity codes, a generalization of lifted codes that can offer further rate improvements. We continue the study of these codes by first establishing new lower bounds on the rate of lifted Reed-Solomon codes for any number of variables $m$, which improve upon the known bounds for any $m\ge 4$. Next, we use these results to provide lower bounds on the rate and distance of lifted multiplicity codes obtained from polynomials in an arbitrary number of variables, which improve upon the known results for any $m\ge 3$. Specifically, we investigate a subcode of a lifted multiplicity code formed by the linear span of $m$-variate monomials whose restriction to an arbitrary line in $\mathbb{F}_q^m$ is equivalent to a low-degree univariate polynomial. We find the tight asymptotic behavior of the fraction of such monomials when the number of variables $m$ is fixed and the alphabet size $q=2^\ell$ is large. Using these results, we give a new explicit construction of batch codes utilizing lifted Reed-Solomon codes. For some parameter regimes, these codes have a better trade-off between parameters than previously known batch codes. Further, we show that lifted multiplicity codes have a better trade-off between redundancy and the number of disjoint recovering sets for every codeword or information symbol than previously known constructions, thereby providing the best known PIR codes for some parameter regimes. Additionally, we present a new local self-correction algorithm for lifted multiplicity codes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2110.02008v2-abstract-full').style.display = 'none'; document.getElementById('2110.02008v2-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> 11 October, 2021; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 5 October, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2021. </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">The results on lifted RS codes have partially been presented at the IEEE International Symposium on Information Theory (ISIT) 2020 (arXiv:2001.11981) and parts of the results on lifted multiplicity codes have been presented at the IEEE Information Theory Workshop (ITW) 2020 (arXiv:2008.04717)</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2108.13359">arXiv:2108.13359</a> <span> [<a href="https://arxiv.org/pdf/2108.13359">pdf</a>, <a href="https://arxiv.org/ps/2108.13359">ps</a>, <a href="https://arxiv.org/format/2108.13359">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"> Fast Decoding of Union-free Codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</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="2108.13359v2-abstract-short" style="display: inline;"> Union-free codes and disjunctive codes are two combinatorial structures, which are used in nonadaptive group testing to find a set of $d$ defective elements among $n$ samples by carrying out the minimal number of tests $t$. It is known that union-free codes have a larger rate, whereas disjunctive codes provide a more efficient decoding algorithm. In this paper we introduce a new family of codes fo… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2108.13359v2-abstract-full').style.display = 'inline'; document.getElementById('2108.13359v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2108.13359v2-abstract-full" style="display: none;"> Union-free codes and disjunctive codes are two combinatorial structures, which are used in nonadaptive group testing to find a set of $d$ defective elements among $n$ samples by carrying out the minimal number of tests $t$. It is known that union-free codes have a larger rate, whereas disjunctive codes provide a more efficient decoding algorithm. In this paper we introduce a new family of codes for nonadaptive group testing with fast decoding. The rate of these codes is larger than the rate of disjunctive codes, while the decoding algorithm has the same complexity. In addition, we derive a lower bound on the rate of new codes for the case of $d=2$ defectives, which is significantly better than the bound for disjunctive codes and almost as good as the bound for union-free codes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2108.13359v2-abstract-full').style.display = 'none'; document.getElementById('2108.13359v2-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 January, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 30 August, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 2021. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2108.09015">arXiv:2108.09015</a> <span> [<a href="https://arxiv.org/pdf/2108.09015">pdf</a>, <a href="https://arxiv.org/ps/2108.09015">ps</a>, <a href="https://arxiv.org/format/2108.09015">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"> Complete Traceability Multimedia Fingerprinting Codes Resistant to Averaging Attack and Adversarial Noise with Optimal Rate </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</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="2108.09015v4-abstract-short" style="display: inline;"> In this paper we consider complete traceability multimedia fingerprinting codes resistant to averaging attacks and adversarial noise. Recently it was shown that there are no such codes for the case of an arbitrary linear attack. However, for the case of averaging attacks complete traceability multimedia fingerprinting codes of exponential cardinality resistant to constant adversarial noise were co… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2108.09015v4-abstract-full').style.display = 'inline'; document.getElementById('2108.09015v4-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2108.09015v4-abstract-full" style="display: none;"> In this paper we consider complete traceability multimedia fingerprinting codes resistant to averaging attacks and adversarial noise. Recently it was shown that there are no such codes for the case of an arbitrary linear attack. However, for the case of averaging attacks complete traceability multimedia fingerprinting codes of exponential cardinality resistant to constant adversarial noise were constructed in 2020 by Egorova et al. We continue this work and provide an improved lower bound on the rate of these codes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2108.09015v4-abstract-full').style.display = 'none'; document.getElementById('2108.09015v4-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 August, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 20 August, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 2021. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2105.02298">arXiv:2105.02298</a> <span> [<a href="https://arxiv.org/pdf/2105.02298">pdf</a>, <a href="https://arxiv.org/ps/2105.02298">ps</a>, <a href="https://arxiv.org/format/2105.02298">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 Localized Deletions </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bitar%2C+R">Rawad Bitar</a>, <a href="/search/cs?searchtype=author&query=Hanna%2C+S+K">Serge Kas Hanna</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N">Nikita Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</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="2105.02298v1-abstract-short" style="display: inline;"> We consider the problem of constructing codes that can correct deletions that are localized within a certain part of the codeword that is unknown a priori. Namely, the model that we study is when at most $k$ deletions occur in a window of size $k$, where the positions of the deletions within this window are not necessarily consecutive. Localized deletions are thus a generalization of burst deletio… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2105.02298v1-abstract-full').style.display = 'inline'; document.getElementById('2105.02298v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2105.02298v1-abstract-full" style="display: none;"> We consider the problem of constructing codes that can correct deletions that are localized within a certain part of the codeword that is unknown a priori. Namely, the model that we study is when at most $k$ deletions occur in a window of size $k$, where the positions of the deletions within this window are not necessarily consecutive. Localized deletions are thus a generalization of burst deletions that occur in consecutive positions. We present novel explicit codes that are efficiently encodable and decodable and can correct up to $k$ localized deletions. Furthermore, these codes have $\log n+\mathcal{O}(k \log^2 (k\log n))$ redundancy, where $n$ is the length of the information message, which is asymptotically optimal in $n$ for $k=o(\log n/(\log \log n)^2)$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2105.02298v1-abstract-full').style.display = 'none'; document.getElementById('2105.02298v1-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, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2021. </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">10 pages, a full version of the paper accepted to 2021 IEEE 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/2010.15928">arXiv:2010.15928</a> <span> [<a href="https://arxiv.org/pdf/2010.15928">pdf</a>, <a href="https://arxiv.org/ps/2010.15928">ps</a>, <a href="https://arxiv.org/format/2010.15928">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> </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.1134/S0032946021030029">10.1134/S0032946021030029 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Feedback Insertion-Deletion Codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Maringer%2C+G">Georg Maringer</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N">Nikita Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</a>, <a href="/search/cs?searchtype=author&query=Welter%2C+L">Lorenz Welter</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="2010.15928v3-abstract-short" style="display: inline;"> In this paper, a new problem of transmitting information over the adversarial insertion-deletion channel with feedback is introduced. Suppose that the encoder transmits $n$ binary symbols one-by-one over a channel, in which some symbols can be deleted and some additional symbols can be inserted. After each transmission, the encoder is notified about the insertions or deletions that have occurred w… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2010.15928v3-abstract-full').style.display = 'inline'; document.getElementById('2010.15928v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2010.15928v3-abstract-full" style="display: none;"> In this paper, a new problem of transmitting information over the adversarial insertion-deletion channel with feedback is introduced. Suppose that the encoder transmits $n$ binary symbols one-by-one over a channel, in which some symbols can be deleted and some additional symbols can be inserted. After each transmission, the encoder is notified about the insertions or deletions that have occurred within the previous transmission and the encoding strategy can be adapted accordingly. The goal is to design an encoder that is able to transmit error-free as much information as possible under the assumption that the total number of deletions and insertions is limited by $蟿n$, $0<蟿<1$. We show how this problem can be reduced to the problem of transmitting messages over the substitution channel. Thereby, the maximal asymptotic rate of feedback insertion-deletion codes is completely established. The maximal asymptotic rate for the adversarial substitution channel has been partially determined by Berlekamp and later finished by Zigangirov. However, the analysis of the lower bound by Zigangirov is quite complicated. We revisit Zigangirov's result and present a more elaborate version of his proof. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2010.15928v3-abstract-full').style.display = 'none'; document.getElementById('2010.15928v3-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 January, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 29 October, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2020. </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, 8 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2008.04717">arXiv:2008.04717</a> <span> [<a href="https://arxiv.org/pdf/2008.04717">pdf</a>, <a href="https://arxiv.org/ps/2008.04717">ps</a>, <a href="https://arxiv.org/format/2008.04717">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> </div> </div> <p class="title is-5 mathjax"> Lifted Multiplicity Codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Holzbaur%2C+L">Lukas Holzbaur</a>, <a href="/search/cs?searchtype=author&query=Polyanskaya%2C+R">Rina Polyanskaya</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N">Nikita Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</a>, <a href="/search/cs?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="2008.04717v2-abstract-short" style="display: inline;"> Lifted Reed-Solomon codes and multiplicity codes are two classes of evaluation codes that allow for the design of high-rate codes that can recover every codeword or information symbol from many disjoint sets. Recently, the underlying approaches have been combined to construct lifted bi-variate multiplicity codes, that can further improve on the rate. We continue the study of these codes by providi… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2008.04717v2-abstract-full').style.display = 'inline'; document.getElementById('2008.04717v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2008.04717v2-abstract-full" style="display: none;"> Lifted Reed-Solomon codes and multiplicity codes are two classes of evaluation codes that allow for the design of high-rate codes that can recover every codeword or information symbol from many disjoint sets. Recently, the underlying approaches have been combined to construct lifted bi-variate multiplicity codes, that can further improve on the rate. We continue the study of these codes by providing lower bounds on the rate and distance for lifted multiplicity codes obtained from polynomials in an arbitrary number of variables. Specifically, we investigate a subcode of a lifted multiplicity code formed by the linear span of $m$-variate monomials whose restriction to an arbitrary line in $\mathbb{F}_q^m$ is equivalent to a low-degree uni-variate polynomial. We find the tight asymptotic behavior of the fraction of such monomials when the number of variables $m$ is fixed and the alphabet size $q=2^\ell$ is large. For some parameter regimes, lifted multiplicity codes are then shown to have a better trade-off between redundancy and the number of disjoint recovering sets for every codeword or information symbol than previously known constructions. Additionally, we present a local self-correction algorithm for lifted multiplicity codes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2008.04717v2-abstract-full').style.display = 'none'; document.getElementById('2008.04717v2-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 October, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 11 August, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 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.01792">arXiv:2007.01792</a> <span> [<a href="https://arxiv.org/pdf/2007.01792">pdf</a>, <a href="https://arxiv.org/ps/2007.01792">ps</a>, <a href="https://arxiv.org/format/2007.01792">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> <span class="tag is-small is-grey 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.1016/j.ffa.2021.101879">10.1016/j.ffa.2021.101879 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Almost Affinely Disjoint Subspaces </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Liu%2C+H">Hedongliang Liu</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N">Nikita Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</a>, <a href="/search/cs?searchtype=author&query=Wachter-Zeh%2C+A">Antonia Wachter-Zeh</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.01792v2-abstract-short" style="display: inline;"> In this work, we introduce a natural notion concerning finite vector spaces. A family of $k$-dimensional subspaces of $\mathbb{F}_q^n$, which forms a partial spread, is called almost affinely disjoint if any $(k+1)$-dimensional subspace containing a subspace from the family non-trivially intersects with only a few subspaces from the family. The central question discussed in the paper is the polyno… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2007.01792v2-abstract-full').style.display = 'inline'; document.getElementById('2007.01792v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2007.01792v2-abstract-full" style="display: none;"> In this work, we introduce a natural notion concerning finite vector spaces. A family of $k$-dimensional subspaces of $\mathbb{F}_q^n$, which forms a partial spread, is called almost affinely disjoint if any $(k+1)$-dimensional subspace containing a subspace from the family non-trivially intersects with only a few subspaces from the family. The central question discussed in the paper is the polynomial growth (in $q$) of the maximal cardinality of these families given the parameters $k$ and $n$. For the cases $k=1$ and $k=2$, optimal families are constructed. For other settings, we find lower and upper bounds on the polynomial growth. Additionally, some connections with problems in coding theory are shown. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2007.01792v2-abstract-full').style.display = 'none'; document.getElementById('2007.01792v2-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 June, 2021; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 3 July, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2020. </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">10 pages; Published in Finite Fields and Their Applications, Volume 75, October 2021, 101879</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Finite Fields and Their Applications, Volume 75, October 2021, 101879 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2001.11981">arXiv:2001.11981</a> <span> [<a href="https://arxiv.org/pdf/2001.11981">pdf</a>, <a href="https://arxiv.org/ps/2001.11981">ps</a>, <a href="https://arxiv.org/format/2001.11981">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"> Lifted Reed-Solomon Codes with Application to Batch Codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Holzbaur%2C+L">Lukas Holzbaur</a>, <a href="/search/cs?searchtype=author&query=Polyanskaya%2C+R">Rina Polyanskaya</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N">Nikita Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</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.11981v2-abstract-short" style="display: inline;"> Guo, Kopparty and Sudan have initiated the study of error-correcting codes derived by lifting of affine-invariant codes. Lifted Reed-Solomon (RS) codes are defined as the evaluation of polynomials in a vector space over a field by requiring their restriction to every line in the space to be a codeword of the RS code. In this paper, we investigate lifted RS codes and discuss their application to ba… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2001.11981v2-abstract-full').style.display = 'inline'; document.getElementById('2001.11981v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2001.11981v2-abstract-full" style="display: none;"> Guo, Kopparty and Sudan have initiated the study of error-correcting codes derived by lifting of affine-invariant codes. Lifted Reed-Solomon (RS) codes are defined as the evaluation of polynomials in a vector space over a field by requiring their restriction to every line in the space to be a codeword of the RS code. In this paper, we investigate lifted RS codes and discuss their application to batch codes, a notion introduced in the context of private information retrieval and load-balancing in distributed storage systems. First, we improve the estimate of the code rate of lifted RS codes for lifting parameter $m\ge 3$ and large field size. Second, a new explicit construction of batch codes utilizing lifted RS codes is proposed. For some parameter regimes, our codes have a better trade-off between parameters than previously known batch codes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2001.11981v2-abstract-full').style.display = 'none'; document.getElementById('2001.11981v2-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 February, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 31 January, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2020. </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">7 pages, 1 figure, a short version was submitted to ISIT 2020</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2001.08005">arXiv:2001.08005</a> <span> [<a href="https://arxiv.org/pdf/2001.08005">pdf</a>, <a href="https://arxiv.org/ps/2001.08005">ps</a>, <a href="https://arxiv.org/format/2001.08005">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"> Optimal Multistage Group Testing Algorithm for 3 Defectives </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</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.08005v2-abstract-short" style="display: inline;"> Group testing is a well-known search problem that consists in detecting of $s$ defective members of a set of $t$ samples by carrying out tests on properly chosen subsets of samples. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests in the worst case. In this work, a multistage group testing problem is considered. Our goal is to cons… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2001.08005v2-abstract-full').style.display = 'inline'; document.getElementById('2001.08005v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2001.08005v2-abstract-full" style="display: none;"> Group testing is a well-known search problem that consists in detecting of $s$ defective members of a set of $t$ samples by carrying out tests on properly chosen subsets of samples. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests in the worst case. In this work, a multistage group testing problem is considered. Our goal is to construct a multistage search procedure, having asymptotically the same number of tests as the optimal adaptive algorithm. We propose a new approach to designing multistage algorithms, which allows us to construct a 5-stage algorithm for finding 3 defectives with the optimal number $3\log_2t(1+o(1))$ of tests. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2001.08005v2-abstract-full').style.display = 'none'; document.getElementById('2001.08005v2-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 May, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 22 January, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2020. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 68R05 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2001.06242">arXiv:2001.06242</a> <span> [<a href="https://arxiv.org/pdf/2001.06242">pdf</a>, <a href="https://arxiv.org/ps/2001.06242">ps</a>, <a href="https://arxiv.org/format/2001.06242">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"> Duplication with transposition distance to the root for $q$-ary strings </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N">Nikita Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</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.06242v1-abstract-short" style="display: inline;"> We study the duplication with transposition distance between strings of length $n$ over a $q$-ary alphabet and their roots. In other words, we investigate the number of duplication operations of the form $x = (abcd) \to y = (abcbd)$, where $x$ and $y$ are strings and $a$, $b$, $c$ and $d$ are their substrings, needed to get a $q$-ary string of length $n$ starting from the set of strings without du… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2001.06242v1-abstract-full').style.display = 'inline'; document.getElementById('2001.06242v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2001.06242v1-abstract-full" style="display: none;"> We study the duplication with transposition distance between strings of length $n$ over a $q$-ary alphabet and their roots. In other words, we investigate the number of duplication operations of the form $x = (abcd) \to y = (abcbd)$, where $x$ and $y$ are strings and $a$, $b$, $c$ and $d$ are their substrings, needed to get a $q$-ary string of length $n$ starting from the set of strings without duplications. For exact duplication, we prove that the maximal distance between a string of length at most $n$ and its root has the asymptotic order $n/\log n$. For approximate duplication, where a $尾$-fraction of symbols may be duplicated incorrectly, we show that the maximal distance has a sharp transition from the order $n/\log n$ to $\log n$ at $尾=(q-1)/q$. The motivation for this problem comes from genomics, where such duplications represent a special kind of mutation and the distance between a given biological sequence and its root is the smallest number of transposition mutations required to generate the sequence. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2001.06242v1-abstract-full').style.display = 'none'; document.getElementById('2001.06242v1-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 January, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2020. </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">6 pages, 1 table, submitted to International Symposium on Information Theory (ISIT) 2020</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1901.06741">arXiv:1901.06741</a> <span> [<a href="https://arxiv.org/pdf/1901.06741">pdf</a>, <a href="https://arxiv.org/ps/1901.06741">ps</a>, <a href="https://arxiv.org/format/1901.06741">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"> Constructions of Batch Codes via Finite Geometry </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N">Nikita Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</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.06741v1-abstract-short" style="display: inline;"> A primitive $k$-batch code encodes a string $x$ of length $n$ into string $y$ of length $N$, such that each multiset of $k$ symbols from $x$ has $k$ mutually disjoint recovering sets from $y$. We develop new explicit and random coding constructions of linear primitive batch codes based on finite geometry. In some parameter regimes, our proposed codes have lower redundancy than previously known bat… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1901.06741v1-abstract-full').style.display = 'inline'; document.getElementById('1901.06741v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1901.06741v1-abstract-full" style="display: none;"> A primitive $k$-batch code encodes a string $x$ of length $n$ into string $y$ of length $N$, such that each multiset of $k$ symbols from $x$ has $k$ mutually disjoint recovering sets from $y$. We develop new explicit and random coding constructions of linear primitive batch codes based on finite geometry. In some parameter regimes, our proposed codes have lower redundancy than previously known batch codes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1901.06741v1-abstract-full').style.display = 'none'; document.getElementById('1901.06741v1-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> 20 January, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 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">7 pages, 1 figure, 1 table</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1901.06740">arXiv:1901.06740</a> <span> [<a href="https://arxiv.org/pdf/1901.06740">pdf</a>, <a href="https://arxiv.org/ps/1901.06740">ps</a>, <a href="https://arxiv.org/format/1901.06740">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"> A New Algorithm for Two-Stage Group Testing </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</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.06740v2-abstract-short" style="display: inline;"> Group testing is a well-known search problem that consists in detecting of $s$ defective members of a set of $t$ samples by carrying out tests on properly chosen subsets of samples. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests in the worst case. In this work, two-stage group testing is considered. Using the hypergraph approach… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1901.06740v2-abstract-full').style.display = 'inline'; document.getElementById('1901.06740v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1901.06740v2-abstract-full" style="display: none;"> Group testing is a well-known search problem that consists in detecting of $s$ defective members of a set of $t$ samples by carrying out tests on properly chosen subsets of samples. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests in the worst case. In this work, two-stage group testing is considered. Using the hypergraph approach we design a new search algorithm, which allows improving the known results for fixed $s$ and $t\to\infty$. For the case $s=2$ this algorithm achieves information-theoretic lower bound $2\log_2t(1+o(1))$ on the number of tests in the worst case. Also, the problem of finding $m$ out of $s$ defectives is considered. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1901.06740v2-abstract-full').style.display = 'none'; document.getElementById('1901.06740v2-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 April, 2019; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 20 January, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 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">7 pages, 1 table</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1804.08599">arXiv:1804.08599</a> <span> [<a href="https://arxiv.org/pdf/1804.08599">pdf</a>, <a href="https://arxiv.org/ps/1804.08599">ps</a>, <a href="https://arxiv.org/format/1804.08599">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.2889250">10.1109/TIT.2018.2889250 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> On capacities of the two-user union channel with complete feedback </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Jiang%2C+Z">Zilin Jiang</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N">Nikita Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</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="1804.08599v2-abstract-short" style="display: inline;"> The exact values of the optimal symmetric rate point in the Cover--Leung capacity region of the two-user union channel with complete feedback were determined by Willems when the size of the input alphabet is 2, and by Vinck, Hoeks and Post when the size is at least 6. We complete this line of research when the size of the input alphabet is 3, 4 or 5. The proof hinges on the technical lemma that co… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1804.08599v2-abstract-full').style.display = 'inline'; document.getElementById('1804.08599v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1804.08599v2-abstract-full" style="display: none;"> The exact values of the optimal symmetric rate point in the Cover--Leung capacity region of the two-user union channel with complete feedback were determined by Willems when the size of the input alphabet is 2, and by Vinck, Hoeks and Post when the size is at least 6. We complete this line of research when the size of the input alphabet is 3, 4 or 5. The proof hinges on the technical lemma that concerns the maximal joint entropy of two independent random variables in terms of their probability of equality. For the zero-error capacity region, using superposition coding, we provide a practical near-optimal communication scheme which improves all the previous explicit constructions. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1804.08599v2-abstract-full').style.display = 'none'; document.getElementById('1804.08599v2-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 December, 2018; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 23 April, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2018. </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">16 pages, 1 figure, 1 table, accepted to IEEE Trans. Inf. Theory, corrections suggested by the referees have been incorporated</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 94A40; 94A24; 94A17 </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, vol. 65, no. 5, pp. 2774-2781, May 2019 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1701.07521">arXiv:1701.07521</a> <span> [<a href="https://arxiv.org/pdf/1701.07521">pdf</a>, <a href="https://arxiv.org/format/1701.07521">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"> Floor Scale Modulo Lifting for QC-LDPC codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N">Nikita Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Usatyuk%2C+V">Vasiliy Usatyuk</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</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.07521v2-abstract-short" style="display: inline;"> In the given paper we present a novel approach for constructing a QC-LDPC code of smaller length by lifting a given QC-LDPC code. The proposed method can be considered as a generalization of floor lifting. Also we prove several probabilistic statements concerning a theoretical improvement of the method with respect to the number of small cycles. Making some offline calculation of scale parameter i… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1701.07521v2-abstract-full').style.display = 'inline'; document.getElementById('1701.07521v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1701.07521v2-abstract-full" style="display: none;"> In the given paper we present a novel approach for constructing a QC-LDPC code of smaller length by lifting a given QC-LDPC code. The proposed method can be considered as a generalization of floor lifting. Also we prove several probabilistic statements concerning a theoretical improvement of the method with respect to the number of small cycles. Making some offline calculation of scale parameter it is possible to construct a sequence of QC-LDPC codes with different circulant sizes generated from a single exponent matrix using only floor and scale operations. The only parameter we store in memory is a constant needed for scaling. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1701.07521v2-abstract-full').style.display = 'none'; document.getElementById('1701.07521v2-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 February, 2017; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 25 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">7 pages, 2 columns</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.06201">arXiv:1701.06201</a> <span> [<a href="https://arxiv.org/pdf/1701.06201">pdf</a>, <a href="https://arxiv.org/format/1701.06201">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"> Hypothesis Test for Bounds on the Size of Random Defective Set </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=D%27yachkov%2C+A+G">A. G. D'yachkov</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N+A">N. A. Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Shchukin%2C+V+Y">V. Yu. Shchukin</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I+V">I. V. Vorobyev</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.06201v3-abstract-short" style="display: inline;"> The conventional model of disjunctive group testing assumes that there are several defective elements (or defectives) among a large population, and a group test yields the positive response if and only if the testing group contains at least one defective element. The basic problem is to find all defectives using a minimal possible number of group tests. However, when the number of defectives is un… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1701.06201v3-abstract-full').style.display = 'inline'; document.getElementById('1701.06201v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1701.06201v3-abstract-full" style="display: none;"> The conventional model of disjunctive group testing assumes that there are several defective elements (or defectives) among a large population, and a group test yields the positive response if and only if the testing group contains at least one defective element. The basic problem is to find all defectives using a minimal possible number of group tests. However, when the number of defectives is unknown there arises an additional problem, namely: how to estimate the random number of defective elements. n this paper, we concentrate on testing the hypothesis $H_0$: the number of defectives $\le s_1$ against the alternative hypothesis $H_1$: the number of defectives $\ge s_2$. We introduce a new decoding algorithm based on the comparison of the number of tests having positive responses with an appropriate fixed threshold. For some asymptotic regimes on $s_1$ and $s_2$, the proposed algorithm is shown to be order-optimal. Additionally, our simulation results verify the advantages of the proposed algorithm such as low complexity and a small error probability compared with known algorithms. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1701.06201v3-abstract-full').style.display = 'none'; document.getElementById('1701.06201v3-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 August, 2019; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 22 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">10 pages, 3 figures</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.06085">arXiv:1701.06085</a> <span> [<a href="https://arxiv.org/pdf/1701.06085">pdf</a>, <a href="https://arxiv.org/format/1701.06085">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"> Separable Codes for the Symmetric Multiple-Access Channel </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Dyachkov%2C+A+G">A. G. Dyachkov</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N">N. Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Shchukin%2C+V">V. Shchukin</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">I. Vorobyev</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.06085v5-abstract-short" style="display: inline;"> A binary matrix is called an s-separable code for the disjunctive multiple-access channel (disj-MAC) if Boolean sums of sets of s columns are all distinct. The well-known issue of the combinatorial coding theory is to obtain upper and lower bounds on the rate of s-separable codes for disj-MAC. In our paper, we generalize the problem and discuss upper and lower bounds on the rate of q-ary s-separab… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1701.06085v5-abstract-full').style.display = 'inline'; document.getElementById('1701.06085v5-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1701.06085v5-abstract-full" style="display: none;"> A binary matrix is called an s-separable code for the disjunctive multiple-access channel (disj-MAC) if Boolean sums of sets of s columns are all distinct. The well-known issue of the combinatorial coding theory is to obtain upper and lower bounds on the rate of s-separable codes for disj-MAC. In our paper, we generalize the problem and discuss upper and lower bounds on the rate of q-ary s-separable codes for models of noiseless symmetric MAC, i.e., when at each time instant the output signal of MAC is a symmetric function of its s input signals. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1701.06085v5-abstract-full').style.display = 'none'; document.getElementById('1701.06085v5-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 August, 2018; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 21 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">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/1607.00511">arXiv:1607.00511</a> <span> [<a href="https://arxiv.org/pdf/1607.00511">pdf</a>, <a href="https://arxiv.org/ps/1607.00511">ps</a>, <a href="https://arxiv.org/format/1607.00511">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"> On a Hypergraph Approach to Multistage Group Testing Problems </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=D%27yachkov%2C+A+G">A. G. D'yachkov</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I+V">I. V. Vorobyev</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N+A">N. A. Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Shchukin%2C+V+Y">V. Yu. Shchukin</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.00511v1-abstract-short" style="display: inline;"> Group testing is a well known search problem that consists in detecting up to $s$ defective elements of the set $[t]=\{1,\ldots,t\}$ by carrying out tests on properly chosen subsets of $[t]$. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests. In this paper we consider multistage group testing. We propose a general idea how to use a… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1607.00511v1-abstract-full').style.display = 'inline'; document.getElementById('1607.00511v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1607.00511v1-abstract-full" style="display: none;"> Group testing is a well known search problem that consists in detecting up to $s$ defective elements of the set $[t]=\{1,\ldots,t\}$ by carrying out tests on properly chosen subsets of $[t]$. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests. In this paper we consider multistage group testing. We propose a general idea how to use a hypergraph approach to searching defects. For the case $s=2$, we design an explicit construction, which makes use of $2\log_2t(1+o(1))$ tests in the worst case and consists of $4$ stages. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1607.00511v1-abstract-full').style.display = 'none'; document.getElementById('1607.00511v1-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 July, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 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">ACCT 2016, 6 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/1607.00507">arXiv:1607.00507</a> <span> [<a href="https://arxiv.org/pdf/1607.00507">pdf</a>, <a href="https://arxiv.org/ps/1607.00507">ps</a>, <a href="https://arxiv.org/format/1607.00507">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="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Adaptive Learning a Hidden Hypergraph </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=D%27yachkov%2C+A+G">A. G. D'yachkov</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I+V">I. V. Vorobyev</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N+A">N. A. Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Shchukin%2C+V+Y">V. Yu. Shchukin</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.00507v1-abstract-short" style="display: inline;"> Learning a hidden hypergraph is a natural generalization of the classical group testing problem that consists in detecting unknown hypergraph $H_{un}=H(V,E)$ by carrying out edge-detecting tests. In the given paper we focus our attention only on a specific family $\mathcal{F}(t,s,\ell)$ of localized hypergraphs for which the total number of vertices $|V| = t$, the number of edges $|E|\le s$,… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1607.00507v1-abstract-full').style.display = 'inline'; document.getElementById('1607.00507v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1607.00507v1-abstract-full" style="display: none;"> Learning a hidden hypergraph is a natural generalization of the classical group testing problem that consists in detecting unknown hypergraph $H_{un}=H(V,E)$ by carrying out edge-detecting tests. In the given paper we focus our attention only on a specific family $\mathcal{F}(t,s,\ell)$ of localized hypergraphs for which the total number of vertices $|V| = t$, the number of edges $|E|\le s$, $s\ll t$, and the cardinality of any edge $|e|\le\ell$, $\ell\ll t$. Our goal is to identify all edges of $H_{un}\in \mathcal{F}(t,s,\ell)$ by using the minimal number of tests. We provide an adaptive algorithm that matches the information theory bound, i.e., the total number of tests of the algorithm in the worst case is at most $s\ell\log_2 t(1+o(1))$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1607.00507v1-abstract-full').style.display = 'none'; document.getElementById('1607.00507v1-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 July, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 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">ACCT 2016, 6 pages. arXiv admin note: text overlap with arXiv:1601.06705</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1607.00502">arXiv:1607.00502</a> <span> [<a href="https://arxiv.org/pdf/1607.00502">pdf</a>, <a href="https://arxiv.org/ps/1607.00502">ps</a>, <a href="https://arxiv.org/format/1607.00502">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"> Threshold Decoding for Disjunctive Group Testing </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=D%27yachkov%2C+A+G">A. G. D'yachkov</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I+V">I. V. Vorobyev</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N+A">N. A. Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Shchukin%2C+V+Y">V. Yu. Shchukin</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.00502v1-abstract-short" style="display: inline;"> Let $1 \le s < t$, $N \ge 1$ be integers and a complex electronic circuit of size $t$ is said to be an $s$-active, $\; s \ll t$, and can work as a system block if not more than $s$ elements of the circuit are defective. Otherwise, the circuit is said to be an $s$-defective and should be replaced by a similar $s$-active circuit. Suppose that there exists a possibility to run $N$ non-adaptive group… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1607.00502v1-abstract-full').style.display = 'inline'; document.getElementById('1607.00502v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1607.00502v1-abstract-full" style="display: none;"> Let $1 \le s < t$, $N \ge 1$ be integers and a complex electronic circuit of size $t$ is said to be an $s$-active, $\; s \ll t$, and can work as a system block if not more than $s$ elements of the circuit are defective. Otherwise, the circuit is said to be an $s$-defective and should be replaced by a similar $s$-active circuit. Suppose that there exists a possibility to run $N$ non-adaptive group tests to check the $s$-activity of the circuit. As usual, we say that a (disjunctive) group test yields the positive response if the group contains at least one defective element. Along with the conventional decoding algorithm based on disjunctive $s$-codes, we consider a threshold decision rule with the minimal possible decoding complexity, which is based on the simple comparison of a fixed threshold $T$, $1 \le T \le N - 1$, with the number of positive responses $p$, $0 \le p \le N$. For the both of decoding algorithms we discuss upper bounds on the $伪$-level of significance of the statistical test for the null hypothesis $\left\{ H_0 \,:\, \text{the circuit is $s$-active} \right\}$ verse the alternative hypothesis $\left\{ H_1 \,:\, \text{the circuit is $s$-defective} \right\}$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1607.00502v1-abstract-full').style.display = 'none'; document.getElementById('1607.00502v1-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 July, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 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">ACCT 2016, 6 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/1605.06847">arXiv:1605.06847</a> <span> [<a href="https://arxiv.org/pdf/1605.06847">pdf</a>, <a href="https://arxiv.org/ps/1605.06847">ps</a>, <a href="https://arxiv.org/format/1605.06847">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"> A simple construction of cover-free $(s,\ell)$-code with certain constant weight </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=D%27yachkov%2C+A+G">A. G. D'yachkov</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I+V">I. V. Vorobyev</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N+A">N. A. Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Shchukin%2C+V+Y">V. Yu. Shchukin</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="1605.06847v1-abstract-short" style="display: inline;"> We give a method of constructing a cover-free $(s, \ell)$-code. For $k > s$, our construction yields a $ {{n \choose s} \choose \ell}\times {n \choose k}$ cover-free $(s, \ell)$-code with a constant column weight. </span> <span class="abstract-full has-text-grey-dark mathjax" id="1605.06847v1-abstract-full" style="display: none;"> We give a method of constructing a cover-free $(s, \ell)$-code. For $k > s$, our construction yields a $ {{n \choose s} \choose \ell}\times {n \choose k}$ cover-free $(s, \ell)$-code with a constant column weight. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1605.06847v1-abstract-full').style.display = 'none'; document.getElementById('1605.06847v1-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 May, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 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">2 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/1605.05363">arXiv:1605.05363</a> <span> [<a href="https://arxiv.org/pdf/1605.05363">pdf</a>, <a href="https://arxiv.org/ps/1605.05363">ps</a>, <a href="https://arxiv.org/format/1605.05363">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 rate of disjunctive codes (in Russian) </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Dyachkov%2C+A+G">A. G. Dyachkov</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N">N. Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Shchukin%2C+V">V. Shchukin</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">I. Vorobyev</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="1605.05363v1-abstract-short" style="display: inline;"> A binary code is called a superimposed cover-free $(s,\ell)$-code if the code is identified by the incidence matrix of a family of finite sets in which no intersection of $\ell$ sets is covered by the union of $s$ others. A binary code is called a superimposed list-decoding $s_L$-code if the code is identified by the incidence matrix of a family of finite sets in which the union of any $s$ sets ca… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1605.05363v1-abstract-full').style.display = 'inline'; document.getElementById('1605.05363v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1605.05363v1-abstract-full" style="display: none;"> A binary code is called a superimposed cover-free $(s,\ell)$-code if the code is identified by the incidence matrix of a family of finite sets in which no intersection of $\ell$ sets is covered by the union of $s$ others. A binary code is called a superimposed list-decoding $s_L$-code if the code is identified by the incidence matrix of a family of finite sets in which the union of any $s$ sets can cover not more than $L-1$ other sets of the family. For $L=\ell=1$, both of the definitions coincide and the corresponding binary code is called a superimposed $s$-code. Our aim is to obtain new lower and upper bounds on the rate of the given codes. In particular, we derive lower bounds on the rates of a superimposed cover-free $(s,\ell)$-code and list-decoding $s_L$-code based on the ensemble of constant weight binary codes. Also, we establish an upper bound on the rate of superimposed list-decoding $s_L$-code. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1605.05363v1-abstract-full').style.display = 'none'; document.getElementById('1605.05363v1-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 May, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 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">36 pages, Original Russian Text published in Problemy Peredachi Informatsii, 2014, Vol. 50, No. 1, pp. 31-63</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1601.06709">arXiv:1601.06709</a> <span> [<a href="https://arxiv.org/pdf/1601.06709">pdf</a>, <a href="https://arxiv.org/ps/1601.06709">ps</a>, <a href="https://arxiv.org/format/1601.06709">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"> Threshold Disjunctive Codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=D%27yachkov%2C+A+G">A. G. D'yachkov</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I+V">I. V. Vorobyev</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N+A">N. A. Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Shchukin%2C+V+Y">V. Yu. Shchukin</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.06709v1-abstract-short" style="display: inline;"> Let $1 \le s < t$, $N \ge 1$ be integers and a complex electronic circuit of size $t$ is said to be an $s$-active, $\; s \ll t$, and can work as a system block if not more than $s$ elements of the circuit are defective. Otherwise, the circuit is said to be an $s$-defective and should be substituted for the similar $s$-active circuit. Suppose that there exists a possibility to check the $s$-activit… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1601.06709v1-abstract-full').style.display = 'inline'; document.getElementById('1601.06709v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1601.06709v1-abstract-full" style="display: none;"> Let $1 \le s < t$, $N \ge 1$ be integers and a complex electronic circuit of size $t$ is said to be an $s$-active, $\; s \ll t$, and can work as a system block if not more than $s$ elements of the circuit are defective. Otherwise, the circuit is said to be an $s$-defective and should be substituted for the similar $s$-active circuit. Suppose that there exists a possibility to check the $s$-activity of the circuit using $N$ non-adaptive group tests identified by a conventional disjunctive $s$-code $X$ of size~$t$ and length~$N$. As usually, we say that any group test yields the positive response if the group contains at least one defective element. In this case, there is no any interest to look for the defective elements. We need to decide on the number of the defective elements in the circuit without knowing the code~$X$. In addition, the decision has the minimal possible complexity because it is based on the simple comparison of a fixed threshold $T$, $0 \le T \le N - 1$, with the number of positive responses $p$, $0 \le p \le N$, obtained after carrying out $N$ non-adaptive tests prescribed by the disjunctive $s$-code~$X$. For the introduced group testing problem, a new class of the well-known disjunctive $s$-codes called the threshold disjunctive $s$-codes is defined. The aim of our paper is to discuss both some constructions of suboptimal threshold disjunctive $s$-codes and the best random coding bounds on the rate of threshold disjunctive $s$-codes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1601.06709v1-abstract-full').style.display = 'none'; document.getElementById('1601.06709v1-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 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">9 pages, IEEE conference</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1601.06705">arXiv:1601.06705</a> <span> [<a href="https://arxiv.org/pdf/1601.06705">pdf</a>, <a href="https://arxiv.org/ps/1601.06705">ps</a>, <a href="https://arxiv.org/format/1601.06705">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/ISIT.2016.7541485">10.1109/ISIT.2016.7541485 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> On Multistage Learning a Hidden Hypergraph </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=D%27yachkov%2C+A+G">A. G. D'yachkov</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I+V">I. V. Vorobyev</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N+A">N. A. Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Shchukin%2C+V+Y">V. Yu. Shchukin</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.06705v3-abstract-short" style="display: inline;"> Learning a hidden hypergraph is a natural generalization of the classical group testing problem that consists in detecting unknown hypergraph $H_{un}=H(V,E)$ by carrying out edge-detecting tests. In the given paper we focus our attention only on a specific family $F(t,s,\ell)$ of localized hypergraphs for which the total number of vertices $|V| = t$, the number of edges $|E|\le s$, $s\ll t$, and t… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1601.06705v3-abstract-full').style.display = 'inline'; document.getElementById('1601.06705v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1601.06705v3-abstract-full" style="display: none;"> Learning a hidden hypergraph is a natural generalization of the classical group testing problem that consists in detecting unknown hypergraph $H_{un}=H(V,E)$ by carrying out edge-detecting tests. In the given paper we focus our attention only on a specific family $F(t,s,\ell)$ of localized hypergraphs for which the total number of vertices $|V| = t$, the number of edges $|E|\le s$, $s\ll t$, and the cardinality of any edge $|e|\le\ell$, $\ell\ll t$. Our goal is to identify all edges of $H_{un}\in F(t,s,\ell)$ by using the minimal number of tests. We develop an adaptive algorithm that matches the information theory bound, i.e., the total number of tests of the algorithm in the worst case is at most $s\ell\log_2 t(1+o(1))$. We also discuss a probabilistic generalization of the problem. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1601.06705v3-abstract-full').style.display = 'none'; document.getElementById('1601.06705v3-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 May, 2016; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 25 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">5 pages, IEEE conference</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1601.06704">arXiv:1601.06704</a> <span> [<a href="https://arxiv.org/pdf/1601.06704">pdf</a>, <a href="https://arxiv.org/ps/1601.06704">ps</a>, <a href="https://arxiv.org/format/1601.06704">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 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/ISIT.2016.7541486">10.1109/ISIT.2016.7541486 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> On a Hypergraph Approach to Multistage Group Testing Problems </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=D%27yachkov%2C+A+G">A. G. D'yachkov</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I+V">I. V. Vorobyev</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N+A">N. A. Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Shchukin%2C+V+Y">V. Yu. Shchukin</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.06704v1-abstract-short" style="display: inline;"> Group testing is a well known search problem that consists in detecting up to $s$ defective elements of the set $[t]=\{1,\ldots,t\}$ by carrying out tests on properly chosen subsets of $[t]$. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests. In this paper we consider multistage group testing. We propose a general idea how to use a… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1601.06704v1-abstract-full').style.display = 'inline'; document.getElementById('1601.06704v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1601.06704v1-abstract-full" style="display: none;"> Group testing is a well known search problem that consists in detecting up to $s$ defective elements of the set $[t]=\{1,\ldots,t\}$ by carrying out tests on properly chosen subsets of $[t]$. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests. In this paper we consider multistage group testing. We propose a general idea how to use a hypergraph approach to searching defects. For the case $s=2$, we design an explicit construction, which makes use of $2\log_2t(1+o(1))$ tests in the worst case and consists of $4$ stages. For the general case $s>2$, we provide an explicit construction, which uses $(2s-1)\log_2t(1+o(1))$ tests and consists of $2s-1$ rounds. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1601.06704v1-abstract-full').style.display = 'none'; document.getElementById('1601.06704v1-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 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">5 pages, IEEE conference</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1410.8566">arXiv:1410.8566</a> <span> [<a href="https://arxiv.org/pdf/1410.8566">pdf</a>, <a href="https://arxiv.org/ps/1410.8566">ps</a>, <a href="https://arxiv.org/format/1410.8566">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"> Almost Cover-Free Codes and Designs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=D%27yachkov%2C+A">Arkadii D'yachkov</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N">Nikita Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Shchukin%2C+V">Vladislav Shchukin</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="1410.8566v5-abstract-short" style="display: inline;"> An $s$-subset of codewords of a binary code $X$ is said to be an {\em $(s,\ell)$-bad} in $X$ if the code $X$ contains a subset of other $\ell$ codewords such that the conjunction of the $\ell$ codewords is covered by the disjunctive sum of the $s$ codewords. Otherwise, the $s$-subset of codewords of $X$ is said to be an {\em $(s,\ell)$-good} in~$X$.mA binary code $X$ is said to be a cover-free… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1410.8566v5-abstract-full').style.display = 'inline'; document.getElementById('1410.8566v5-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1410.8566v5-abstract-full" style="display: none;"> An $s$-subset of codewords of a binary code $X$ is said to be an {\em $(s,\ell)$-bad} in $X$ if the code $X$ contains a subset of other $\ell$ codewords such that the conjunction of the $\ell$ codewords is covered by the disjunctive sum of the $s$ codewords. Otherwise, the $s$-subset of codewords of $X$ is said to be an {\em $(s,\ell)$-good} in~$X$.mA binary code $X$ is said to be a cover-free $(s,\ell)$-code if the code $X$ does not contain $(s,\ell)$-bad subsets. In this paper, we introduce a natural {\em probabilistic} generalization of cover-free $(s,\ell)$-codes, namely: a binary code is said to be an almost cover-free $(s,\ell)$-code if {\em almost all} $s$-subsets of its codewords are $(s,\ell)$-good. We discuss the concept of almost cover-free $(s,\ell)$-codes arising in combinatorial group testing problems connected with the nonadaptive search of defective supersets (complexes). We develop a random coding method based on the ensemble of binary constant weight codes to obtain lower bounds on the capacity of such codes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1410.8566v5-abstract-full').style.display = 'none'; document.getElementById('1410.8566v5-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 March, 2015; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 30 October, 2014; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2014. </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">18 pages, conference paper</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1410.8385">arXiv:1410.8385</a> <span> [<a href="https://arxiv.org/pdf/1410.8385">pdf</a>, <a href="https://arxiv.org/format/1410.8385">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"> Symmetric Disjunctive List-Decoding Codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=D%27yachkov%2C+A">Arkadii D'yachkov</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N">Nikita Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Shchukin%2C+V">Vladislav Shchukin</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="1410.8385v5-abstract-short" style="display: inline;"> A binary code is said to be a disjunctive list-decoding $s_L$-code (LD $s_L$-code), $s \ge 2$, $L \ge 1$, if the code is identified by the incidence matrix of a family of finite sets in which the union (or disjunctive sum) of any $s$ sets can cover not more than $L-1$ other sets of the family. In this paper, we consider a similar class of binary codes which are based on a {\em symmetric disjunctiv… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1410.8385v5-abstract-full').style.display = 'inline'; document.getElementById('1410.8385v5-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1410.8385v5-abstract-full" style="display: none;"> A binary code is said to be a disjunctive list-decoding $s_L$-code (LD $s_L$-code), $s \ge 2$, $L \ge 1$, if the code is identified by the incidence matrix of a family of finite sets in which the union (or disjunctive sum) of any $s$ sets can cover not more than $L-1$ other sets of the family. In this paper, we consider a similar class of binary codes which are based on a {\em symmetric disjunctive sum} (SDS) of binary symbols. By definition, the symmetric disjunctive sum (SDS) takes values from the ternary alphabet $\{0, 1, *\}$, where the symbol~$*$ denotes "erasure". Namely: SDS is equal to $0$ ($1$) if all its binary symbols are equal to $0$ ($1$), otherwise SDS is equal to~$*$. List decoding codes for symmetric disjunctive sum are said to be {\em symmetric disjunctive list-decoding $s_L$-codes} (SLD $s_L$-codes). In the given paper, we remind some applications of SLD $s_L$-codes which motivate the concept of symmetric disjunctive sum. We refine the known relations between parameters of LD $s_L$-codes and SLD $s_L$-codes. For the ensemble of binary constant-weight codes we develop a random coding method to obtain lower bounds on the rate of these codes. Our lower bounds improve the known random coding bounds obtained up to now using the ensemble with independent symbols of codewords. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1410.8385v5-abstract-full').style.display = 'none'; document.getElementById('1410.8385v5-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, 2015; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 30 October, 2014; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2014. </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">18 pages, 1 figure, 1 table, conference paper</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1407.2482">arXiv:1407.2482</a> <span> [<a href="https://arxiv.org/pdf/1407.2482">pdf</a>, <a href="https://arxiv.org/ps/1407.2482">ps</a>, <a href="https://arxiv.org/format/1407.2482">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"> Almost Disjunctive List-Decoding Codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Dyachkov%2C+A+G">A. G. Dyachkov</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I+V">I. V. Vorobyev</a>, <a href="/search/cs?searchtype=author&query=Polyanskii%2C+N+A">N. A. Polyanskii</a>, <a href="/search/cs?searchtype=author&query=Shchukin%2C+V+Y">V. Yu. Shchukin</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="1407.2482v1-abstract-short" style="display: inline;"> A binary code is said to be a disjunctive list-decoding $s_L$-code, $s\ge1$, $L\ge1$, (briefly, LD $s_L$-code) if the code is identified by the incidence matrix of a family of finite sets in which the union of any $s$ sets can cover not more than $L-1$ other sets of the family. In this paper, we introduce a natural {\em probabilistic} generalization of LD $s_L$-code when the code is said to be an… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1407.2482v1-abstract-full').style.display = 'inline'; document.getElementById('1407.2482v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1407.2482v1-abstract-full" style="display: none;"> A binary code is said to be a disjunctive list-decoding $s_L$-code, $s\ge1$, $L\ge1$, (briefly, LD $s_L$-code) if the code is identified by the incidence matrix of a family of finite sets in which the union of any $s$ sets can cover not more than $L-1$ other sets of the family. In this paper, we introduce a natural {\em probabilistic} generalization of LD $s_L$-code when the code is said to be an almost disjunctive LD $s_L$-code if the unions of {\em almost all} $s$ sets satisfy the given condition. We develop a random coding method based on the ensemble of binary constant-weight codes to obtain lower bounds on the capacity and error probability exponent of such codes. For the considered ensemble our lower bounds are asymptotically tight. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1407.2482v1-abstract-full').style.display = 'none'; document.getElementById('1407.2482v1-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> 9 July, 2014; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2014. </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">17 pages, 1 table</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1401.0050">arXiv:1401.0050</a> <span>  </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="Probability">math.PR</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.1134/S0032946014010037">10.1134/S0032946014010037 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Bounds on the rate of superimposed codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=D%27yachkov%2C+A">Arkady D'yachkov</a>, <a href="/search/cs?searchtype=author&query=Vorobyev%2C+I">Ilya Vorobyev</a>, <a href="/search/cs?searchtype=author&query=Polianskii%2C+N">Nikita Polianskii</a>, <a href="/search/cs?searchtype=author&query=Shchukin%2C+V">Vladislav Shchukin</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="1401.0050v6-abstract-short" style="display: inline;"> A binary code is called a superimposed cover-free $(s,\ell)$-code if the code is identified by the incidence matrix of a family of finite sets in which no intersection of $\ell$ sets is covered by the union of $s$ others. A binary code is called a superimposed list-decoding $s_L$-code if the code is identified by the incidence matrix of a family of finite sets in which the union of any $s$ sets ca… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1401.0050v6-abstract-full').style.display = 'inline'; document.getElementById('1401.0050v6-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1401.0050v6-abstract-full" style="display: none;"> A binary code is called a superimposed cover-free $(s,\ell)$-code if the code is identified by the incidence matrix of a family of finite sets in which no intersection of $\ell$ sets is covered by the union of $s$ others. A binary code is called a superimposed list-decoding $s_L$-code if the code is identified by the incidence matrix of a family of finite sets in which the union of any $s$ sets can cover not more than $L-1$ other sets of the family. For $L=\ell=1$, both of the definitions coincide and the corresponding binary code is called a superimposed $s$-code. Our aim is to obtain new lower and upper bounds on the rate of given codes. The most interesting result is a lower bound on the rate of superimposed cover-free $(s,\ell)$-code based on the ensemble of constant-weight binary codes. If parameter $\ell\ge1$ is fixed and $s\to\infty$, then the ratio of this lower bound to the best known upper bound converges to the limit $2\,e^{-2}=0,271$. For the classical case $\ell=1$ and $s\ge2$, the given Statement means that our recurrent upper bound on the rate of superimposed $s$-codes obtained in 1982 is attained to within a constant factor $a$, $0,271\le a\le1$ <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1401.0050v6-abstract-full').style.display = 'none'; document.getElementById('1401.0050v6-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 May, 2016; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 30 December, 2013; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2014. </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">32 pages, 3 tables. We have found a mistake in the article. More precisely, the proof of Theorem 4 is incorrect</span> </p> </li> </ol> <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