Search | arXiv e-print repository

<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"/> <meta name="viewport" content="width=device-width, initial-scale=1"/>  <link rel="apple-touch-icon" sizes="180x180" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/apple-touch-icon.png"> <link rel="icon" type="image/png" sizes="32x32" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon-32x32.png"> <link rel="icon" type="image/png" sizes="16x16" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon-16x16.png"> <link rel="manifest" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/site.webmanifest"> <link rel="mask-icon" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/safari-pinned-tab.svg" color="#b31b1b"> <link rel="shortcut icon" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon.ico"> <meta name="msapplication-TileColor" content="#b31b1b"> <meta name="msapplication-config" content="images/icons/browserconfig.xml"> <meta name="theme-color" content="#b31b1b">  <title>Search | arXiv e-print repository</title> <script defer src="https://static.arxiv.org/static/base/1.0.0a5/fontawesome-free-5.11.2-web/js/all.js"></script> <link rel="stylesheet" href="https://static.arxiv.org/static/base/1.0.0a5/css/arxivstyle.css" /> <script type="text/x-mathjax-config"> MathJax.Hub.Config({ messageStyle: "none", extensions: ["tex2jax.js"], jax: ["input/TeX", "output/HTML-CSS"], tex2jax: { inlineMath: [ ['$','$'], ["\$","\$"] ], displayMath: [ ['$$','$$'], ["\\[","\\]"] ], processEscapes: true, ignoreClass: '.*', processClass: 'mathjax.*' }, TeX: { extensions: ["AMSmath.js", "AMSsymbols.js", "noErrors.js"], noErrors: { inlineDelimiters: ["$","$"], multiLine: false, style: { "font-size": "normal", "border": "" } } }, "HTML-CSS": { availableFonts: ["TeX"] } }); </script> <script src='//static.arxiv.org/MathJax-2.7.3/MathJax.js'></script> <script src="https://static.arxiv.org/static/base/1.0.0a5/js/notification.js"></script> <link rel="stylesheet" href="https://static.arxiv.org/static/search/0.5.6/css/bulma-tooltip.min.css" /> <link rel="stylesheet" href="https://static.arxiv.org/static/search/0.5.6/css/search.css" /> <script src="https://code.jquery.com/jquery-3.2.1.slim.min.js" integrity="sha256-k2WSCIexGzOj3Euiig+TlR8gA0EmPjuc79OEeY5L45g=" crossorigin="anonymous"></script> <script src="https://static.arxiv.org/static/search/0.5.6/js/fieldset.js"></script> <style> radio#cf-customfield_11400 { display: none; } </style> </head> <body> <header><a href="#main-container" class="is-sr-only">Skip to main content</a>  <div class="attribution level is-marginless" role="banner"> <div class="level-left"> <a class="level-item" href="https://cornell.edu/"><img src="https://static.arxiv.org/static/base/1.0.0a5/images/cornell-reduced-white-SMALL.svg" alt="Cornell University" width="200" aria-label="logo" /></a> </div> <div class="level-right is-marginless"><p class="sponsors level-item is-marginless"><span id="support-ack-url">We gratefully acknowledge support from<br /> the Simons Foundation, <a href="https://info.arxiv.org/about/ourmembers.html">member institutions</a>, and all contributors. <a href="https://info.arxiv.org/about/donate.html">Donate</a></span></p></div> </div>  <div class="identity level is-marginless"> <div class="level-left"> <div class="level-item"> <a class="arxiv" href="https://arxiv.org/" aria-label="arxiv-logo"> <img src="https://static.arxiv.org/static/base/1.0.0a5/images/arxiv-logo-one-color-white.svg" aria-label="logo" alt="arxiv logo" width="85" style="width:85px;"/> </a> </div> </div> <div class="search-block level-right"> <form class="level-item mini-search" method="GET" action="https://arxiv.org/search"> <div class="field has-addons"> <div class="control"> <input class="input is-small" type="text" name="query" placeholder="Search..." aria-label="Search term or terms" /> <p class="help"><a href="https://info.arxiv.org/help">Help</a> | <a href="https://arxiv.org/search/advanced">Advanced Search</a></p> </div> <div class="control"> <div class="select is-small"> <select name="searchtype" aria-label="Field to search"> <option value="all" selected="selected">All fields</option> <option value="title">Title</option> <option value="author">Author</option> <option value="abstract">Abstract</option> <option value="comments">Comments</option> <option value="journal_ref">Journal reference</option> <option value="acm_class">ACM classification</option> <option value="msc_class">MSC classification</option> <option value="report_num">Report number</option> <option value="paper_id">arXiv identifier</option> <option value="doi">DOI</option> <option value="orcid">ORCID</option> <option value="author_id">arXiv author ID</option> <option value="help">Help pages</option> <option value="full_text">Full text</option> </select> </div> </div> <input type="hidden" name="source" value="header"> <button class="button is-small is-cul-darker">Search</button> </div> </form> </div> </div>  <div class="container"> <div class="user-tools is-size-7 has-text-right has-text-weight-bold" role="navigation" aria-label="User menu"> <a href="https://arxiv.org/login">Login</a> </div> </div> </header> <main class="container" id="main-container"> <div class="level is-marginless"> <div class="level-left"> <h1 class="title is-clearfix"> Showing 1–50 of 65 results for author: <span class="mathjax">Pradhan, S S</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=Pradhan%2C+S+S">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="Pradhan, S S"> </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=Pradhan%2C+S+S&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="Pradhan, S S"> <ul id="abstracts"><li><input checked id="abstracts-0" name="abstracts" type="radio" value="show"> <label for="abstracts-0">Show abstracts</label></li><li><input id="abstracts-1" name="abstracts" type="radio" value="hide"> <label for="abstracts-1">Hide abstracts</label></li></ul> </div> <div class="box field is-grouped is-grouped-multiline level-item"> <div class="control"> <span class="select is-small"> <select id="size" name="size"><option value="25">25</option><option selected value="50">50</option><option value="100">100</option><option value="200">200</option></select> </span> <label for="size">results per page</label>. </div> <div class="control"> <label for="order">Sort results by</label> <span class="select is-small"> <select id="order" name="order"><option selected value="-announced_date_first">Announcement date (newest first)</option><option value="announced_date_first">Announcement date (oldest first)</option><option value="-submitted_date">Submission date (newest first)</option><option value="submitted_date">Submission date (oldest first)</option><option value="">Relevance</option></select> </span> </div> <div class="control"> <button class="button is-small is-link">Go</button> </div> </div> </form> </div> </div> <nav class="pagination is-small is-centered breathe-horizontal" role="navigation" aria-label="pagination"> <a href="" class="pagination-previous is-invisible">Previous </a> <a href="/search/?searchtype=author&query=Pradhan%2C+S+S&start=50" class="pagination-next" >Next </a> <ul class="pagination-list"> <li> <a href="/search/?searchtype=author&query=Pradhan%2C+S+S&start=0" class="pagination-link is-current" aria-label="Goto page 1">1 </a> </li> <li> <a href="/search/?searchtype=author&query=Pradhan%2C+S+S&start=50" class="pagination-link " aria-label="Page 2" aria-current="page">2 </a> </li> </ul> </nav> <ol class="breathe-horizontal" start="1"> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2502.12129">arXiv:2502.12129</a> <span> [<a href="https://arxiv.org/pdf/2502.12129">pdf</a>, <a href="https://arxiv.org/format/2502.12129">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="Quantum Physics">quant-ph</span> </div> </div> <p class="title is-5 mathjax"> When Wyner and Ziv Met Bayes in Quantum-Classical Realm </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Sohail%2C+M+A">Mohammad Aamir Sohail</a>, <a href="/search/cs?searchtype=author&query=Atif%2C+T+A">Touheed Anwar Atif</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="2502.12129v1-abstract-short" style="display: inline;"> In this work, we address the lossy quantum-classical source coding with the quantum side-information (QC-QSI) problem. The task is to compress the classical information about a quantum source, obtained after performing a measurement while incurring a bounded reconstruction error. Here, the decoder is allowed to use the side information to recover the classical data obtained from measurements on th… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2502.12129v1-abstract-full').style.display = 'inline'; document.getElementById('2502.12129v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2502.12129v1-abstract-full" style="display: none;"> In this work, we address the lossy quantum-classical source coding with the quantum side-information (QC-QSI) problem. The task is to compress the classical information about a quantum source, obtained after performing a measurement while incurring a bounded reconstruction error. Here, the decoder is allowed to use the side information to recover the classical data obtained from measurements on the source states. We introduce a new formulation based on a backward (posterior) channel, replacing the single-letter distortion observable with a single-letter posterior channel to capture reconstruction error. Unlike the rate-distortion framework, this formulation imposes a block error constraint. An analogous formulation is developed for lossy classical source coding with classical side information (C-CSI) problem. We derive an inner bound on the asymptotic performance limit in terms of single-letter quantum and classical mutual information quantities of the given posterior channel for QC-QSI and C-CSI cases, respectively. Furthermore, we establish a connection between rate-distortion and rate-channel theory, showing that a rate-channel compression protocol attains the optimal rate-distortion function for a specific distortion measure and level. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2502.12129v1-abstract-full').style.display = 'none'; document.getElementById('2502.12129v1-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 February, 2025; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2025. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2409.18307">arXiv:2409.18307</a> <span> [<a href="https://arxiv.org/pdf/2409.18307">pdf</a>, <a href="https://arxiv.org/ps/2409.18307">ps</a>, <a href="https://arxiv.org/format/2409.18307">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 the Strong Converse Exponent of the Classical Soft Covering </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=He%2C+X">Xingyi He</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="2409.18307v1-abstract-short" style="display: inline;"> In this paper, we provide a lower and an upper bound for the strong converse exponent of the soft covering problem in the classical setting. This exponent characterizes the slowest achievable convergence speed of the total variation to one when a code with a rate below mutual information is applied to a discrete memoryless channel for synthesizing a product output distribution. We employ a type-ba… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2409.18307v1-abstract-full').style.display = 'inline'; document.getElementById('2409.18307v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2409.18307v1-abstract-full" style="display: none;"> In this paper, we provide a lower and an upper bound for the strong converse exponent of the soft covering problem in the classical setting. This exponent characterizes the slowest achievable convergence speed of the total variation to one when a code with a rate below mutual information is applied to a discrete memoryless channel for synthesizing a product output distribution. We employ a type-based approach and additionally propose an equivalent form of our upper bound using the R茅nyi mutual information. Future works include tightening these two bounds to determine the exact bound of the strong converse exponent. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2409.18307v1-abstract-full').style.display = 'none'; document.getElementById('2409.18307v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 26 September, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2409.13133">arXiv:2409.13133</a> <span> [<a href="https://arxiv.org/pdf/2409.13133">pdf</a>, <a href="https://arxiv.org/format/2409.13133">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</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="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> CorBin-FL: A Differentially Private Federated Learning Mechanism using Common Randomness </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Salehi%2C+H+A">Hojat Allah Salehi</a>, <a href="/search/cs?searchtype=author&query=Mia%2C+M+J">Md Jueal Mia</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</a>, <a href="/search/cs?searchtype=author&query=Amini%2C+M+H">M. Hadi Amini</a>, <a href="/search/cs?searchtype=author&query=Shirani%2C+F">Farhad Shirani</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="2409.13133v1-abstract-short" style="display: inline;"> Federated learning (FL) has emerged as a promising framework for distributed machine learning. It enables collaborative learning among multiple clients, utilizing distributed data and computing resources. However, FL faces challenges in balancing privacy guarantees, communication efficiency, and overall model accuracy. In this work, we introduce CorBin-FL, a privacy mechanism that uses correlated… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2409.13133v1-abstract-full').style.display = 'inline'; document.getElementById('2409.13133v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2409.13133v1-abstract-full" style="display: none;"> Federated learning (FL) has emerged as a promising framework for distributed machine learning. It enables collaborative learning among multiple clients, utilizing distributed data and computing resources. However, FL faces challenges in balancing privacy guarantees, communication efficiency, and overall model accuracy. In this work, we introduce CorBin-FL, a privacy mechanism that uses correlated binary stochastic quantization to achieve differential privacy while maintaining overall model accuracy. The approach uses secure multi-party computation techniques to enable clients to perform correlated quantization of their local model updates without compromising individual privacy. We provide theoretical analysis showing that CorBin-FL achieves parameter-level local differential privacy (PLDP), and that it asymptotically optimizes the privacy-utility trade-off between the mean square error utility measure and the PLDP privacy measure. We further propose AugCorBin-FL, an extension that, in addition to PLDP, achieves user-level and sample-level central differential privacy guarantees. For both mechanisms, we derive bounds on privacy parameters and mean squared error performance measures. Extensive experiments on MNIST and CIFAR10 datasets demonstrate that our mechanisms outperform existing differentially private FL mechanisms, including Gaussian and Laplacian mechanisms, in terms of model accuracy under equal PLDP privacy budgets. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2409.13133v1-abstract-full').style.display = 'none'; document.getElementById('2409.13133v1-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 September, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2407.13858">arXiv:2407.13858</a> <span> [<a href="https://arxiv.org/pdf/2407.13858">pdf</a>, <a href="https://arxiv.org/format/2407.13858">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Quantum Physics">quant-ph</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Optimization and Control">math.OC</span> </div> </div> <p class="title is-5 mathjax"> Quantum Natural Stochastic Pairwise Coordinate Descent </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Sohail%2C+M+A">Mohammad Aamir Sohail</a>, <a href="/search/cs?searchtype=author&query=Khoozani%2C+M+H">Mohsen Heidari Khoozani</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="2407.13858v1-abstract-short" style="display: inline;"> Quantum machine learning through variational quantum algorithms (VQAs) has gained substantial attention in recent years. VQAs employ parameterized quantum circuits, which are typically optimized using gradient-based methods. However, these methods often exhibit sub-optimal convergence performance due to their dependence on Euclidean geometry. The quantum natural gradient descent (QNGD) optimizatio… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2407.13858v1-abstract-full').style.display = 'inline'; document.getElementById('2407.13858v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2407.13858v1-abstract-full" style="display: none;"> Quantum machine learning through variational quantum algorithms (VQAs) has gained substantial attention in recent years. VQAs employ parameterized quantum circuits, which are typically optimized using gradient-based methods. However, these methods often exhibit sub-optimal convergence performance due to their dependence on Euclidean geometry. The quantum natural gradient descent (QNGD) optimization method, which considers the geometry of the quantum state space via a quantum information (Riemannian) metric tensor, provides a more effective optimization strategy. Despite its advantages, QNGD encounters notable challenges for learning from quantum data, including the no-cloning principle, which prohibits the replication of quantum data, state collapse, and the measurement postulate, which leads to the stochastic loss function. This paper introduces the quantum natural stochastic pairwise coordinate descent (2-QNSCD) optimization method. This method leverages the curved geometry of the quantum state space through a novel ensemble-based quantum information metric tensor, offering a more physically realizable optimization strategy for learning from quantum data. To improve computational efficiency and reduce sample complexity, we develop a highly sparse unbiased estimator of the novel metric tensor using a quantum circuit with gate complexity $螛(1)$ times that of the parameterized quantum circuit and single-shot quantum measurements. Our approach avoids the need for multiple copies of quantum data, thus adhering to the no-cloning principle. We provide a detailed theoretical foundation for our optimization method, along with an exponential convergence analysis. Additionally, we validate the utility of our method through a series of numerical experiments. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2407.13858v1-abstract-full').style.display = 'none'; document.getElementById('2407.13858v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 18 July, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2402.11112">arXiv:2402.11112</a> <span> [<a href="https://arxiv.org/pdf/2402.11112">pdf</a>, <a href="https://arxiv.org/format/2402.11112">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="Quantum Physics">quant-ph</span> </div> </div> <p class="title is-5 mathjax"> Quantum Soft Covering and Decoupling with Relative Entropy Criterion </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=He%2C+X">Xingyi He</a>, <a href="/search/cs?searchtype=author&query=Atif%2C+T+A">Touheed Anwar Atif</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2402.11112v1-abstract-short" style="display: inline;"> We propose quantum soft covering problems for fully quantum channels and classical-quantum (CQ) channels using relative entropy as a criterion of operator closeness. We prove covering lemmas by deriving one-shot bounds on the rates in terms of smooth min-entropies and smooth max-divergences, respectively. In the asymptotic regime, we show that for quantum channels, the rate infimum defined as the… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2402.11112v1-abstract-full').style.display = 'inline'; document.getElementById('2402.11112v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2402.11112v1-abstract-full" style="display: none;"> We propose quantum soft covering problems for fully quantum channels and classical-quantum (CQ) channels using relative entropy as a criterion of operator closeness. We prove covering lemmas by deriving one-shot bounds on the rates in terms of smooth min-entropies and smooth max-divergences, respectively. In the asymptotic regime, we show that for quantum channels, the rate infimum defined as the logarithm of the minimum rank of the input state is the coherent information between the reference and output state; for CQ channels, the rate infimum defined as the logarithm of the minimum number of input codewords is the Helovo information between the input and output state. Furthermore, we present a one-shot quantum decoupling theorem with relative entropy criterion. Our results based on the relative-entropy criterion are tighter than the corresponding results based on the trace norm considered in the literature due to the Pinsker inequality. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2402.11112v1-abstract-full').style.display = 'none'; document.getElementById('2402.11112v1-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> 16 February, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2402.00242">arXiv:2402.00242</a> <span> [<a href="https://arxiv.org/pdf/2402.00242">pdf</a>, <a href="https://arxiv.org/format/2402.00242">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Quantum Physics">quant-ph</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Quantum Advantage in Non-Interactive Source Simulation </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Salehi%2C+H+A">Hojat Allah Salehi</a>, <a href="/search/cs?searchtype=author&query=Shirani%2C+F">Farhad Shirani</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2402.00242v2-abstract-short" style="display: inline;"> This work considers the non-interactive source simulation problem (NISS). In the standard NISS scenario, a pair of distributed agents, Alice and Bob, observe a distributed binary memoryless source $(X^d,Y^d)$ generated based on joint distribution $P_{X,Y}$. The agents wish to produce a pair of discrete random variables $(U_d,V_d)$ with joint distribution $P_{U_d,V_d}$, such that $P_{U_d,V_d}$ conv… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2402.00242v2-abstract-full').style.display = 'inline'; document.getElementById('2402.00242v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2402.00242v2-abstract-full" style="display: none;"> This work considers the non-interactive source simulation problem (NISS). In the standard NISS scenario, a pair of distributed agents, Alice and Bob, observe a distributed binary memoryless source $(X^d,Y^d)$ generated based on joint distribution $P_{X,Y}$. The agents wish to produce a pair of discrete random variables $(U_d,V_d)$ with joint distribution $P_{U_d,V_d}$, such that $P_{U_d,V_d}$ converges in total variation distance to a target distribution $Q_{U,V}$. Two variations of the standard NISS scenario are considered. In the first variation, in addition to $(X^d,Y^d)$ the agents have access to a shared Bell state. The agents each measure their respective state, using a measurement of their choice, and use its classical output along with $(X^d,Y^d)$ to simulate the target distribution. This scenario is called the entanglement-assisted NISS (EA-NISS). In the second variation, the agents have access to a classical common random bit $Z$, in addition to $(X^d,Y^d)$. This scenario is called the classical common randomness NISS (CR-NISS). It is shown that for binary-output NISS scenarios, the set of feasible distributions for EA-NISS and CR-NISS are equal with each other. Hence, there is not quantum advantage in these EA-NISS scenarios. For non-binary output NISS scenarios, it is shown through an example that there are distributions that are feasible in EA-NISS but not in CR-NISS. This shows that there is a quantum advantage in non-binary output EA-NISS. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2402.00242v2-abstract-full').style.display = 'none'; document.getElementById('2402.00242v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 2 May, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 31 January, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2401.05824">arXiv:2401.05824</a> <span> [<a href="https://arxiv.org/pdf/2401.05824">pdf</a>, <a href="https://arxiv.org/format/2401.05824">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Human-Computer Interaction">cs.HC</span> </div> </div> <p class="title is-5 mathjax"> Youth WellTech: A Global Remote Co-Design Sprint for Youth Mental Health Technology </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Phang%2C+K">Kenji Phang</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">Siddharth Saarathi Pradhan</a>, <a href="/search/cs?searchtype=author&query=Ikwuegbu%2C+C">Chino Ikwuegbu</a>, <a href="/search/cs?searchtype=author&query=Ramos%2C+G">Gonzalo Ramos</a>, <a href="/search/cs?searchtype=author&query=Ford%2C+D">Denae Ford</a>, <a href="/search/cs?searchtype=author&query=Okoli%2C+E">Ebele Okoli</a>, <a href="/search/cs?searchtype=author&query=Chishti%2C+S+M+K">Salman Muin Kayser Chishti</a>, <a href="/search/cs?searchtype=author&query=Suh%2C+J">Jina Suh</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.05824v1-abstract-short" style="display: inline;"> Mental health is a pressing concern in today's digital age, particularly among youth who are deeply intertwined with technology. Despite the influx of technology solutions addressing mental health issues, youth often remain sidelined during the design process. While co-design methods have been employed to improve participation by youth, many such initiatives are limited to design activities and la… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2401.05824v1-abstract-full').style.display = 'inline'; document.getElementById('2401.05824v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2401.05824v1-abstract-full" style="display: none;"> Mental health is a pressing concern in today's digital age, particularly among youth who are deeply intertwined with technology. Despite the influx of technology solutions addressing mental health issues, youth often remain sidelined during the design process. While co-design methods have been employed to improve participation by youth, many such initiatives are limited to design activities and lack training for youth to research and develop solutions for themselves. In this case study, we detail our 8-week remote, collaborative research initiative called Youth WellTech, designed to facilitate remote co-design sprints aimed at equipping youth with the tools and knowledge to envision and design tech futures for their own communities. We pilot this initiative with 12 student technology evangelists across 8 countries globally to foster the sharing of mental health challenges and diverse perspectives. We highlight insights from our experiences running this global program remotely, its structure, and recommendations for co-research. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2401.05824v1-abstract-full').style.display = 'none'; document.getElementById('2401.05824v1-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 January, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 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">Case Study, 13 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">ACM Class:</span> H.5.2 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2309.13347">arXiv:2309.13347</a> <span> [<a href="https://arxiv.org/pdf/2309.13347">pdf</a>, <a href="https://arxiv.org/format/2309.13347">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Sound">cs.SD</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Audio and Speech Processing">eess.AS</span> </div> </div> <p class="title is-5 mathjax"> My Science Tutor (MyST) -- A Large Corpus of Children's Conversational Speech </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">Sameer S. Pradhan</a>, <a href="/search/cs?searchtype=author&query=Cole%2C+R+A">Ronald A. Cole</a>, <a href="/search/cs?searchtype=author&query=Ward%2C+W+H">Wayne H. Ward</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="2309.13347v1-abstract-short" style="display: inline;"> This article describes the MyST corpus developed as part of the My Science Tutor project -- one of the largest collections of children's conversational speech comprising approximately 400 hours, spanning some 230K utterances across about 10.5K virtual tutor sessions by around 1.3K third, fourth and fifth grade students. 100K of all utterances have been transcribed thus far. The corpus is freely av… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2309.13347v1-abstract-full').style.display = 'inline'; document.getElementById('2309.13347v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2309.13347v1-abstract-full" style="display: none;"> This article describes the MyST corpus developed as part of the My Science Tutor project -- one of the largest collections of children's conversational speech comprising approximately 400 hours, spanning some 230K utterances across about 10.5K virtual tutor sessions by around 1.3K third, fourth and fifth grade students. 100K of all utterances have been transcribed thus far. The corpus is freely available (https://myst.cemantix.org) for non-commercial use using a creative commons license. It is also available for commercial use (https://boulderlearning.com/resources/myst-corpus/). To date, ten organizations have licensed the corpus for commercial use, and approximately 40 university and other not-for-profit research groups have downloaded the corpus. It is our hope that the corpus can be used to improve automatic speech recognition algorithms, build and evaluate conversational AI agents for education, and together help accelerate development of multimodal applications to improve children's excitement and learning about science, and help them learn remotely. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2309.13347v1-abstract-full').style.display = 'none'; document.getElementById('2309.13347v1-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 September, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2306.12416">arXiv:2306.12416</a> <span> [<a href="https://arxiv.org/pdf/2306.12416">pdf</a>, <a href="https://arxiv.org/format/2306.12416">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Quantum Physics">quant-ph</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.1142/S0219749924400136">10.1142/S0219749924400136 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Quantum soft-covering lemma with applications to rate-distortion coding, resolvability and identification via quantum channels </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Atif%2C+T+A">Touheed Anwar Atif</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</a>, <a href="/search/cs?searchtype=author&query=Winter%2C+A">Andreas Winter</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="2306.12416v3-abstract-short" style="display: inline;"> We propose a quantum soft-covering problem for a given general quantum channel and one of its output states, which consists in finding the minimum rank of an input state needed to approximate the given channel output. We then prove a one-shot quantum covering lemma in terms of smooth min-entropies by leveraging decoupling techniques from quantum Shannon theory. This covering result is shown to be… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2306.12416v3-abstract-full').style.display = 'inline'; document.getElementById('2306.12416v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2306.12416v3-abstract-full" style="display: none;"> We propose a quantum soft-covering problem for a given general quantum channel and one of its output states, which consists in finding the minimum rank of an input state needed to approximate the given channel output. We then prove a one-shot quantum covering lemma in terms of smooth min-entropies by leveraging decoupling techniques from quantum Shannon theory. This covering result is shown to be equivalent to a coding theorem for rate distortion under a posterior (reverse) channel distortion criterion by two of the present authors. Both one-shot results directly yield corollaries about the i.i.d. asymptotics, in terms of the coherent information of the channel. The power of our quantum covering lemma is demonstrated by two additional applications: first, we formulate a quantum channel resolvability problem, and provide one-shot as well as asymptotic upper and lower bounds. Secondly, we provide new upper bounds on the unrestricted and simultaneous identification capacities of quantum channels, in particular separating for the first time the simultaneous identification capacity from the unrestricted one, proving a long-standing conjecture of the last author. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2306.12416v3-abstract-full').style.display = 'none'; document.getElementById('2306.12416v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 26 April, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 21 June, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 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">30 pages, 3 figures; v2 fixes an error in Definition 36 and various typos and minor issues throughout; v3 fixes some further minor points and provides a proof of Lemma 11 due to F. Dupuis, it is the version accepted by IJQI (special issue in honour of Alexander S. Holevo)</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Int. J. Quantum Inf. 22(5):2440013, 2024 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2306.06796">arXiv:2306.06796</a> <span> [<a href="https://arxiv.org/pdf/2306.06796">pdf</a>, <a href="https://arxiv.org/format/2306.06796">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 The Reliability Function of Discrete Memoryless Multiple-Access Channel with Feedback </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Heidari%2C+M">Mohsen Heidari</a>, <a href="/search/cs?searchtype=author&query=Anastasopoulos%2C+A">Achilleas Anastasopoulos</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="2306.06796v1-abstract-short" style="display: inline;"> The reliability function of a channel is the maximum achievable exponential rate of decay of the error probability as a function of the transmission rate. In this work, we derive bounds on the reliability function of discrete memoryless multiple-access channels (MAC) with noiseless feedback. We show that our bounds are tight for a variety of MACs, such as $m$-ary additive and two independent point… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2306.06796v1-abstract-full').style.display = 'inline'; document.getElementById('2306.06796v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2306.06796v1-abstract-full" style="display: none;"> The reliability function of a channel is the maximum achievable exponential rate of decay of the error probability as a function of the transmission rate. In this work, we derive bounds on the reliability function of discrete memoryless multiple-access channels (MAC) with noiseless feedback. We show that our bounds are tight for a variety of MACs, such as $m$-ary additive and two independent point-to-point channels. The bounds are expressed in terms of a new information measure called ``variable-length directed information". The upper bound is proved by analyzing stochastic processes defined based on the entropy of the message, given the past channel's outputs. Our method relies on tools from the theory of martingales, variable-length information measures, and a new technique called time pruning. We further propose a variable-length achievable scheme consisting of three phases: (i) data transmission, (ii) hybrid data-confirmation, and (iii) full confirmation. We show that two-phase-type schemes are strictly suboptimal in achieving the MAC's reliability function. Moreover, we study the shape of the lower-bound and show that it increases linearly with respect to a specific Euclidean distance measure defined between the transmission rate pair and the capacity boundary. As side results, we derive an upper bound on the capacity of MAC with noiseless feedback and study a new problem involving a hybrid of hypothesis testing and data transmission. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2306.06796v1-abstract-full').style.display = 'none'; document.getElementById('2306.06796v1-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 June, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2305.10004">arXiv:2305.10004</a> <span> [<a href="https://arxiv.org/pdf/2305.10004">pdf</a>, <a href="https://arxiv.org/format/2305.10004">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Quantum Physics">quant-ph</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Rate-Limited Quantum-to-Classical Optimal Transport in Finite and Continuous-Variable Quantum Systems </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Garmaroudi%2C+H+M">Hafez M. Garmaroudi</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</a>, <a href="/search/cs?searchtype=author&query=Chen%2C+J">Jun Chen</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.10004v2-abstract-short" style="display: inline;"> We consider the rate-limited quantum-to-classical optimal transport in terms of output-constrained rate-distortion coding for both finite-dimensional and continuous-variable quantum-to-classical systems with limited classical common randomness. The main coding theorem provides a single-letter characterization of the achievable rate region of a lossy quantum measurement source coding for an exact c… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.10004v2-abstract-full').style.display = 'inline'; document.getElementById('2305.10004v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2305.10004v2-abstract-full" style="display: none;"> We consider the rate-limited quantum-to-classical optimal transport in terms of output-constrained rate-distortion coding for both finite-dimensional and continuous-variable quantum-to-classical systems with limited classical common randomness. The main coding theorem provides a single-letter characterization of the achievable rate region of a lossy quantum measurement source coding for an exact construction of the destination distribution (or the equivalent quantum state) while maintaining a threshold of distortion from the source state according to a generally defined distortion observable. The constraint on the output space fixes the output distribution to an IID predefined probability mass function. Therefore, this problem can also be viewed as information-constrained optimal transport which finds the optimal cost of transporting the source quantum state to the destination classical distribution via a quantum measurement with limited communication rate and common randomness. We develop a coding framework for continuous-variable quantum systems by employing a clipping projection and a dequantization block and using our finite-dimensional coding theorem. Moreover, for the Gaussian quantum systems, we derive an analytical solution for rate-limited Wasserstein distance of order 2, along with a Gaussian optimality theorem, showing that Gaussian measurement optimizes the rate in a system with Gaussian quantum source and Gaussian destination distribution. The results further show that in contrast to the classical Wasserstein distance of Gaussian distributions, which corresponds to an infinite transmission rate, in the Quantum Gaussian measurement system, the optimal transport is achieved with a finite transmission rate due to the inherent noise of the quantum measurement imposed by Heisenberg's uncertainty principle. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.10004v2-abstract-full').style.display = 'none'; document.getElementById('2305.10004v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 28 November, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 17 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">51 pages, 4 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/2303.09511">arXiv:2303.09511</a> <span> [<a href="https://arxiv.org/pdf/2303.09511">pdf</a>, <a href="https://arxiv.org/format/2303.09511">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="Signal Processing">eess.SP</span> </div> </div> <p class="title is-5 mathjax"> Capacity-achieving Polar-based Codes with Sparsity Constraints on the Generator Matrices </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Pang%2C+J+C">James Chin-Jen Pang</a>, <a href="/search/cs?searchtype=author&query=Mahdavifar%2C+H">Hessam Mahdavifar</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="2303.09511v1-abstract-short" style="display: inline;"> In this paper, we leverage polar codes and the well-established channel polarization to design capacity-achieving codes with a certain constraint on the weights of all the columns in the generator matrix (GM) while having a low-complexity decoding algorithm. We first show that given a binary-input memoryless symmetric (BMS) channel $W$ and a constant $s \in (0, 1]$, there exists a polarization ker… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2303.09511v1-abstract-full').style.display = 'inline'; document.getElementById('2303.09511v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2303.09511v1-abstract-full" style="display: none;"> In this paper, we leverage polar codes and the well-established channel polarization to design capacity-achieving codes with a certain constraint on the weights of all the columns in the generator matrix (GM) while having a low-complexity decoding algorithm. We first show that given a binary-input memoryless symmetric (BMS) channel $W$ and a constant $s \in (0, 1]$, there exists a polarization kernel such that the corresponding polar code is capacity-achieving with the \textit{rate of polarization} $s/2$, and the GM column weights being bounded from above by $N^s$. To improve the sparsity versus error rate trade-off, we devise a column-splitting algorithm and two coding schemes for BEC and then for general BMS channels. The \textit{polar-based} codes generated by the two schemes inherit several fundamental properties of polar codes with the original $2 \times 2$ kernel including the decay in error probability, decoding complexity, and the capacity-achieving property. Furthermore, they demonstrate the additional property that their GM column weights are bounded from above sublinearly in $N$, while the original polar codes have some column weights that are linear in $N$. In particular, for any BEC and $尾<0.5$, the existence of a sequence of capacity-achieving polar-based codes where all the GM column weights are bounded from above by $N^位$ with $位\approx 0.585$, and with the error probability bounded by $O(2^{-N^尾} )$ under a decoder with complexity $O(N\log N)$, is shown. The existence of similar capacity-achieving polar-based codes with the same decoding complexity is shown for any BMS channel and $尾<0.5$ with $位\approx 0.631$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2303.09511v1-abstract-full').style.display = 'none'; document.getElementById('2303.09511v1-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> 16 March, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 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">31 pages, single column. arXiv admin note: substantial text overlap with arXiv:2012.13977</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2302.00625">arXiv:2302.00625</a> <span> [<a href="https://arxiv.org/pdf/2302.00625">pdf</a>, <a href="https://arxiv.org/format/2302.00625">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Quantum Physics">quant-ph</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Lossy Quantum Source Coding with a Global Error Criterion based on a Posterior Reference Map </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Atif%2C+T+A">Touheed Anwar Atif</a>, <a href="/search/cs?searchtype=author&query=Sohail%2C+M+A">Mohammad Aamir Sohail</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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.00625v1-abstract-short" style="display: inline;"> We consider the lossy quantum source coding problem where the task is to compress a given quantum source below its von Neumann entropy. Inspired by the duality connections between the rate-distortion and channel coding problems in the classical setting, we propose a new formulation for the lossy quantum source coding problem. This formulation differs from the existing quantum rate-distortion theor… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.00625v1-abstract-full').style.display = 'inline'; document.getElementById('2302.00625v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2302.00625v1-abstract-full" style="display: none;"> We consider the lossy quantum source coding problem where the task is to compress a given quantum source below its von Neumann entropy. Inspired by the duality connections between the rate-distortion and channel coding problems in the classical setting, we propose a new formulation for the lossy quantum source coding problem. This formulation differs from the existing quantum rate-distortion theory in two aspects. Firstly, we require that the reconstruction of the compressed quantum source fulfill a global error constraint as opposed to the sample-wise local error criterion used in the standard rate-distortion setting. Secondly, instead of a distortion observable, we employ the notion of a backward quantum channel, which we refer to as a "posterior reference map", to measure the reconstruction error. Using these, we characterize the asymptotic performance limit of the lossy quantum source coding problem in terms of single-letter coherent information of the given posterior reference map. We demonstrate a protocol to encode (at the specified rate) and decode, with the reconstruction satisfying the provided global error criterion, and therefore achieving the asymptotic performance limit. The protocol is constructed by decomposing coherent information as a difference of two Holevo information quantities, inspired from prior works in quantum communication problems. To further support the findings, we develop analogous formulations for the quantum-classical and classical variants and express the asymptotic performance limit in terms of single-letter mutual information quantities with respect to appropriately defined channels analogous to posterior reference maps. We also provide various examples for the three formulations, and shed light on their connection to the standard rate-distortion formulation wherever possible. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.00625v1-abstract-full').style.display = 'none'; document.getElementById('2302.00625v1-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> 1 February, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2203.05511">arXiv:2203.05511</a> <span> [<a href="https://arxiv.org/pdf/2203.05511">pdf</a>, <a href="https://arxiv.org/ps/2203.05511">ps</a>, <a href="https://arxiv.org/format/2203.05511">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Quantum Physics">quant-ph</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Multi-Party Quantum Purity Distillation with Bounded Classical Communication </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Atif%2C+T+A">Touheed Anwar Atif</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="2203.05511v1-abstract-short" style="display: inline;"> We consider the task of distilling local purity from a noisy quantum state $蟻^{ABC}$, wherein we provide a protocol for three parties, Alice, Bob and Charlie, to distill local purity (at a rate $P$) from many independent copies of a given quantum state $蟻^{ABC}$. The three parties have access to their respective subsystems of $蟻^{ABC}$, and are provided with pure ancilla catalytically, i.e., with… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2203.05511v1-abstract-full').style.display = 'inline'; document.getElementById('2203.05511v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2203.05511v1-abstract-full" style="display: none;"> We consider the task of distilling local purity from a noisy quantum state $蟻^{ABC}$, wherein we provide a protocol for three parties, Alice, Bob and Charlie, to distill local purity (at a rate $P$) from many independent copies of a given quantum state $蟻^{ABC}$. The three parties have access to their respective subsystems of $蟻^{ABC}$, and are provided with pure ancilla catalytically, i.e., with the promise of returning them unaltered after the end of the protocol. In addition, Alice and Bob can communicate with Charlie using a one-way multiple-access dephasing channel of link rates $R_1$ and $R_2$, respectively. The objective of the protocol is to minimize the usage of the dephasing channel (in terms of rates $R_1$ and $R_2$) while maximizing the asymptotic purity that can be jointly distilled from $蟻^{ABC}$. To achieve this, we employ ideas from distributed measurement compression protocols, and in turn, characterize a set of sufficient conditions on $(P,R_1,R_2)$ in terms of quantum information theoretic quantities such that $P$ amount of purity can be distilled using rates $R_1$ and $R_2$. Finally, we also incorporate the technique of asymptotic algebraic structured coding, and provide a unified approach of characterizing the performance limits. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2203.05511v1-abstract-full').style.display = 'none'; document.getElementById('2203.05511v1-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 March, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 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.11238">arXiv:2202.11238</a> <span> [<a href="https://arxiv.org/pdf/2202.11238">pdf</a>, <a href="https://arxiv.org/format/2202.11238">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="Signal Processing">eess.SP</span> </div> </div> <p class="title is-5 mathjax"> Lattices from Linear Codes: Source and Channel Networks </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Shirani%2C+F">Farhad Shirani</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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.11238v1-abstract-short" style="display: inline;"> In this paper, we consider the information-theoretic characterization of the set of achievable rates and distortions in a broad class of multiterminal communication scenarios with general continuous-valued sources and channels. A framework is presented which involves fine discretization of the source and channel variables followed by communication over the resulting discretized network. In order t… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2202.11238v1-abstract-full').style.display = 'inline'; document.getElementById('2202.11238v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2202.11238v1-abstract-full" style="display: none;"> In this paper, we consider the information-theoretic characterization of the set of achievable rates and distortions in a broad class of multiterminal communication scenarios with general continuous-valued sources and channels. A framework is presented which involves fine discretization of the source and channel variables followed by communication over the resulting discretized network. In order to evaluate fundamental performance limits, convergence results for information measures are provided under the proposed discretization process. Using this framework, we consider point-to-point source coding and channel coding with side-information, distributed source coding with distortion constraints, the function reconstruction problems (two-help-one), computation over multiple access channel, the interference channel, and the multiple-descriptions source coding problem. We construct lattice-like codes for general sources and channels, and derive inner-bounds to set of achievable rates and distortions in these communication scenarios. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2202.11238v1-abstract-full').style.display = 'none'; document.getElementById('2202.11238v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 22 February, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 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.10403">arXiv:2202.10403</a> <span> [<a href="https://arxiv.org/pdf/2202.10403">pdf</a>, <a href="https://arxiv.org/format/2202.10403">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="Systems and Control">eess.SY</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Quantum Physics">quant-ph</span> </div> </div> <p class="title is-5 mathjax"> Unified approach for computing sum of sources over CQ-MAC </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Sohail%2C+M+A">Mohammad Aamir Sohail</a>, <a href="/search/cs?searchtype=author&query=Atif%2C+T+A">Touheed Anwar Atif</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</a>, <a href="/search/cs?searchtype=author&query=Padakandla%2C+A">Arun Padakandla</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.10403v2-abstract-short" style="display: inline;"> We consider the task of communicating a generic bivariate function of two classical sources over a Classical-Quantum Multiple Access Channel (CQ-MAC). The two sources are observed at the encoders of the CQ-MAC, and the decoder aims at reconstructing a bivariate function from the received quantum state. Inspired by the techniques developed for the analogous classical setting, and employing the tech… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2202.10403v2-abstract-full').style.display = 'inline'; document.getElementById('2202.10403v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2202.10403v2-abstract-full" style="display: none;"> We consider the task of communicating a generic bivariate function of two classical sources over a Classical-Quantum Multiple Access Channel (CQ-MAC). The two sources are observed at the encoders of the CQ-MAC, and the decoder aims at reconstructing a bivariate function from the received quantum state. Inspired by the techniques developed for the analogous classical setting, and employing the technique of simultaneous (joint) decoding developed for the classical-quantum setting, we propose and analyze a coding scheme based on a fusion of algebraic structured and unstructured codes. This coding scheme allows exploiting both the symmetric structure common amongst the sources and the asymmetries. We derive a new set of sufficient conditions that strictly enlarges the largest known set of sources (capable of communicating the bivariate function) for any given CQ-MAC. We provide these conditions in terms of single-letter quantum information-theoretic quantities. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2202.10403v2-abstract-full').style.display = 'none'; document.getElementById('2202.10403v2-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 February, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 21 February, 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">20 pages, 4 figures. Update: a detailed example</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2202.09933">arXiv:2202.09933</a> <span> [<a href="https://arxiv.org/pdf/2202.09933">pdf</a>, <a href="https://arxiv.org/ps/2202.09933">ps</a>, <a href="https://arxiv.org/format/2202.09933">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"> Upper Bounds on the Feedback Error Exponent of Channels With States and Memory </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Heidari%2C+M">Mohsen Heidari</a>, <a href="/search/cs?searchtype=author&query=Anastasopoulos%2C+A">Achilleas Anastasopoulos</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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.09933v1-abstract-short" style="display: inline;"> As a class of state-dependent channels, Markov channels have been long studied in information theory for characterizing the feedback capacity and error exponent. This paper studies a more general variant of such channels where the state evolves via a general stochastic process, not necessarily Markov or ergodic. The states are assumed to be unknown to the transmitter and the receiver, but the unde… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2202.09933v1-abstract-full').style.display = 'inline'; document.getElementById('2202.09933v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2202.09933v1-abstract-full" style="display: none;"> As a class of state-dependent channels, Markov channels have been long studied in information theory for characterizing the feedback capacity and error exponent. This paper studies a more general variant of such channels where the state evolves via a general stochastic process, not necessarily Markov or ergodic. The states are assumed to be unknown to the transmitter and the receiver, but the underlying probability distributions are known. For this setup, we derive an upper bound on the feedback error exponent and the feedback capacity with variable-length codes. The bounds are expressed in terms of the directed mutual information and directed relative entropy. The bounds on the error exponent are simplified to Burnashev's expression for discrete memoryless channels. Our method relies on tools from the theory of martingales to analyze a stochastic process defined based on the entropy of the message given the past channel's outputs. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2202.09933v1-abstract-full').style.display = 'none'; document.getElementById('2202.09933v1-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 February, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 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.03472">arXiv:2202.03472</a> <span> [<a href="https://arxiv.org/pdf/2202.03472">pdf</a>, <a href="https://arxiv.org/format/2202.03472">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="Signal Processing">eess.SP</span> </div> </div> <p class="title is-5 mathjax"> New Bounds on the Size of Binary Codes with Large Minimum Distance </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Pang%2C+J+C">James Chin-Jen Pang</a>, <a href="/search/cs?searchtype=author&query=Mahdavifar%2C+H">Hessam Mahdavifar</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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.03472v4-abstract-short" style="display: inline;"> Let $A(n, d)$ denote the maximum size of a binary code of length $n$ and minimum Hamming distance $d$. Studying $A(n, d)$, including efforts to determine it as well to derive bounds on $A(n, d)$ for large $n$'s, is one of the most fundamental subjects in coding theory. In this paper, we explore new lower and upper bounds on $A(n, d)$ in the large-minimum distance regime, in particular, when… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2202.03472v4-abstract-full').style.display = 'inline'; document.getElementById('2202.03472v4-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2202.03472v4-abstract-full" style="display: none;"> Let $A(n, d)$ denote the maximum size of a binary code of length $n$ and minimum Hamming distance $d$. Studying $A(n, d)$, including efforts to determine it as well to derive bounds on $A(n, d)$ for large $n$'s, is one of the most fundamental subjects in coding theory. In this paper, we explore new lower and upper bounds on $A(n, d)$ in the large-minimum distance regime, in particular, when $d = n/2 - 惟(\sqrt{n})$. We first provide a new construction of cyclic codes, by carefully selecting specific roots in the binary extension field for the check polynomial, with length $n= 2^m -1$, distance $d \geq n/2 - 2^{c-1}\sqrt{n}$, and size $n^{c+1/2}$, for any $m\geq 4$ and any integer $c$ with $0 \leq c \leq m/2 - 1$. These code parameters are slightly worse than those of the Delsarte--Goethals (DG) codes that provide the previously known best lower bound in the large-minimum distance regime. However, using a similar and extended code construction technique we show a sequence of cyclic codes that improve upon DG codes and provide the best lower bound in a narrower range of the minimum distance $d$, in particular, when $d = n/2 - 惟(n^{2/3})$. Furthermore, by leveraging a Fourier-analytic view of Delsarte's linear program, upper bounds on $A(n, n/2 - 蟻\sqrt{n})$ with $蟻\in (0.5, 9.5)$ are obtained that scale polynomially in $n$. To the best of authors' knowledge, the upper bound due to Barg and Nogin \cite{barg2006spectral} is the only previously known upper bound that scale polynomially in $n$ in this regime. We numerically demonstrate that our upper bound improves upon the Barg-Nogin upper bound in the specified high-minimum distance regime. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2202.03472v4-abstract-full').style.display = 'none'; document.getElementById('2202.03472v4-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 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 7 February, 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">23 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/2103.07339">arXiv:2103.07339</a> <span> [<a href="https://arxiv.org/pdf/2103.07339">pdf</a>, <a href="https://arxiv.org/format/2103.07339">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"> Synthesizing Correlated Randomness using Algebraic Structured Codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Atif%2C+T+A">Touheed Anwar Atif</a>, <a href="/search/cs?searchtype=author&query=Padakandla%2C+A">Arun Padakandla</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="2103.07339v1-abstract-short" style="display: inline;"> In this problem, Alice and Bob, are provided $X_{1}^{n}$ and $X_{2}^{n}$ that are IID $p_{X_1 X_2}$. Alice and Bob can communicate to Charles over (noiseless) links of rate $R_1$ and $R_2$, respectively. Their goal is to enable Charles generate samples $Y^{n}$ such that the triple $(X_{1}^{n},X_{2}^{n},Y^{n})$ has a PMF that is close, in total variation, to $\prod p_{X_1 X_2 Y}$. In addition, the… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2103.07339v1-abstract-full').style.display = 'inline'; document.getElementById('2103.07339v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2103.07339v1-abstract-full" style="display: none;"> In this problem, Alice and Bob, are provided $X_{1}^{n}$ and $X_{2}^{n}$ that are IID $p_{X_1 X_2}$. Alice and Bob can communicate to Charles over (noiseless) links of rate $R_1$ and $R_2$, respectively. Their goal is to enable Charles generate samples $Y^{n}$ such that the triple $(X_{1}^{n},X_{2}^{n},Y^{n})$ has a PMF that is close, in total variation, to $\prod p_{X_1 X_2 Y}$. In addition, the three parties may posses shared common randomness at rate $C$. We address the problem of characterizing the set of rate triples $(R_1,R_2,C)$ for which the above goal can be accomplished. We build on our recent findings and propose a new coding scheme based on coset codes. We analyze its information-theoretic performance and derive a new inner bound. We identify examples for which the derived inner bound is analytically proven to contain rate triples that are not achievable via any known unstructured code based coding techniques. Our findings build on a variant of soft-covering which generalizes its applicability to the algebraic structured code ensembles. This adds to the advancement of the use structured codes in network information theory. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2103.07339v1-abstract-full').style.display = 'none'; document.getElementById('2103.07339v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 12 March, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2021. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2103.03978">arXiv:2103.03978</a> <span> [<a href="https://arxiv.org/pdf/2103.03978">pdf</a>, <a href="https://arxiv.org/ps/2103.03978">ps</a>, <a href="https://arxiv.org/format/2103.03978">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="Quantum Physics">quant-ph</span> </div> </div> <p class="title is-5 mathjax"> Achievable rate-region for $3-$User Classical-Quantum Interference Channel using Structured Codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Atif%2C+T+A">Touheed Anwar Atif</a>, <a href="/search/cs?searchtype=author&query=Padakandla%2C+A">Arun Padakandla</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="2103.03978v1-abstract-short" style="display: inline;"> We consider the problem of characterizing an inner bound to the capacity region of a $3-$user classical-quantum interference channel ($3-$CQIC). The best known coding scheme for communicating over CQICs is based on unstructured random codes and employs the techniques of message splitting and superposition coding. For classical $3-$user interference channels (ICs), it has been proven that coding te… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2103.03978v1-abstract-full').style.display = 'inline'; document.getElementById('2103.03978v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2103.03978v1-abstract-full" style="display: none;"> We consider the problem of characterizing an inner bound to the capacity region of a $3-$user classical-quantum interference channel ($3-$CQIC). The best known coding scheme for communicating over CQICs is based on unstructured random codes and employs the techniques of message splitting and superposition coding. For classical $3-$user interference channels (ICs), it has been proven that coding techniques based on coset codes - codes possessing algebraic closure properties - strictly outperform all coding techniques based on unstructured codes. In this work, we develop analogous techniques based on coset codes for $3$to$1-$CQICs - a subclass of $3-$user CQICs. We analyze its performance and derive a new inner bound to the capacity region of $3$to$1-$CQICs that subsume the current known largest and strictly enlarges the same for identified examples. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2103.03978v1-abstract-full').style.display = 'none'; document.getElementById('2103.03978v1-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 March, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 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">18 pages. arXiv admin note: text overlap with arXiv:2103.02082</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2103.02082">arXiv:2103.02082</a> <span> [<a href="https://arxiv.org/pdf/2103.02082">pdf</a>, <a href="https://arxiv.org/ps/2103.02082">ps</a>, <a href="https://arxiv.org/format/2103.02082">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="Quantum Physics">quant-ph</span> </div> </div> <p class="title is-5 mathjax"> Computing Sum of Sources over a Classical-Quantum MAC </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Atif%2C+T+A">Touheed Anwar Atif</a>, <a href="/search/cs?searchtype=author&query=Padakandla%2C+A">Arun Padakandla</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="2103.02082v1-abstract-short" style="display: inline;"> We consider the problem of communicating a general bivariate function of two classical sources observed at the encoders of a classical-quantum multiple access channel. Building on the techniques developed for the case of a classical channel, we propose and analyze a coding scheme based on coset codes. The proposed technique enables the decoder recover the desired function without recovering the so… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2103.02082v1-abstract-full').style.display = 'inline'; document.getElementById('2103.02082v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2103.02082v1-abstract-full" style="display: none;"> We consider the problem of communicating a general bivariate function of two classical sources observed at the encoders of a classical-quantum multiple access channel. Building on the techniques developed for the case of a classical channel, we propose and analyze a coding scheme based on coset codes. The proposed technique enables the decoder recover the desired function without recovering the sources themselves. We derive a new set of sufficient conditions that are weaker than the current known for identified examples. This work is based on a new ensemble of coset codes that are proven to achieve the capacity of a classical-quantum point-to-point channel. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2103.02082v1-abstract-full').style.display = 'none'; document.getElementById('2103.02082v1-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 March, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 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">13 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/2101.02360">arXiv:2101.02360</a> <span> [<a href="https://arxiv.org/pdf/2101.02360">pdf</a>, <a href="https://arxiv.org/ps/2101.02360">ps</a>, <a href="https://arxiv.org/format/2101.02360">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="Quantum Physics">quant-ph</span> </div> </div> <p class="title is-5 mathjax"> Distributed Quantum Faithful Simulation and Function Computation Using Algebraic Structured Measurements </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Atif%2C+T+A">Touheed Anwar Atif</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="2101.02360v3-abstract-short" style="display: inline;"> In this work, we consider the task of faithfully simulating a quantum measurement, acting on a joint bipartite quantum state, in a distributed manner. In the distributed setup, the constituent sub-systems of the joint quantum state are measured by two agents, Alice and Bob. A third agent, Charlie receives the measurement outcomes sent by Alice and Bob. Charlie uses local and pairwise shared random… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2101.02360v3-abstract-full').style.display = 'inline'; document.getElementById('2101.02360v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2101.02360v3-abstract-full" style="display: none;"> In this work, we consider the task of faithfully simulating a quantum measurement, acting on a joint bipartite quantum state, in a distributed manner. In the distributed setup, the constituent sub-systems of the joint quantum state are measured by two agents, Alice and Bob. A third agent, Charlie receives the measurement outcomes sent by Alice and Bob. Charlie uses local and pairwise shared randomness to compute a bivariate function of the measurement outcomes. The objective of three agents is to faithfully simulate the given distributed quantum measurement acting on the given quantum state while minimizing the communication and shared randomness rates. We demonstrate a new achievable information-theoretic rate-region that exploits the bivariate function using random structured POVMs based on asymptotically good algebraic codes. The algebraic structure of these codes is matched to that of the bivariate function that models the action of Charlie. The conventional approach for this class of problems has been to reconstruct individual measurement outcomes corresponding to Alice and Bob, at Charlie, and then compute the bivariate function, achieved using mutually independent approximating POVMs based on random unstructured codes. In the present approach, using algebraic structured POVMs, the computation is performed on the fly, thus obviating the need to reconstruct individual measurement outcomes at Charlie. Using this, we show that a strictly larger rate region can be achieved. One of the challenges in analyzing these structured POVMs is that they exhibit only pairwise independence and induce only uniform single-letter distributions. To address this, we use nesting of algebraic codes and develop a covering lemma applicable to pairwise-independent POVM ensembles. Combining these techniques, we provide a multi-party distributed faithful simulation and function computation protocol. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2101.02360v3-abstract-full').style.display = 'none'; document.getElementById('2101.02360v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 14 October, 2021; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 6 January, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 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">31 pages, 2 figures, 3 examples</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2012.13977">arXiv:2012.13977</a> <span> [<a href="https://arxiv.org/pdf/2012.13977">pdf</a>, <a href="https://arxiv.org/format/2012.13977">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Capacity-achieving Polar-based LDGM Codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Pang%2C+J+C">James Chin-Jen Pang</a>, <a href="/search/cs?searchtype=author&query=Mahdavifar%2C+H">Hessam Mahdavifar</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="2012.13977v2-abstract-short" style="display: inline;"> In this paper, we study codes with sparse generator matrices. More specifically, low-density generator matrix (LDGM) codes with a certain constraint on the weight of the columns in the generator matrix are considered. In this paper, it is first shown that when a BMS channel W and a constant s>0 are given, there exists a polarization kernel such that the corresponding polar code is capacity-achievi… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2012.13977v2-abstract-full').style.display = 'inline'; document.getElementById('2012.13977v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2012.13977v2-abstract-full" style="display: none;"> In this paper, we study codes with sparse generator matrices. More specifically, low-density generator matrix (LDGM) codes with a certain constraint on the weight of the columns in the generator matrix are considered. In this paper, it is first shown that when a BMS channel W and a constant s>0 are given, there exists a polarization kernel such that the corresponding polar code is capacity-achieving and the column weights of the generator matrix (GM) are bounded from above by $N^s$. Then, a general construction based on a concatenation of polar codes and a rate-$1$ code, and a new column-splitting algorithm that guarantees a much sparser GM, is given. More specifically, for any BMS channel and any $蔚> 2蔚^*$, where $蔚^* \approx 0.085$, an existence of a sequence of capacity-achieving codes with all the GM column weights upper bounded by $(\log N)^{1+蔚}$ is shown. Furthermore, two coding schemes for BEC and BMS channels, based on a second column-splitting algorithm, are devised with low-complexity decoding that uses successive-cancellation. The second splitting algorithm allows for the use of a low-complexity decoder by preserving the reliability of the bit-channels observed by the source bits, and by increasing the code block length. The concatenation-based construction can also be applied to the random linear code ensemble to yield capacity-achieving codes with all the GM column weights being $O(\log N)$ and with (large-degree) polynomial decoding complexity. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2012.13977v2-abstract-full').style.display = 'none'; document.getElementById('2012.13977v2-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, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 27 December, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 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">Extended version, now includes moderate-block length comparison with the RLE. arXiv admin note: text overlap with arXiv:2001.11986</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2004.03651">arXiv:2004.03651</a> <span> [<a href="https://arxiv.org/pdf/2004.03651">pdf</a>, <a href="https://arxiv.org/format/2004.03651">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"> Source Coding for Synthesizing Correlated Randomness </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Atif%2C+T+A">Touheed Anwar Atif</a>, <a href="/search/cs?searchtype=author&query=Padakandla%2C+A">Arun Padakandla</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2004.03651v2-abstract-short" style="display: inline;"> We consider a scenario wherein two parties Alice and Bob are provided $X_{1}^{n}$ and $X_{2}^{n}$ -- samples that are IID from a PMF $P_{X_1 X_2}$. Alice and Bob can communicate to Charles over (noiseless) communication links of rate $R_1$ and $R_2$ respectively. Their goal is to enable Charles generate samples $Y^{n}$ such that the triple $(X_{1}^{n},X_{2}^{n},Y^{n})$ has a PMF that is close, in… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2004.03651v2-abstract-full').style.display = 'inline'; document.getElementById('2004.03651v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2004.03651v2-abstract-full" style="display: none;"> We consider a scenario wherein two parties Alice and Bob are provided $X_{1}^{n}$ and $X_{2}^{n}$ -- samples that are IID from a PMF $P_{X_1 X_2}$. Alice and Bob can communicate to Charles over (noiseless) communication links of rate $R_1$ and $R_2$ respectively. Their goal is to enable Charles generate samples $Y^{n}$ such that the triple $(X_{1}^{n},X_{2}^{n},Y^{n})$ has a PMF that is close, in total variation, to $\prod P_{X_1 X_2 Y}$. In addition, the three parties may posses pairwise shared common randomness at rates $C_1$ and $C_2$. We address the problem of characterizing the set of rate quadruples $(R_1,R_2,C_1,C_2)$ for which the above goal can be accomplished. We provide a set of sufficient conditions, i.e. an inner bound to the achievable rate region, and necessary conditions, i.e. an outer bound to the rate region for this three party setup. We provide a joint-typicality based random coding argument involving encoding and decoding operations to perform soft covering and a pertinent relaxation of the PMF requirement for the encoders. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2004.03651v2-abstract-full').style.display = 'none'; document.getElementById('2004.03651v2-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 April, 2021; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 7 April, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2020. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2001.11986">arXiv:2001.11986</a> <span> [<a href="https://arxiv.org/pdf/2001.11986">pdf</a>, <a href="https://arxiv.org/ps/2001.11986">ps</a>, <a href="https://arxiv.org/format/2001.11986">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Signal Processing">eess.SP</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Distributed, Parallel, and Cluster Computing">cs.DC</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> Capacity-achieving Polar-based LDGM Codes with Crowdsourcing Applications </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Pang%2C+J+C">James Chin-Jen Pang</a>, <a href="/search/cs?searchtype=author&query=Mahdavifar%2C+H">Hessam Mahdavifar</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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.11986v1-abstract-short" style="display: inline;"> In this paper we study codes with sparse generator matrices. More specifically, codes with a certain constraint on the weight of all the columns in the generator matrix are considered. The end result is the following. For any binary-input memoryless symmetric (BMS) channel and any epsilon > 2 epsilon*, where epsilon^* = \frac{1}{6}-\frac{5}{3}\log{\frac{4}{3}} \approx 0.085, we show an explicit se… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2001.11986v1-abstract-full').style.display = 'inline'; document.getElementById('2001.11986v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2001.11986v1-abstract-full" style="display: none;"> In this paper we study codes with sparse generator matrices. More specifically, codes with a certain constraint on the weight of all the columns in the generator matrix are considered. The end result is the following. For any binary-input memoryless symmetric (BMS) channel and any epsilon > 2 epsilon*, where epsilon^* = \frac{1}{6}-\frac{5}{3}\log{\frac{4}{3}} \approx 0.085, we show an explicit sequence of capacity-achieving codes with all the column wights of the generator matrix upper bounded by (\log N)^{1+epsilon}, where N is the code block length. The constructions are based on polar codes. Applications to crowdsourcing are also shown. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2001.11986v1-abstract-full').style.display = 'none'; document.getElementById('2001.11986v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 31 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">12 pages, 2 tables</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1906.10637">arXiv:1906.10637</a> <span> [<a href="https://arxiv.org/pdf/1906.10637">pdf</a>, <a href="https://arxiv.org/ps/1906.10637">ps</a>, <a href="https://arxiv.org/format/1906.10637">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> </div> </div> <p class="title is-5 mathjax"> Coding for Crowdsourced Classification with XOR Queries </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Pang%2C+J+C">James Chin-Jen Pang</a>, <a href="/search/cs?searchtype=author&query=Mahdavifar%2C+H">Hessam Mahdavifar</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="1906.10637v2-abstract-short" style="display: inline;"> This paper models the crowdsourced labeling/classification problem as a sparsely encoded source coding problem, where each query answer, regarded as a code bit, is the XOR of a small number of labels, as source information bits. In this paper we leverage the connections between this problem and well-studied codes with sparse representations for the channel coding problem to provide querying scheme… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1906.10637v2-abstract-full').style.display = 'inline'; document.getElementById('1906.10637v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1906.10637v2-abstract-full" style="display: none;"> This paper models the crowdsourced labeling/classification problem as a sparsely encoded source coding problem, where each query answer, regarded as a code bit, is the XOR of a small number of labels, as source information bits. In this paper we leverage the connections between this problem and well-studied codes with sparse representations for the channel coding problem to provide querying schemes with almost optimal number of queries, each of which involving only a constant number of labels. We also extend this scenario to the case where some workers can be unresponsive. For this case, we propose querying schemes where each query involves only log n items, where n is the total number of items to be labeled. Furthermore, we consider classification of two correlated labeling systems and provide two-stage querying schemes with almost optimal number of queries each involving a constant number of labels. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1906.10637v2-abstract-full').style.display = 'none'; document.getElementById('1906.10637v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 31 January, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 25 June, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 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">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/1906.08810">arXiv:1906.08810</a> <span> [<a href="https://arxiv.org/pdf/1906.08810">pdf</a>, <a href="https://arxiv.org/format/1906.08810">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 Achievable Rate-Distortion Region for Distributed Source Coding </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Shirani%2C+F">Farhad Shirani</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="1906.08810v2-abstract-short" style="display: inline;"> In this work, lossy distributed compression of pairs of correlated sources is considered. Conventionally, Shannon's random coding arguments -- using randomly generated unstructured codebooks whose blocklength is taken to be asymptotically large -- are used to derive achievability results. However, it was recently observed that in various multi-terminal communications scenarios, using random codes… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1906.08810v2-abstract-full').style.display = 'inline'; document.getElementById('1906.08810v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1906.08810v2-abstract-full" style="display: none;"> In this work, lossy distributed compression of pairs of correlated sources is considered. Conventionally, Shannon's random coding arguments -- using randomly generated unstructured codebooks whose blocklength is taken to be asymptotically large -- are used to derive achievability results. However, it was recently observed that in various multi-terminal communications scenarios, using random codes with constant finite blocklength may lead to improved achievable regions compared to the conventional approach. In other words, in some network communication scenarios, there is a finite optimal value in the blocklength of the randomly generated code used for distributed processing of information sources. Motivated by this, a coding scheme is proposed which consists of two codebook layers: i) the primary codebook which has constant finite blocklength, and ii) the secondary codebook whose blocklength is taken to be asymptotically large. The achievable region is analyzed in two steps. In the first step, a characterization of the achievable region is derived using information measures which are functions of multi-letter probability distributions. In the next step, a computable single-letter inner-bound to the achievable region is derived. It is shown through several examples that the resulting rate-distortion region is strictly larger than the Berger Tung achievable region. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1906.08810v2-abstract-full').style.display = 'none'; document.getElementById('1906.08810v2-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 October, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 20 June, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2019. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1905.04760">arXiv:1905.04760</a> <span> [<a href="https://arxiv.org/pdf/1905.04760">pdf</a>, <a href="https://arxiv.org/ps/1905.04760">ps</a>, <a href="https://arxiv.org/format/1905.04760">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"> Structured Mappings and Conferencing Common Information for Multiple-access Channels </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Heidari%2C+M">Mohsen Heidari</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="1905.04760v1-abstract-short" style="display: inline;"> In this work, we study two problems: three-user Multiple-Access Channel (MAC) with correlated sources, and MAC with Feedback (MAC-FB) with independent messages. For the first problem, we identify a structure in the joint probability distribution of discrete memoryless sources, and define a new common information called ``conferencing common information". We develop a multi-user joint-source channe… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1905.04760v1-abstract-full').style.display = 'inline'; document.getElementById('1905.04760v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1905.04760v1-abstract-full" style="display: none;"> In this work, we study two problems: three-user Multiple-Access Channel (MAC) with correlated sources, and MAC with Feedback (MAC-FB) with independent messages. For the first problem, we identify a structure in the joint probability distribution of discrete memoryless sources, and define a new common information called ``conferencing common information". We develop a multi-user joint-source channel coding methodology based on structured mappings to encode this common information efficiently and to transmit it over a MAC. We derive a new set of sufficient conditions for this coding strategy using single-letter information quantities for arbitrary sources and channel distributions. Next, we make a fundamental connection between this problem and the problem of communication of independent messages over three-user MAC-FB. In the latter problem, although the messages are independent to begin with, they become progressively correlated given the channel output feedback. Subsequent communication can be modeled as transmission of correlated sources over MAC. Exploiting this connection, we develop a new coding scheme for the problem. We characterize its performance using single-letter information quantities, and derive an inner bound to the capacity region. For both problems, we provide a set of examples where these rate regions are shown to be optimal. Moreover, we analytically prove that this performance is not achievable using random unstructured random mappings/codes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1905.04760v1-abstract-full').style.display = 'none'; document.getElementById('1905.04760v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 12 May, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 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">50 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/1901.10576">arXiv:1901.10576</a> <span> [<a href="https://arxiv.org/pdf/1901.10576">pdf</a>, <a href="https://arxiv.org/format/1901.10576">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"> Boolean Functions with Biased Inputs: Approximation and Noise Sensitivity </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Heidari%2C+M">Mohsen Heidari</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</a>, <a href="/search/cs?searchtype=author&query=Venkataramanan%2C+R">Ramji Venkataramanan</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.10576v2-abstract-short" style="display: inline;"> This paper considers the problem of approximating a Boolean function $f$ using another Boolean function from a specified class. Two classes of approximating functions are considered: $k$-juntas, and linear Boolean functions. The $n$ input bits of the function are assumed to be independently drawn from a distribution that may be biased. The quality of approximation is measured by the mismatch proba… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1901.10576v2-abstract-full').style.display = 'inline'; document.getElementById('1901.10576v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1901.10576v2-abstract-full" style="display: none;"> This paper considers the problem of approximating a Boolean function $f$ using another Boolean function from a specified class. Two classes of approximating functions are considered: $k$-juntas, and linear Boolean functions. The $n$ input bits of the function are assumed to be independently drawn from a distribution that may be biased. The quality of approximation is measured by the mismatch probability between $f$ and the approximating function $g$. For each class, the optimal approximation and the associated mismatch probability is characterized in terms of the biased Fourier expansion of $f$. The technique used to analyze the mismatch probability also yields an expression for the noise sensitivity of $f$ in terms of the biased Fourier coefficients, under a general i.i.d. input perturbation model. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1901.10576v2-abstract-full').style.display = 'none'; document.getElementById('1901.10576v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 8 July, 2019; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 29 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">5 pages, 2 figures, To appear in IEEE ISIT 2018</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.06788">arXiv:1901.06788</a> <span> [<a href="https://arxiv.org/pdf/1901.06788">pdf</a>, <a href="https://arxiv.org/format/1901.06788">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="Quantum Physics">quant-ph</span> </div> </div> <p class="title is-5 mathjax"> Faithful Simulation of Distributed Quantum Measurements with Applications in Distributed Rate-Distortion Theory </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Atif%2C+T+A">Touheed Anwar Atif</a>, <a href="/search/cs?searchtype=author&query=Heidari%2C+M">Mohsen Heidari</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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.06788v3-abstract-short" style="display: inline;"> We consider the task of faithfully simulating a distributed quantum measurement, wherein we provide a protocol for the three parties, Alice, Bob and Eve, to simulate a repeated action of a distributed quantum measurement using a pair of non-product approximating measurements by Alice and Bob, followed by a stochastic mapping at Eve. The objective of the protocol is to utilize minimum resources, in… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1901.06788v3-abstract-full').style.display = 'inline'; document.getElementById('1901.06788v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1901.06788v3-abstract-full" style="display: none;"> We consider the task of faithfully simulating a distributed quantum measurement, wherein we provide a protocol for the three parties, Alice, Bob and Eve, to simulate a repeated action of a distributed quantum measurement using a pair of non-product approximating measurements by Alice and Bob, followed by a stochastic mapping at Eve. The objective of the protocol is to utilize minimum resources, in terms of classical bits needed by Alice and Bob to communicate their measurement outcomes to Eve, and the common randomness shared among the three parties, while faithfully simulating independent repeated instances of the original measurement. To achieve this, we develop a mutual covering lemma and a technique for random binning of distributed quantum measurements, and, in turn, characterize a set of sufficient communication and common randomness rates required for asymptotic simulatability in terms of single-letter quantum information quantities. Furthermore, using these results we address a distributed quantum rate-distortion problem, where we characterize the achievable rate-distortion region through a single-letter inner bound. Finally, via a technique of single-letterization of multi-letter quantum information quantities, we provide an outer bound for the rate-distortion region. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1901.06788v3-abstract-full').style.display = 'none'; document.getElementById('1901.06788v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 14 August, 2020; <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">Submitted to IEEE Transactions on Information Theory</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1801.07777">arXiv:1801.07777</a> <span> [<a href="https://arxiv.org/pdf/1801.07777">pdf</a>, <a href="https://arxiv.org/format/1801.07777">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 The Reliability Function of Discrete Memoryless Multiple-Access Channel with Feedback </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Heidari%2C+M">Mohsen Heidari</a>, <a href="/search/cs?searchtype=author&query=Anastasopoulos%2C+A">Achilleas Anastasopoulos</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1801.07777v3-abstract-short" style="display: inline;"> We derive a lower and upper bound on the reliability function of discrete memoryless multiple-access channel (MAC) with noiseless feedback and variable-length codes (VLCs). For the upper-bound, we use proof techniques of Burnashev for the point-to-point case. Also, we adopt the techniques used to prove the converse for the feedback-capacity of MAC. For the lower-bound on the error exponent, we pre… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1801.07777v3-abstract-full').style.display = 'inline'; document.getElementById('1801.07777v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1801.07777v3-abstract-full" style="display: none;"> We derive a lower and upper bound on the reliability function of discrete memoryless multiple-access channel (MAC) with noiseless feedback and variable-length codes (VLCs). For the upper-bound, we use proof techniques of Burnashev for the point-to-point case. Also, we adopt the techniques used to prove the converse for the feedback-capacity of MAC. For the lower-bound on the error exponent, we present a coding scheme consisting of a data and a confirmation stage. In the data stage, any arbitrary feedback capacity-achieving code is used. In the confirmation stage, each transmitter sends one bit of information to the receiver using a pair of codebooks of size two, one for each transmitter. The codewords at this stage are selected randomly according to an appropriately optimized joint probability distribution. The bounds increase linearly with respect to a specific Euclidean distance measure defined between the transmission rate pair and the capacity boundary. The lower and upper bounds match for a class of MACs. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1801.07777v3-abstract-full').style.display = 'none'; document.getElementById('1801.07777v3-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 June, 2018; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 23 January, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2018. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1801.05294">arXiv:1801.05294</a> <span> [<a href="https://arxiv.org/pdf/1801.05294">pdf</a>, <a href="https://arxiv.org/ps/1801.05294">ps</a>, <a href="https://arxiv.org/format/1801.05294">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 Effective-length of Optimal Codes for Interference Channel with Feedback </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Heidari%2C+M">Mohsen Heidari</a>, <a href="/search/cs?searchtype=author&query=Shirani%2C+F">Farhad Shirani</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1801.05294v1-abstract-short" style="display: inline;"> In this paper, we investigate the necessity of finite blocklength codes in distributed transmission of independent message sets over channels with feedback. Previously, it was shown that finite effective length codes are necessary in distributed transmission and compression of sources. We provide two examples of three user interference channels with feedback where codes with asymptotically large e… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1801.05294v1-abstract-full').style.display = 'inline'; document.getElementById('1801.05294v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1801.05294v1-abstract-full" style="display: none;"> In this paper, we investigate the necessity of finite blocklength codes in distributed transmission of independent message sets over channels with feedback. Previously, it was shown that finite effective length codes are necessary in distributed transmission and compression of sources. We provide two examples of three user interference channels with feedback where codes with asymptotically large effective lengths are sub-optimal. As a result, we conclude that coded transmission using finite effective length codes is necessary to achieve optimality. We argue that the sub-optimal performance of large effective length codes is due to their inefficiency in preserving the correlation between the inputs to the distributed terminals in the communication system. This correlation is made available by the presence of feedback at the terminals and is used as a means for coordination between the terminals when using finite effective length coding strategies. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1801.05294v1-abstract-full').style.display = 'none'; document.getElementById('1801.05294v1-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> 16 January, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2018. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1705.00410">arXiv:1705.00410</a> <span> [<a href="https://arxiv.org/pdf/1705.00410">pdf</a>, <a href="https://arxiv.org/format/1705.00410">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 the Sub-optimality of Single-Letter Coding over Networks </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Shirani%2C+F">Farhad Shirani</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="1705.00410v1-abstract-short" style="display: inline;"> In this paper, we establish a new bound tying together the effective length and the maximum correlation between the outputs of an arbitrary pair of Boolean functions which operate on two sequences of correlated random variables. We derive a new upper bound on the correlation between the outputs of these functions. The upper bound may find applications in problems in many areas which deal with comm… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1705.00410v1-abstract-full').style.display = 'inline'; document.getElementById('1705.00410v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1705.00410v1-abstract-full" style="display: none;"> In this paper, we establish a new bound tying together the effective length and the maximum correlation between the outputs of an arbitrary pair of Boolean functions which operate on two sequences of correlated random variables. We derive a new upper bound on the correlation between the outputs of these functions. The upper bound may find applications in problems in many areas which deal with common information. We build upon Witsenhausen's result on maximum correlation. The present upper bound takes into account the effective length of the Boolean functions in characterizing the correlation. We use the new bound to characterize the communication-cooperation tradeoff in multi-terminal communications. We investigate binary block-codes (BBC). A BBC is defined as a vector of Boolean functions. We consider an ensemble of BBCs which is randomly generated using single-letter distributions. We characterize the vector of dependency spectrums of these BBCs. We use this vector to bound the correlation between the outputs of two distributed BBCs. Finally, the upper bound is used to show that the large blocklength single-letter coding schemes studied in the literature are sub-optimal in various multi-terminal communication settings. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1705.00410v1-abstract-full').style.display = 'none'; document.getElementById('1705.00410v1-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, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 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">arXiv admin note: substantial text overlap with arXiv:1702.01376, arXiv:1702.01353</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1702.05544">arXiv:1702.05544</a> <span> [<a href="https://arxiv.org/pdf/1702.05544">pdf</a>, <a href="https://arxiv.org/ps/1702.05544">ps</a>, <a href="https://arxiv.org/format/1702.05544">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 the Necessity of Structured Codes for Communications over MAC with Feedback </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Heidari%2C+M">Mohsen Heidari</a>, <a href="/search/cs?searchtype=author&query=Shirani%2C+F">Farhad Shirani</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="1702.05544v1-abstract-short" style="display: inline;"> The problem of three-user multiple-access channel (MAC) with noiseless feedback is investigated. A new coding strategy is presented. The coding scheme builds upon the natural extension of the Cover-Leung (CL) scheme; and uses quasi-linear codes. A new single-letter achievable rate region is derived. The new achievable region strictly contains the CL region. This is shown through an example. In thi… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1702.05544v1-abstract-full').style.display = 'inline'; document.getElementById('1702.05544v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1702.05544v1-abstract-full" style="display: none;"> The problem of three-user multiple-access channel (MAC) with noiseless feedback is investigated. A new coding strategy is presented. The coding scheme builds upon the natural extension of the Cover-Leung (CL) scheme; and uses quasi-linear codes. A new single-letter achievable rate region is derived. The new achievable region strictly contains the CL region. This is shown through an example. In this example, the coding scheme achieves optimality in terms of transmission rates. It is shown that any optimality achieving scheme for this example must have a specific algebraic structure. Particularly, the codebooks must be closed under binary addition. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1702.05544v1-abstract-full').style.display = 'none'; document.getElementById('1702.05544v1-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 February, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2017. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1702.02330">arXiv:1702.02330</a> <span> [<a href="https://arxiv.org/pdf/1702.02330">pdf</a>, <a href="https://arxiv.org/ps/1702.02330">ps</a>, <a href="https://arxiv.org/format/1702.02330">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 Achievable Rate Region for Multiple-Access Channel with States </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Heidari%2C+M">Mohsen Heidari</a>, <a href="/search/cs?searchtype=author&query=Shirani%2C+F">Farhad Shirani</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="1702.02330v1-abstract-short" style="display: inline;"> The problem of reliable communication over the multiple-access channel (MAC) with states is investigated. We propose a new coding scheme for this problem which uses quasi-group codes (QGC). We derive a new computable single-letter characterization of the achievable rate region. As an example, we investigate the problem of doubly-dirty MAC with modulo-$4$ addition. It is shown that the sum-rate… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1702.02330v1-abstract-full').style.display = 'inline'; document.getElementById('1702.02330v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1702.02330v1-abstract-full" style="display: none;"> The problem of reliable communication over the multiple-access channel (MAC) with states is investigated. We propose a new coding scheme for this problem which uses quasi-group codes (QGC). We derive a new computable single-letter characterization of the achievable rate region. As an example, we investigate the problem of doubly-dirty MAC with modulo-$4$ addition. It is shown that the sum-rate $R_1+R_2=1$ bits per channel use is achievable using the new scheme. Whereas, the natural extension of the Gel'fand-Pinsker scheme, sum-rates greater than $0.32$ are not achievable. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1702.02330v1-abstract-full').style.display = 'none'; document.getElementById('1702.02330v1-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 February, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 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">13 pages, ISIT 2017</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1702.01376">arXiv:1702.01376</a> <span> [<a href="https://arxiv.org/pdf/1702.01376">pdf</a>, <a href="https://arxiv.org/format/1702.01376">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> On the Sub-optimality of Single-letter Coding in Multi-terminal Communications </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Shirani%2C+F">Farhad Shirani</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="1702.01376v1-abstract-short" style="display: inline;"> We investigate binary block-codes (BBC). A BBC is defined as a vector of Boolean functions. We consider BBCs which are generated randomly, and using single-letter distributions. We characterize the vector of dependency spectrums of these BBCs. We use this vector to upper-bound the correlation between the outputs of two distributed BBCs. Finally, the upper-bound is used to show that the large block… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1702.01376v1-abstract-full').style.display = 'inline'; document.getElementById('1702.01376v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1702.01376v1-abstract-full" style="display: none;"> We investigate binary block-codes (BBC). A BBC is defined as a vector of Boolean functions. We consider BBCs which are generated randomly, and using single-letter distributions. We characterize the vector of dependency spectrums of these BBCs. We use this vector to upper-bound the correlation between the outputs of two distributed BBCs. Finally, the upper-bound is used to show that the large blocklength single-letter coding schemes in the literature are sub-optimal in some multiterminal communication settings. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1702.01376v1-abstract-full').style.display = 'none'; document.getElementById('1702.01376v1-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, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2017. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1702.01353">arXiv:1702.01353</a> <span> [<a href="https://arxiv.org/pdf/1702.01353">pdf</a>, <a href="https://arxiv.org/format/1702.01353">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 the Correlation between Boolean Functions of Sequences of Random Variables </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Shirani%2C+F">Farhad Shirani</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="1702.01353v1-abstract-short" style="display: inline;"> In this paper, we establish a new inequality tying together the effective length and the maximum correlation between the outputs of an arbitrary pair of Boolean functions which operate on two sequences of correlated random variables. We derive a new upper-bound on the correlation between the outputs of these functions. The upper-bound is useful in various disciplines which deal with common-informa… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1702.01353v1-abstract-full').style.display = 'inline'; document.getElementById('1702.01353v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1702.01353v1-abstract-full" style="display: none;"> In this paper, we establish a new inequality tying together the effective length and the maximum correlation between the outputs of an arbitrary pair of Boolean functions which operate on two sequences of correlated random variables. We derive a new upper-bound on the correlation between the outputs of these functions. The upper-bound is useful in various disciplines which deal with common-information. We build upon Witsenhausen's bound on maximum-correlation. The previous upper-bound did not take the effective length of the Boolean functions into account. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1702.01353v1-abstract-full').style.display = 'none'; document.getElementById('1702.01353v1-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">originally announced</span> February 2017. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1609.04360">arXiv:1609.04360</a> <span> [<a href="https://arxiv.org/pdf/1609.04360">pdf</a>, <a href="https://arxiv.org/format/1609.04360">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.7541614">10.1109/ISIT.2016.7541614 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> How to Compute Modulo Prime-Power Sums </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Heidari%2C+M">Mohsen Heidari</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="1609.04360v1-abstract-short" style="display: inline;"> The problem of computing modulo prime-power sums is investigated in distributed source coding as well as computation over Multiple-Access Channel (MAC). We build upon group codes and present a new class of codes called Quasi Group Codes (QGC). A QGC is a subset of a group code. These codes are not closed under the group addition. We investigate some properties of QGC's, and provide a packing and a… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1609.04360v1-abstract-full').style.display = 'inline'; document.getElementById('1609.04360v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1609.04360v1-abstract-full" style="display: none;"> The problem of computing modulo prime-power sums is investigated in distributed source coding as well as computation over Multiple-Access Channel (MAC). We build upon group codes and present a new class of codes called Quasi Group Codes (QGC). A QGC is a subset of a group code. These codes are not closed under the group addition. We investigate some properties of QGC's, and provide a packing and a covering bound. Next, we use these bounds to derived achievable rates for distributed source coding as well as computation over MAC. We show that strict improvements over the previously known schemes can be obtained using QGC's. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1609.04360v1-abstract-full').style.display = 'none'; document.getElementById('1609.04360v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 14 September, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2016. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> 2016 IEEE International Symposium on Information Theory (ISIT), Barcelona, 2016, pp. 1824-1828 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1603.05274">arXiv:1603.05274</a> <span> [<a href="https://arxiv.org/pdf/1603.05274">pdf</a>, <a href="https://arxiv.org/format/1603.05274">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"> New Sufficient Conditions for Multiple-Access Channel with Correlated Sources </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Heidari%2C+M">Mohsen Heidari</a>, <a href="/search/cs?searchtype=author&query=Shirani%2C+F">Farhad Shirani</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="1603.05274v1-abstract-short" style="display: inline;"> The problem of three-user Multiple-Access Channel (MAC) with correlated sources is investigated. An extension to the Cover-El Gamal-Salehi (CES) scheme is introduced. We use a combination of this scheme with linear codes and propose a new coding strategy. We derive new sufficient conditions to transmit correlated sources reliably. We consider an example of three-user MAC with binary inputs. Using… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1603.05274v1-abstract-full').style.display = 'inline'; document.getElementById('1603.05274v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1603.05274v1-abstract-full" style="display: none;"> The problem of three-user Multiple-Access Channel (MAC) with correlated sources is investigated. An extension to the Cover-El Gamal-Salehi (CES) scheme is introduced. We use a combination of this scheme with linear codes and propose a new coding strategy. We derive new sufficient conditions to transmit correlated sources reliably. We consider an example of three-user MAC with binary inputs. Using this example, we show strict improvements over the CES scheme. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1603.05274v1-abstract-full').style.display = 'none'; document.getElementById('1603.05274v1-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> 16 March, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2016. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1602.05287">arXiv:1602.05287</a> <span> [<a href="https://arxiv.org/pdf/1602.05287">pdf</a>, <a href="https://arxiv.org/format/1602.05287">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"> Trade-off between Communication and Cooperation in the Interference Channel </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Shirani%2C+F">F. Shirani</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. S. Pradhan</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="1602.05287v1-abstract-short" style="display: inline;"> We consider the problem of coding over the multi-user Interference Channel (IC). It is well-known that aligning the interfering signals results in improved achievable rates in certain setups involving more than two users. We argue that in the general interference problem, senders face a tradeoff between communicating their message to their corresponding decoder or cooperating with other users by a… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1602.05287v1-abstract-full').style.display = 'inline'; document.getElementById('1602.05287v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1602.05287v1-abstract-full" style="display: none;"> We consider the problem of coding over the multi-user Interference Channel (IC). It is well-known that aligning the interfering signals results in improved achievable rates in certain setups involving more than two users. We argue that in the general interference problem, senders face a tradeoff between communicating their message to their corresponding decoder or cooperating with other users by aligning their signals. Traditionally, interference alignment is carried out using structured codes such as linear codes and group codes. We show through an example that the usual structured coding schemes used for interference neutralization lack the necessary flexibility to optimize this tradeoff. Based on this intuition, we propose a new class of codes for this problem. We use the example to show that the application of these codes gives strict improvements in terms of achievable rates. Finally, we derive a new achievable region for the three user IC which strictly improves upon the previously known inner bounds for this problem. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1602.05287v1-abstract-full').style.display = 'none'; document.getElementById('1602.05287v1-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> 16 February, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2016. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1602.04521">arXiv:1602.04521</a> <span> [<a href="https://arxiv.org/pdf/1602.04521">pdf</a>, <a href="https://arxiv.org/format/1602.04521">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"> Quasi Linear Codes: Application to Point-to-Point and Multi-Terminal Source Coding </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Shirani%2C+F">F. Shirani</a>, <a href="/search/cs?searchtype=author&query=Heidari%2C+M">M. Heidari</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. S. Pradhan</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="1602.04521v1-abstract-short" style="display: inline;"> A new ensemble of structured codes is introduced. These codes are called Quasi Linear Codes (QLC). The QLC's are constructed by taking subsets of linear codes. They have a looser structure compared to linear codes and are not closed under addition. We argue that these codes provide gains in terms of achievable Rate-Distortions (RD) in different multi-terminal source coding problems. We derive the… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1602.04521v1-abstract-full').style.display = 'inline'; document.getElementById('1602.04521v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1602.04521v1-abstract-full" style="display: none;"> A new ensemble of structured codes is introduced. These codes are called Quasi Linear Codes (QLC). The QLC's are constructed by taking subsets of linear codes. They have a looser structure compared to linear codes and are not closed under addition. We argue that these codes provide gains in terms of achievable Rate-Distortions (RD) in different multi-terminal source coding problems. We derive the necessary covering bounds for analyzing the performance of QLC's. We then consider the Multiple-Descriptions (MD) problem, and prove through an example that the application of QLC's gives an improved achievable RD region for this problem. Finally, we derive an inner bound to the achievable RD region for the general MD problem which strictly contains all of the previous known achievable regions. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1602.04521v1-abstract-full').style.display = 'none'; document.getElementById('1602.04521v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 14 February, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2016. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1602.01911">arXiv:1602.01911</a> <span> [<a href="https://arxiv.org/pdf/1602.01911">pdf</a>, <a href="https://arxiv.org/format/1602.01911">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> </div> </div> <p class="title is-5 mathjax"> An Achievable Rate-Distortion Region for Multiple Descriptions Source Coding Based on Coset Codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Shirani%2C+F">Farhad Shirani</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="1602.01911v1-abstract-short" style="display: inline;"> We consider the problem of multiple descriptions (MD) source coding and propose new coding strategies involving both unstructured and structured coding layers. Previously, the most general achievable rate-distortion (RD) region for the $l$-descriptions problem was the Combinatorial Message Sharing with Binning (CMSB) region. The CMSB scheme utilizes unstructured quantizers and unstructured binning… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1602.01911v1-abstract-full').style.display = 'inline'; document.getElementById('1602.01911v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1602.01911v1-abstract-full" style="display: none;"> We consider the problem of multiple descriptions (MD) source coding and propose new coding strategies involving both unstructured and structured coding layers. Previously, the most general achievable rate-distortion (RD) region for the $l$-descriptions problem was the Combinatorial Message Sharing with Binning (CMSB) region. The CMSB scheme utilizes unstructured quantizers and unstructured binning. In the first part of the paper, we show that this strategy can be improved upon using more general unstructured quantizers and a more general unstructured binning method. In the second part, structured coding strategies are considered. First, structured coding strategies are developed by considering specific MD examples involving three or more descriptions. We show that application of structured quantizers results in strict RD improvements when there are more than two descriptions. Furthermore, we show that structured binning also yields improvements. These improvements are in addition to the ones derived in the first part of the paper. This suggests that structured coding is essential when coding over more than two descriptions. Using the ideas developed through these examples we provide a new unified coding strategy by considering several structured coding layers. Finally, we characterize its performance in the form of an inner bound to the optimal rate-distortion region using computable single-letter information quantities. The new RD region strictly contains all of the previous known achievable regions. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1602.01911v1-abstract-full').style.display = 'none'; document.getElementById('1602.01911v1-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, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2016. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1502.04367">arXiv:1502.04367</a> <span> [<a href="https://arxiv.org/pdf/1502.04367">pdf</a>, <a href="https://arxiv.org/format/1502.04367">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.2015.7282820">10.1109/ISIT.2015.7282820 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Coset codes for communicating over non-additive channels </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Padakandla%2C+A">Arun Padakandla</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="1502.04367v1-abstract-short" style="display: inline;"> We present a case for the use of codes possessing algebraic closure properties - coset codes - in developing coding techniques and characterizing achievable rate regions for generic multi-terminal channels. In particular, we consider three diverse communication scenarios - $3-$user interference channel (many-to-many), $3-$user broadcast channel (one-to-many), and multiple access with distributed s… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1502.04367v1-abstract-full').style.display = 'inline'; document.getElementById('1502.04367v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1502.04367v1-abstract-full" style="display: none;"> We present a case for the use of codes possessing algebraic closure properties - coset codes - in developing coding techniques and characterizing achievable rate regions for generic multi-terminal channels. In particular, we consider three diverse communication scenarios - $3-$user interference channel (many-to-many), $3-$user broadcast channel (one-to-many), and multiple access with distributed states (many-to-one) - and identify non-additive examples for which coset codes are analytically proven to yield strictly larger achievable rate regions than those achievable using iid codes. On the one hand, our findings motivate the need for multi-terminal information theory to step beyond iid codes. On the other, it encourages current research of linear code-based techniques to go beyond particular additive communication channels. Detailed proofs of our results are available in [1]-[3]. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1502.04367v1-abstract-full').style.display = 'none'; document.getElementById('1502.04367v1-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 February, 2015; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2015. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1403.4583">arXiv:1403.4583</a> <span> [<a href="https://arxiv.org/pdf/1403.4583">pdf</a>, <a href="https://arxiv.org/format/1403.4583">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.2016.2518171">10.1109/TIT.2016.2518171 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> An Achievable rate region for the $3-$user interference channel based on coset codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Padakandla%2C+A">Arun Padakandla</a>, <a href="/search/cs?searchtype=author&query=Sahebi%2C+A+G">Aria G. Sahebi</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="1403.4583v2-abstract-short" style="display: inline;"> We consider the problem of communication over a three user discrete memoryless interference channel ($3-$IC). The current known coding techniques for communicating over an arbitrary $3-$IC are based on message splitting, superposition coding and binning using independent and identically distributed (iid) random codebooks. In this work, we propose a new ensemble of codes - partitioned coset codes (… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1403.4583v2-abstract-full').style.display = 'inline'; document.getElementById('1403.4583v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1403.4583v2-abstract-full" style="display: none;"> We consider the problem of communication over a three user discrete memoryless interference channel ($3-$IC). The current known coding techniques for communicating over an arbitrary $3-$IC are based on message splitting, superposition coding and binning using independent and identically distributed (iid) random codebooks. In this work, we propose a new ensemble of codes - partitioned coset codes (PCC) - that possess an appropriate mix of empirical and algebraic closure properties. We develop coding techniques that exploit algebraic closure property of PCC to enable efficient communication over $3-$IC. We analyze the performance of the proposed coding technique to derive an achievable rate region for the general discrete $3-$IC. Additive and non-additive examples are identified for which the derived achievable rate region is the capacity, and moreover, strictly larger than current known largest achievable rate regions based on iid random codebooks. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1403.4583v2-abstract-full').style.display = 'none'; document.getElementById('1403.4583v2-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, 2015; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 18 March, 2014; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 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">New examples for which coset codes yield strictly larger achievable rate regions in comparison to those achievable using unstructured iid codes are identified. The issue of aligning interference at multiple receiver terminals addressed through an example. Revised submission to IEEE Trans. on Information Theory</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> 10.1109/TIT.2016.2518171 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1401.7006">arXiv:1401.7006</a> <span> [<a href="https://arxiv.org/pdf/1401.7006">pdf</a>, <a href="https://arxiv.org/format/1401.7006">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"> Polar Codes for Some Multi-terminal Communications Problems </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Sahebi%2C+A+G">Aria G. Sahebi</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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.7006v2-abstract-short" style="display: inline;"> It is shown that polar coding schemes achieve the known achievable rate regions for several multi-terminal communications problems including lossy distributed source coding, multiple access channels and multiple descriptions coding. The results are valid for arbitrary alphabet sizes (binary or nonbinary) and arbitrary distributions (symmetric or asymmetric). </span> <span class="abstract-full has-text-grey-dark mathjax" id="1401.7006v2-abstract-full" style="display: none;"> It is shown that polar coding schemes achieve the known achievable rate regions for several multi-terminal communications problems including lossy distributed source coding, multiple access channels and multiple descriptions coding. The results are valid for arbitrary alphabet sizes (binary or nonbinary) and arbitrary distributions (symmetric or asymmetric). <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1401.7006v2-abstract-full').style.display = 'none'; document.getElementById('1401.7006v2-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 April, 2014; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 25 January, 2014; <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">arXiv admin note: substantial text overlap with arXiv:1401.6482</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.6482">arXiv:1401.6482</a> <span> [<a href="https://arxiv.org/pdf/1401.6482">pdf</a>, <a href="https://arxiv.org/format/1401.6482">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"> Nested Polar Codes Achieve the Shannon Rate-Distortion Function and the Shannon Capacity </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Sahebi%2C+A+G">Aria G. Sahebi</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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.6482v1-abstract-short" style="display: inline;"> It is shown that nested polar codes achieve the Shannon rate-distortion function for arbitrary (binary or non-binary) discrete memoryless sources and the Shannon capacity of arbitrary discrete memoryless channels. </span> <span class="abstract-full has-text-grey-dark mathjax" id="1401.6482v1-abstract-full" style="display: none;"> It is shown that nested polar codes achieve the Shannon rate-distortion function for arbitrary (binary or non-binary) discrete memoryless sources and the Shannon capacity of arbitrary discrete memoryless channels. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1401.6482v1-abstract-full').style.display = 'none'; document.getElementById('1401.6482v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 24 January, 2014; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2014. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1305.1598">arXiv:1305.1598</a> <span> [<a href="https://arxiv.org/pdf/1305.1598">pdf</a>, <a href="https://arxiv.org/ps/1305.1598">ps</a>, <a href="https://arxiv.org/format/1305.1598">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"> Abelian Group Codes for Source Coding and Channel Coding </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Sahebi%2C+A+G">Aria G. Sahebi</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="1305.1598v1-abstract-short" style="display: inline;"> In this paper, we study the asymptotic performance of Abelian group codes for the lossy source coding problem for arbitrary discrete (finite alphabet) memoryless sources as well as the channel coding problem for arbitrary discrete (finite alphabet) memoryless channels. For the source coding problem, we derive an achievable rate-distortion function that is characterized in a single-letter informati… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1305.1598v1-abstract-full').style.display = 'inline'; document.getElementById('1305.1598v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1305.1598v1-abstract-full" style="display: none;"> In this paper, we study the asymptotic performance of Abelian group codes for the lossy source coding problem for arbitrary discrete (finite alphabet) memoryless sources as well as the channel coding problem for arbitrary discrete (finite alphabet) memoryless channels. For the source coding problem, we derive an achievable rate-distortion function that is characterized in a single-letter information-theoretic form using the ensemble of Abelian group codes. When the underlying group is a field, it simplifies to the symmetric rate-distortion function. Similarly, for the channel coding problem, we find an achievable rate characterized in a single-letter information-theoretic form using group codes. This simplifies to the symmetric capacity of the channel when the underlying group is a field. We compute the rate-distortion function and the achievable rate for several examples of sources and channels. Due to the non-symmetric nature of the sources and channels considered, our analysis uses a synergy of information theoretic and group-theoretic tools. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1305.1598v1-abstract-full').style.display = 'none'; document.getElementById('1305.1598v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 7 May, 2013; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2013. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1302.5021">arXiv:1302.5021</a> <span> [<a href="https://arxiv.org/pdf/1302.5021">pdf</a>, <a href="https://arxiv.org/ps/1302.5021">ps</a>, <a href="https://arxiv.org/format/1302.5021">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/JSAC.2013.130406">10.1109/JSAC.2013.130406 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Linear Coding Schemes for the Distributed Computation of Subspaces </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Lalitha%2C+V">V. Lalitha</a>, <a href="/search/cs?searchtype=author&query=Prakash%2C+N">N. Prakash</a>, <a href="/search/cs?searchtype=author&query=Vinodh%2C+K">K. Vinodh</a>, <a href="/search/cs?searchtype=author&query=Kumar%2C+P+V">P. Vijay Kumar</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="1302.5021v1-abstract-short" style="display: inline;"> Let $X_1, ..., X_m$ be a set of $m$ statistically dependent sources over the common alphabet $\mathbb{F}_q$, that are linearly independent when considered as functions over the sample space. We consider a distributed function computation setting in which the receiver is interested in the lossless computation of the elements of an $s$-dimensional subspace $W$ spanned by the elements of the row vect… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1302.5021v1-abstract-full').style.display = 'inline'; document.getElementById('1302.5021v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1302.5021v1-abstract-full" style="display: none;"> Let $X_1, ..., X_m$ be a set of $m$ statistically dependent sources over the common alphabet $\mathbb{F}_q$, that are linearly independent when considered as functions over the sample space. We consider a distributed function computation setting in which the receiver is interested in the lossless computation of the elements of an $s$-dimensional subspace $W$ spanned by the elements of the row vector $[X_1, \ldots, X_m]螕$ in which the $(m \times s)$ matrix $螕$ has rank $s$. A sequence of three increasingly refined approaches is presented, all based on linear encoders. The first approach uses a common matrix to encode all the sources and a Korner-Marton like receiver to directly compute $W$. The second improves upon the first by showing that it is often more efficient to compute a carefully chosen superspace $U$ of $W$. The superspace is identified by showing that the joint distribution of the $\{X_i\}$ induces a unique decomposition of the set of all linear combinations of the $\{X_i\}$, into a chain of subspaces identified by a normalized measure of entropy. This subspace chain also suggests a third approach, one that employs nested codes. For any joint distribution of the $\{X_i\}$ and any $W$, the sum-rate of the nested code approach is no larger than that under the Slepian-Wolf (SW) approach. Under the SW approach, $W$ is computed by first recovering each of the $\{X_i\}$. For a large class of joint distributions and subspaces $W$, the nested code approach is shown to improve upon SW. Additionally, a class of source distributions and subspaces are identified, for which the nested-code approach is sum-rate optimal. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1302.5021v1-abstract-full').style.display = 'none'; document.getElementById('1302.5021v1-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 February, 2013; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2013. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">To appear in IEEE Journal of Selected Areas in Communications (In-Network Computation: Exploring the Fundamental Limits), April 2013</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1301.5684">arXiv:1301.5684</a> <span> [<a href="https://arxiv.org/pdf/1301.5684">pdf</a>, <a href="https://arxiv.org/ps/1301.5684">ps</a>, <a href="https://arxiv.org/format/1301.5684">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.2013.6620605">10.1109/ISIT.2013.6620605 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Computing sum of sources over an arbitrary multiple access channel </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Padakandla%2C+A">Arun Padakandla</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="1301.5684v3-abstract-short" style="display: inline;"> The problem of computing sum of sources over a multiple access channel (MAC) is considered. Building on the technique of linear computation coding (LCC) proposed by Nazer and Gastpar [2007], we employ the ensemble of nested coset codes to derive a new set of sufficient conditions for computing the sum of sources over an \textit{arbitrary} MAC. The optimality of nested coset codes [Padakandla, Prad… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1301.5684v3-abstract-full').style.display = 'inline'; document.getElementById('1301.5684v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1301.5684v3-abstract-full" style="display: none;"> The problem of computing sum of sources over a multiple access channel (MAC) is considered. Building on the technique of linear computation coding (LCC) proposed by Nazer and Gastpar [2007], we employ the ensemble of nested coset codes to derive a new set of sufficient conditions for computing the sum of sources over an \textit{arbitrary} MAC. The optimality of nested coset codes [Padakandla, Pradhan 2011] enables this technique outperform LCC even for linear MAC with a structural match. Examples of nonadditive MAC for which the technique proposed herein outperforms separation and systematic based computation are also presented. Finally, this technique is enhanced by incorporating separation based strategy, leading to a new set of sufficient conditions for computing the sum over a MAC. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1301.5684v3-abstract-full').style.display = 'none'; document.getElementById('1301.5684v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 18 May, 2013; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 23 January, 2013; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2013. </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">Contains proof of the main theorem and a few minor corrections. Contents of this article have been accepted for presentation at ISIT2013</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1207.3146">arXiv:1207.3146</a> <span> [<a href="https://arxiv.org/pdf/1207.3146">pdf</a>, <a href="https://arxiv.org/format/1207.3146">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.2013.6620432">10.1109/ISIT.2013.6620432 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Achievable rate region for three user discrete broadcast channel based on coset codes </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Padakandla%2C+A">Arun Padakandla</a>, <a href="/search/cs?searchtype=author&query=Pradhan%2C+S+S">S. Sandeep Pradhan</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="1207.3146v6-abstract-short" style="display: inline;"> We present an achievable rate region for the general three user discrete memoryless broadcast channel, based on nested coset codes. We characterize 3-to-1 discrete broadcast channels, a class of broadcast channels for which the best known coding technique\footnote{We henceforth refer to this as Marton's coding for three user discrete broadcast channel.}, which is obtained by a natural generalizati… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1207.3146v6-abstract-full').style.display = 'inline'; document.getElementById('1207.3146v6-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1207.3146v6-abstract-full" style="display: none;"> We present an achievable rate region for the general three user discrete memoryless broadcast channel, based on nested coset codes. We characterize 3-to-1 discrete broadcast channels, a class of broadcast channels for which the best known coding technique\footnote{We henceforth refer to this as Marton's coding for three user discrete broadcast channel.}, which is obtained by a natural generalization of that proposed by Marton for the general two user discrete broadcast channel, is strictly sub-optimal. In particular, we identify a novel 3-to-1 discrete broadcast channel for which Marton's coding is \textit{analytically} proved to be strictly suboptimal. We present achievable rate regions for the general 3-to-1 discrete broadcast channels, based on nested coset codes, that strictly enlarge Marton's rate region for the aforementioned channel. We generalize this to present achievable rate region for the general three user discrete broadcast channel. Combining together Marton's coding and that proposed herein, we propose the best known coding technique, for a general three user discrete broadcast channel. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1207.3146v6-abstract-full').style.display = 'none'; document.getElementById('1207.3146v6-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, 2015; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 13 July, 2012; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2012. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">A non-additive 3-user discrete broadcast channel is identified for which achievable rate region based on coset codes is analytically proven to be strictly larger than that achievable using unstructured iid codes. This version is submitted to IEEE Transactions on Information Theory</span> </p> </li> </ol> <nav class="pagination is-small is-centered breathe-horizontal" role="navigation" aria-label="pagination"> <a href="" class="pagination-previous is-invisible">Previous </a> <a href="/search/?searchtype=author&query=Pradhan%2C+S+S&start=50" class="pagination-next" >Next </a> <ul class="pagination-list"> <li> <a href="/search/?searchtype=author&query=Pradhan%2C+S+S&start=0" class="pagination-link is-current" aria-label="Goto page 1">1 </a> </li> <li> <a href="/search/?searchtype=author&query=Pradhan%2C+S+S&start=50" class="pagination-link " aria-label="Page 2" aria-current="page">2 </a> </li> </ul> </nav> <div class="is-hidden-tablet">  <span class="help" style="display: inline-block;"><a href="https://github.com/arXiv/arxiv-search/releases">Search v0.5.6 released 2020-02-24</a>  </span> </div> </div> </main> <footer> <div class="columns is-desktop" role="navigation" aria-label="Secondary">  <div class="column"> <div class="columns"> <div class="column"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/about">About</a></li> <li><a href="https://info.arxiv.org/help">Help</a></li> </ul> </div> <div class="column"> <ul class="nav-spaced"> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>contact arXiv</title><desc>Click here to contact arXiv</desc><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg> <a href="https://info.arxiv.org/help/contact.html"> Contact</a> </li> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>subscribe to arXiv mailings</title><desc>Click here to subscribe</desc><path d="M476 3.2L12.5 270.6c-18.1 10.4-15.8 35.6 2.2 43.2L121 358.4l287.3-253.2c5.5-4.9 13.3 2.6 8.6 8.3L176 407v80.5c0 23.6 28.5 32.9 42.5 15.8L282 426l124.6 52.2c14.2 6 30.4-2.9 33-18.2l72-432C515 7.8 493.3-6.8 476 3.2z"/></svg> <a href="https://info.arxiv.org/help/subscribe"> Subscribe</a> </li> </ul> </div> </div> </div>   <div class="column"> <div class="columns"> <div class="column"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/help/license/index.html">Copyright</a></li> <li><a href="https://info.arxiv.org/help/policies/privacy_policy.html">Privacy Policy</a></li> </ul> </div> <div class="column sorry-app-links"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/help/web_accessibility.html">Web Accessibility Assistance</a></li> <li> <p class="help"> <a class="a11y-main-link" href="https://status.arxiv.org" target="_blank">arXiv Operational Status <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 256 512" class="icon filter-dark_grey" role="presentation"><path d="M224.3 273l-136 136c-9.4 9.4-24.6 9.4-33.9 0l-22.6-22.6c-9.4-9.4-9.4-24.6 0-33.9l96.4-96.4-96.4-96.4c-9.4-9.4-9.4-24.6 0-33.9L54.3 103c9.4-9.4 24.6-9.4 33.9 0l136 136c9.5 9.4 9.5 24.6.1 34z"/></svg></a><br> Get status notifications via <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/email/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg>email</a> or <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/slack/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512" class="icon filter-black" role="presentation"><path d="M94.12 315.1c0 25.9-21.16 47.06-47.06 47.06S0 341 0 315.1c0-25.9 21.16-47.06 47.06-47.06h47.06v47.06zm23.72 0c0-25.9 21.16-47.06 47.06-47.06s47.06 21.16 47.06 47.06v117.84c0 25.9-21.16 47.06-47.06 47.06s-47.06-21.16-47.06-47.06V315.1zm47.06-188.98c-25.9 0-47.06-21.16-47.06-47.06S139 32 164.9 32s47.06 21.16 47.06 47.06v47.06H164.9zm0 23.72c25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06H47.06C21.16 243.96 0 222.8 0 196.9s21.16-47.06 47.06-47.06H164.9zm188.98 47.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06h-47.06V196.9zm-23.72 0c0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06V79.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06V196.9zM283.1 385.88c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06v-47.06h47.06zm0-23.72c-25.9 0-47.06-21.16-47.06-47.06 0-25.9 21.16-47.06 47.06-47.06h117.84c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06H283.1z"/></svg>slack</a> </p> </li> </ul> </div> </div> </div>  </div> </footer> <script src="https://static.arxiv.org/static/base/1.0.0a5/js/member_acknowledgement.js"></script> </body> </html>

CINXE.COM

Search | arXiv e-print repository