CINXE.COM
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"/> <!-- new favicon config and versions by realfavicongenerator.net --> <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"> <!-- end favicon config --> <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> <!-- contains Cornell logo and sponsor statement --> <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> <!-- contains arXiv identity and search bar --> <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> <!-- closes identity --> <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–13 of 13 results for author: <span class="mathjax">Manna, B</span> </h1> </div> <div class="level-right is-hidden-mobile"> <!-- feedback for mobile is moved to footer --> <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=Manna%2C+B">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="Manna, B"> </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=Manna%2C+B&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="Manna, B"> <ul id="abstracts"><li><input checked id="abstracts-0" name="abstracts" type="radio" value="show"> <label for="abstracts-0">Show abstracts</label></li><li><input id="abstracts-1" name="abstracts" type="radio" value="hide"> <label for="abstracts-1">Hide abstracts</label></li></ul> </div> <div class="box field is-grouped is-grouped-multiline level-item"> <div class="control"> <span class="select is-small"> <select id="size" name="size"><option value="25">25</option><option selected value="50">50</option><option value="100">100</option><option value="200">200</option></select> </span> <label for="size">results per page</label>. </div> <div class="control"> <label for="order">Sort results by</label> <span class="select is-small"> <select id="order" name="order"><option selected value="-announced_date_first">Announcement date (newest first)</option><option value="announced_date_first">Announcement date (oldest first)</option><option value="-submitted_date">Submission date (newest first)</option><option value="submitted_date">Submission date (oldest first)</option><option value="">Relevance</option></select> </span> </div> <div class="control"> <button class="button is-small is-link">Go</button> </div> </div> </form> </div> </div> <ol class="breathe-horizontal" start="1"> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2407.02177">arXiv:2407.02177</a> <span> [<a href="https://arxiv.org/pdf/2407.02177">pdf</a>, <a href="https://arxiv.org/format/2407.02177">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> </div> </div> <p class="title is-5 mathjax"> Minsum Problem for Discrete and Weighted Set Flow on Dynamic Path Network </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Manna%2C+B">Bubai Manna</a>, <a href="/search/cs?searchtype=author&query=Roy%2C+B">Bodhayan Roy</a>, <a href="/search/cs?searchtype=author&query=Suppakitpaisarn%2C+V">Vorapong Suppakitpaisarn</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.02177v1-abstract-short" style="display: inline;"> In this research, we examine the minsum flow problem in dynamic path networks where flows are represented as discrete and weighted sets. The minsum flow problem has been widely studied for its relevance in finding evacuation routes during emergencies such as earthquakes. However, previous approaches often assume that individuals are separable and identical, which does not adequately account for th… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2407.02177v1-abstract-full').style.display = 'inline'; document.getElementById('2407.02177v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2407.02177v1-abstract-full" style="display: none;"> In this research, we examine the minsum flow problem in dynamic path networks where flows are represented as discrete and weighted sets. The minsum flow problem has been widely studied for its relevance in finding evacuation routes during emergencies such as earthquakes. However, previous approaches often assume that individuals are separable and identical, which does not adequately account for the fact that some groups of people, such as families, need to move together and that some groups may be more important than others. To address these limitations, we modify the minsum flow problem to support flows represented as discrete and weighted sets. We also propose a 2-approximation pseudo-polynomial time algorithm to solve this modified problem for path networks with uniform capacity. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2407.02177v1-abstract-full').style.display = 'none'; document.getElementById('2407.02177v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 2 July, 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/2405.18569">arXiv:2405.18569</a> <span> [<a href="https://arxiv.org/pdf/2405.18569">pdf</a>, <a href="https://arxiv.org/format/2405.18569">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Geometry">cs.CG</span> </div> </div> <p class="title is-5 mathjax"> Minimum Strict Consistent Subset in Paths, Spiders, Combs and Trees </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Manna%2C+B">Bubai Manna</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2405.18569v3-abstract-short" style="display: inline;"> Let G be a simple connected graph with vertex set V(G) and edge set E(G. Each vertex of V(G) is colored by a color from the set of colors {c_1, c_2,\dots, c_伪}. We take a subset S of V(G), such that for every vertex v in V(G)搂, at least one vertex of the same color is present in its set of nearest neighbors in S. We refer to such an S as a consistent subset (CS). The Minimum Consistent Subset (MCS… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.18569v3-abstract-full').style.display = 'inline'; document.getElementById('2405.18569v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2405.18569v3-abstract-full" style="display: none;"> Let G be a simple connected graph with vertex set V(G) and edge set E(G. Each vertex of V(G) is colored by a color from the set of colors {c_1, c_2,\dots, c_伪}. We take a subset S of V(G), such that for every vertex v in V(G)搂, at least one vertex of the same color is present in its set of nearest neighbors in S. We refer to such an S as a consistent subset (CS). The Minimum Consistent Subset (MCS) problem is the computation of a consistent subset of the minimum cardinality. It is established that MCS is NP-complete for general graphs, including planar graphs. The strict consistent subset is a variant of consistent subset problems. We take a subset S^{\prime} of V(G), such that for every vertex v in V(G)搂^{\prime}, all the vertices in its set of nearest neighbors in S^{\prime} have the same color as that of v. We refer to such an S^{\prime} as a strict consistent subset (SCS). The Minimum Strict Consistent Subset (MSCS) problem is the computation of a strict consistent subset of the minimum cardinality. We demonstrate that MSCS is NP-hard for general graphs using a reduction from dominating set problems. We construct a 2-approximation algorithm and a polynomial-time algorithm in trees. Lastly, we conclude the faster polynomial-time algorithms in paths, spiders, and combs. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.18569v3-abstract-full').style.display = 'none'; document.getElementById('2405.18569v3-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 July, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 28 May, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2405.14493">arXiv:2405.14493</a> <span> [<a href="https://arxiv.org/pdf/2405.14493">pdf</a>, <a href="https://arxiv.org/format/2405.14493">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Geometry">cs.CG</span> </div> </div> <p class="title is-5 mathjax"> Minimum Consistent Subset in Interval Graphs and Circle Graphs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Manna%2C+B">Bubai Manna</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2405.14493v1-abstract-short" style="display: inline;"> In a connected simple graph G = (V,E), each vertex of V is colored by a color from the set of colors C={c1, c2,..., c_伪}$. We take a subset S of V, such that for every vertex v in V搂, at least one vertex of the same color is present in its set of nearest neighbors in S. We refer to such a S as a consistent subset. The Minimum Consistent Subset (MCS) problem is the computation of a consistent subse… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.14493v1-abstract-full').style.display = 'inline'; document.getElementById('2405.14493v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2405.14493v1-abstract-full" style="display: none;"> In a connected simple graph G = (V,E), each vertex of V is colored by a color from the set of colors C={c1, c2,..., c_伪}$. We take a subset S of V, such that for every vertex v in V搂, at least one vertex of the same color is present in its set of nearest neighbors in S. We refer to such a S as a consistent subset. The Minimum Consistent Subset (MCS) problem is the computation of a consistent subset of the minimum size. It is established that MCS is NP-complete for general graphs, including planar graphs. We expand our study to interval graphs and circle graphs in an attempt to gain a complete understanding of the computational complexity of the \mcs problem across various graph classes. This work introduces an (4伪+ 2)- approximation algorithm for MCS in interval graphs where 伪is the number of colors in the interval graphs. Later, we show that in circle graphs, MCS is APX-hard. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.14493v1-abstract-full').style.display = 'none'; document.getElementById('2405.14493v1-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, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2404.16329">arXiv:2404.16329</a> <span> [<a href="https://arxiv.org/pdf/2404.16329">pdf</a>, <a href="https://arxiv.org/format/2404.16329">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Geometry">cs.CG</span> </div> </div> <p class="title is-5 mathjax"> On Approximating the Dynamic and Discrete Network Flow Problem </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Manna%2C+B">Bubai Manna</a>, <a href="/search/cs?searchtype=author&query=Roy%2C+B">Bodhayan Roy</a>, <a href="/search/cs?searchtype=author&query=Suppakitpaisarn%2C+V">Vorapong Suppakitpaisarn</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2404.16329v1-abstract-short" style="display: inline;"> We examine the dynamic network flow problem under the assumption that the flow consists of discrete units. The dynamic network flow problem is commonly addressed in the context of developing evacuation plans, where the flow is typically treated as a continuous quantity. However, real-world scenarios often involve moving groups, such as families, as single units. We demonstrate that solving the dyn… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2404.16329v1-abstract-full').style.display = 'inline'; document.getElementById('2404.16329v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2404.16329v1-abstract-full" style="display: none;"> We examine the dynamic network flow problem under the assumption that the flow consists of discrete units. The dynamic network flow problem is commonly addressed in the context of developing evacuation plans, where the flow is typically treated as a continuous quantity. However, real-world scenarios often involve moving groups, such as families, as single units. We demonstrate that solving the dynamic flow problem with this consideration is APX-hard. Conversely, we present a PTAS for instances where the base graph is a path with a constant number of nodes. We introduce a `ready time' constraint to the minsum bin packing problem, meaning certain items cannot be placed in specific bins, develop a PTAS for this modified problem, and apply our algorithms to the discrete and dynamic flow problem. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2404.16329v1-abstract-full').style.display = 'none'; document.getElementById('2404.16329v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 25 April, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2404.15487">arXiv:2404.15487</a> <span> [<a href="https://arxiv.org/pdf/2404.15487">pdf</a>, <a href="https://arxiv.org/format/2404.15487">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Geometry">cs.CG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Minimum Consistent Subset in Trees and Interval Graphs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Banik%2C+A">Aritra Banik</a>, <a href="/search/cs?searchtype=author&query=Das%2C+S">Sayani Das</a>, <a href="/search/cs?searchtype=author&query=Maheshwari%2C+A">Anil Maheshwari</a>, <a href="/search/cs?searchtype=author&query=Manna%2C+B">Bubai Manna</a>, <a href="/search/cs?searchtype=author&query=Nandy%2C+S+C">Subhas C Nandy</a>, <a href="/search/cs?searchtype=author&query=M%2C+K+P+K">Krishna Priya K M</a>, <a href="/search/cs?searchtype=author&query=Roy%2C+B">Bodhayan Roy</a>, <a href="/search/cs?searchtype=author&query=Roy%2C+S">Sasanka Roy</a>, <a href="/search/cs?searchtype=author&query=Sahu%2C+A">Abhishek Sahu</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2404.15487v1-abstract-short" style="display: inline;"> In the Minimum Consistent Subset (MCS) problem, we are presented with a connected simple undirected graph $G=(V,E)$, consisting of a vertex set $V$ of size $n$ and an edge set $E$. Each vertex in $V$ is assigned a color from the set $\{1,2,\ldots, c\}$. The objective is to determine a subset $V' \subseteq V$ with minimum possible cardinality, such that for every vertex $v \in V$, at least one of i… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2404.15487v1-abstract-full').style.display = 'inline'; document.getElementById('2404.15487v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2404.15487v1-abstract-full" style="display: none;"> In the Minimum Consistent Subset (MCS) problem, we are presented with a connected simple undirected graph $G=(V,E)$, consisting of a vertex set $V$ of size $n$ and an edge set $E$. Each vertex in $V$ is assigned a color from the set $\{1,2,\ldots, c\}$. The objective is to determine a subset $V' \subseteq V$ with minimum possible cardinality, such that for every vertex $v \in V$, at least one of its nearest neighbors in $V'$ (measured in terms of the hop distance) shares the same color as $v$. The decision problem, indicating whether there exists a subset $V'$ of cardinality at most $l$ for some positive integer $l$, is known to be NP-complete even for planar graphs. In this paper, we establish that the MCS problem for trees, when the number of colors $c$ is considered an input parameter, is NP-complete. We propose a fixed-parameter tractable (FPT) algorithm for MCS on trees running in $O(2^{6c}n^6)$ time, significantly improving the currently best-known algorithm whose running time is $O(2^{4c}n^{2c+3})$. In an effort to comprehensively understand the computational complexity of the MCS problem across different graph classes, we extend our investigation to interval graphs. We show that it remains NP-complete for interval graphs, thus enriching graph classes where MCS remains intractable. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2404.15487v1-abstract-full').style.display = 'none'; document.getElementById('2404.15487v1-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 April, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2312.15444">arXiv:2312.15444</a> <span> [<a href="https://arxiv.org/pdf/2312.15444">pdf</a>, <a href="https://arxiv.org/format/2312.15444">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Emerging Technologies">cs.ET</span> </div> </div> <p class="title is-5 mathjax"> Variation-Resilient FeFET-Based In-Memory Computing Leveraging Probabilistic Deep Learning </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Manna%2C+B">Bibhas Manna</a>, <a href="/search/cs?searchtype=author&query=Saha%2C+A">Arnob Saha</a>, <a href="/search/cs?searchtype=author&query=Jiang%2C+Z">Zhouhang Jiang</a>, <a href="/search/cs?searchtype=author&query=Ni%2C+K">Kai Ni</a>, <a href="/search/cs?searchtype=author&query=Sengupta%2C+A">Abhronil Sengupta</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="2312.15444v2-abstract-short" style="display: inline;"> Reliability issues stemming from device level non-idealities of non-volatile emerging technologies like ferroelectric field-effect transistors (FeFET), especially at scaled dimensions, cause substantial degradation in the accuracy of In-Memory crossbar-based AI systems. In this work, we present a variation-aware design technique to characterize the device level variations and to mitigate their imp… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2312.15444v2-abstract-full').style.display = 'inline'; document.getElementById('2312.15444v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2312.15444v2-abstract-full" style="display: none;"> Reliability issues stemming from device level non-idealities of non-volatile emerging technologies like ferroelectric field-effect transistors (FeFET), especially at scaled dimensions, cause substantial degradation in the accuracy of In-Memory crossbar-based AI systems. In this work, we present a variation-aware design technique to characterize the device level variations and to mitigate their impact on hardware accuracy employing a Bayesian Neural Network (BNN) approach. An effective conductance variation model is derived from the experimental measurements of cycle-to-cycle (C2C) and device-to-device (D2D) variations performed on FeFET devices fabricated using 28 nm high-$k$ metal gate technology. The variations were found to be a function of different conductance states within the given programming range, which sharply contrasts earlier efforts where a fixed variation dispersion was considered for all conductance values. Such variation characteristics formulated for three different device sizes at different read voltages were provided as prior variation information to the BNN to yield a more exact and reliable inference. Near-ideal accuracy for shallow networks (MLP5 and LeNet models) on the MNIST dataset and limited accuracy decline by $\sim$3.8-16.1% for deeper AlexNet models on CIFAR10 dataset under a wide range of variations corresponding to different device sizes and read voltages, demonstrates the efficacy of our proposed device-algorithm co-design technique. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2312.15444v2-abstract-full').style.display = 'none'; document.getElementById('2312.15444v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 13 March, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 24 December, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2303.02337">arXiv:2303.02337</a> <span> [<a href="https://arxiv.org/pdf/2303.02337">pdf</a>, <a href="https://arxiv.org/format/2303.02337">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Geometry">cs.CG</span> </div> </div> <p class="title is-5 mathjax"> Some results on Minimum Consistent Subsets of Trees </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Manna%2C+B">Bubai Manna</a>, <a href="/search/cs?searchtype=author&query=Roy%2C+B">Bodhayan Roy</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.02337v2-abstract-short" style="display: inline;"> For a graph G = (V,E) where each vertex is coloured by one of k colours, consider a subset C of V such that for each vertex v in V\C, its set of nearest neighbours in C contains at least one vertex of the same colour as v. Such a C is called a consistent subset (CS). Computing a consistent subset of the minimum size is called the Minimum Consistent Subset problem (MCS). MCS is known to be NP-compl… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2303.02337v2-abstract-full').style.display = 'inline'; document.getElementById('2303.02337v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2303.02337v2-abstract-full" style="display: none;"> For a graph G = (V,E) where each vertex is coloured by one of k colours, consider a subset C of V such that for each vertex v in V\C, its set of nearest neighbours in C contains at least one vertex of the same colour as v. Such a C is called a consistent subset (CS). Computing a consistent subset of the minimum size is called the Minimum Consistent Subset problem (MCS). MCS is known to be NP-complete for planar graphs. We propose a polynomial-time algorithm for finding a minimum consistent subset of a k-chromatic spider graph when k is a constant. We also show MCS remains NP-complete on trees. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2303.02337v2-abstract-full').style.display = 'none'; document.getElementById('2303.02337v2-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 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 4 March, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2004.01709">arXiv:2004.01709</a> <span> [<a href="https://arxiv.org/pdf/2004.01709">pdf</a>, <a href="https://arxiv.org/format/2004.01709">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Logic in Computer Science">cs.LO</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.23638/LMCS-16(4:17)2020">10.23638/LMCS-16(4:17)2020 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Ticking clocks as dependent right adjoints: Denotational semantics for clocked type theory </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Mannaa%2C+B">Bassel Mannaa</a>, <a href="/search/cs?searchtype=author&query=M%C3%B8gelberg%2C+R+E">Rasmus Ejlers M酶gelberg</a>, <a href="/search/cs?searchtype=author&query=Veltri%2C+N">Niccol貌 Veltri</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.01709v3-abstract-short" style="display: inline;"> Clocked Type Theory (CloTT) is a type theory for guarded recursion useful for programming with coinductive types, allowing productivity to be encoded in types, and for reasoning about advanced programming language features using an abstract form of step-indexing. CloTT has previously been shown to enjoy a number of syntactic properties including strong normalisation, canonicity and decidability of… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2004.01709v3-abstract-full').style.display = 'inline'; document.getElementById('2004.01709v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2004.01709v3-abstract-full" style="display: none;"> Clocked Type Theory (CloTT) is a type theory for guarded recursion useful for programming with coinductive types, allowing productivity to be encoded in types, and for reasoning about advanced programming language features using an abstract form of step-indexing. CloTT has previously been shown to enjoy a number of syntactic properties including strong normalisation, canonicity and decidability of the equational theory. In this paper we present a denotational semantics for CloTT useful, e.g., for studying future extensions of CloTT with constructions such as path types. The main challenge for constructing this model is to model the notion of ticks on a clock used in CloTT for coinductive reasoning about coinductive types. We build on a category previously used to model guarded recursion with multiple clocks. In this category there is an object of clocks but no object of ticks, and so tick-assumptions in a context can not be modelled using standard tools. Instead we model ticks using dependent right adjoint functors, a generalisation of the category theoretic notion of adjunction to the setting of categories with families. Dependent right adjoints are known to model Fitch-style modal types, but in the case of CloTT, the modal operators constitute a family indexed internally in the type theory by clocks. We model this family using a dependent right adjoint on the slice category over the object of clocks. Finally we show how to model the tick constant of CloTT using a semantic substitution. This work improves on a previous model by the first two named authors which not only had a flaw but was also considerably more complicated. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2004.01709v3-abstract-full').style.display = 'none'; document.getElementById('2004.01709v3-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 December, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 3 April, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 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">31 pages. Second version is a minor revision. arXiv admin note: text overlap with arXiv:1804.06687</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Logical Methods in Computer Science, Volume 16, Issue 4 (December 15, 2020) lmcs:6278 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1804.06687">arXiv:1804.06687</a> <span> [<a href="https://arxiv.org/pdf/1804.06687">pdf</a>, <a href="https://arxiv.org/format/1804.06687">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Logic in Computer Science">cs.LO</span> </div> </div> <p class="title is-5 mathjax"> The clocks they are adjunctions:Denotational semantics for Clocked Type Theory </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Mannaa%2C+B">Bassel Mannaa</a>, <a href="/search/cs?searchtype=author&query=M%C3%B8gelberg%2C+R+E">Rasmus Ejlers M酶gelberg</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1804.06687v1-abstract-short" style="display: inline;"> Clocked Type Theory (CloTT) is a type theory for guarded recursion useful for programming with coinductive types, allowing productivity to be encoded in types, and for reasoning about advanced programming language features using an abstract form of step-indexing. CloTT has previously been shown to enjoy a number of syntactic properties including strong normalisation, canonicity and decidability of… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1804.06687v1-abstract-full').style.display = 'inline'; document.getElementById('1804.06687v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1804.06687v1-abstract-full" style="display: none;"> Clocked Type Theory (CloTT) is a type theory for guarded recursion useful for programming with coinductive types, allowing productivity to be encoded in types, and for reasoning about advanced programming language features using an abstract form of step-indexing. CloTT has previously been shown to enjoy a number of syntactic properties including strong normalisation, canonicity and decidability of type checking. In this paper we present a denotational semantics for CloTT useful, e.g., for studying future extensions of CloTT with constructions such as path types. The main challenge for constructing this model is to model the notion of ticks used in CloTT for coinductive reasoning about coinductive types. We build on a category previously used to model guarded recursion, but in this category there is no object of ticks, so tick-assumptions in a context can not be modelled using standard tools. Instead we show how ticks can be modelled using adjoint functors, and how to model the tick constant using a semantic substitution. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1804.06687v1-abstract-full').style.display = 'none'; document.getElementById('1804.06687v1-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 April, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2018. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1804.05236">arXiv:1804.05236</a> <span> [<a href="https://arxiv.org/pdf/1804.05236">pdf</a>, <a href="https://arxiv.org/ps/1804.05236">ps</a>, <a href="https://arxiv.org/format/1804.05236">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Logic in Computer Science">cs.LO</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.1017/S0960129519000197">10.1017/S0960129519000197 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Modal Dependent Type Theory and Dependent Right Adjoints </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Birkedal%2C+L">Lars Birkedal</a>, <a href="/search/cs?searchtype=author&query=Clouston%2C+R">Ranald Clouston</a>, <a href="/search/cs?searchtype=author&query=Mannaa%2C+B">Bassel Mannaa</a>, <a href="/search/cs?searchtype=author&query=M%C3%B8gelberg%2C+R+E">Rasmus Ejlers M酶gelberg</a>, <a href="/search/cs?searchtype=author&query=Pitts%2C+A+M">Andrew M. Pitts</a>, <a href="/search/cs?searchtype=author&query=Spitters%2C+B">Bas Spitters</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1804.05236v3-abstract-short" style="display: inline;"> In recent years we have seen several new models of dependent type theory extended with some form of modal necessity operator, including nominal type theory, guarded and clocked type theory, and spatial and cohesive type theory. In this paper we study modal dependent type theory: dependent type theory with an operator satisfying (a dependent version of) the K-axiom of modal logic. We investigate bo… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1804.05236v3-abstract-full').style.display = 'inline'; document.getElementById('1804.05236v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1804.05236v3-abstract-full" style="display: none;"> In recent years we have seen several new models of dependent type theory extended with some form of modal necessity operator, including nominal type theory, guarded and clocked type theory, and spatial and cohesive type theory. In this paper we study modal dependent type theory: dependent type theory with an operator satisfying (a dependent version of) the K-axiom of modal logic. We investigate both semantics and syntax. For the semantics, we introduce categories with families with a dependent right adjoint (CwDRA) and show that the examples above can be presented as such. Indeed, we show that any finite limit category with an adjunction of endofunctors gives rise to a CwDRA via the local universe construction. For the syntax, we introduce a dependently typed extension of Fitch-style modal lambda-calculus, show that it can be interpreted in any CwDRA, and build a term model. We extend the syntax and semantics with universes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1804.05236v3-abstract-full').style.display = 'none'; document.getElementById('1804.05236v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 25 July, 2019; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 14 April, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2018. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Math. Struct. Comp. Sci. 30 (2020) 118-138 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1701.02571">arXiv:1701.02571</a> <span> [<a href="https://arxiv.org/pdf/1701.02571">pdf</a>, <a href="https://arxiv.org/ps/1701.02571">ps</a>, <a href="https://arxiv.org/format/1701.02571">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Logic in Computer Science">cs.LO</span> </div> </div> <p class="title is-5 mathjax"> Stack Semantics of Type Theory </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Coquand%2C+T">Thierry Coquand</a>, <a href="/search/cs?searchtype=author&query=Mannaa%2C+B">Bassel Mannaa</a>, <a href="/search/cs?searchtype=author&query=Ruch%2C+F">Fabian Ruch</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1701.02571v2-abstract-short" style="display: inline;"> We give a model of dependent type theory with one univalent universe and propositional truncation interpreting a type as a stack, generalising the groupoid model of type theory. As an application, we show that countable choice cannot be proved in dependent type theory with one univalent universe and propositional truncation. </span> <span class="abstract-full has-text-grey-dark mathjax" id="1701.02571v2-abstract-full" style="display: none;"> We give a model of dependent type theory with one univalent universe and propositional truncation interpreting a type as a stack, generalising the groupoid model of type theory. As an application, we show that countable choice cannot be proved in dependent type theory with one univalent universe and propositional truncation. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1701.02571v2-abstract-full').style.display = 'none'; document.getElementById('1701.02571v2-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 April, 2017; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 10 January, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2017. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">ACM Class:</span> F.3.2; F.4.1 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1602.04530">arXiv:1602.04530</a> <span> [<a href="https://arxiv.org/pdf/1602.04530">pdf</a>, <a href="https://arxiv.org/format/1602.04530">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Logic in Computer Science">cs.LO</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.23638/LMCS-13(3:10)2017">10.23638/LMCS-13(3:10)2017 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> The Independence of Markov's Principle in Type Theory </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Coquand%2C+T">Thierry Coquand</a>, <a href="/search/cs?searchtype=author&query=Mannaa%2C+B">Bassel Mannaa</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.04530v6-abstract-short" style="display: inline;"> In this paper, we show that Markov's principle is not derivable in dependent type theory with natural numbers and one universe. One way to prove this would be to remark that Markov's principle does not hold in a sheaf model of type theory over Cantor space, since Markov's principle does not hold for the generic point of this model. Instead we design an extension of type theory, which intuitively e… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1602.04530v6-abstract-full').style.display = 'inline'; document.getElementById('1602.04530v6-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1602.04530v6-abstract-full" style="display: none;"> In this paper, we show that Markov's principle is not derivable in dependent type theory with natural numbers and one universe. One way to prove this would be to remark that Markov's principle does not hold in a sheaf model of type theory over Cantor space, since Markov's principle does not hold for the generic point of this model. Instead we design an extension of type theory, which intuitively extends type theory by the addition of a generic point of Cantor space. We then show the consistency of this extension by a normalization argument. Markov's principle does not hold in this extension, and it follows that it cannot be proved in type theory. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1602.04530v6-abstract-full').style.display = 'none'; document.getElementById('1602.04530v6-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, 2017; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 14 February, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2016. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">ACM Class:</span> F.4.1 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Logical Methods in Computer Science, Volume 13, Issue 3 (August 15, 2017) lmcs:2565 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1511.09072">arXiv:1511.09072</a> <span> [<a href="https://arxiv.org/pdf/1511.09072">pdf</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Emerging Technologies">cs.ET</span> </div> </div> <p class="title is-5 mathjax"> High Sensitivity Biosensor using Injection Locked Spin Torque Nano-Oscillators </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Srimani%2C+T">Tathagata Srimani</a>, <a href="/search/cs?searchtype=author&query=Manna%2C+B">Bibhas Manna</a>, <a href="/search/cs?searchtype=author&query=Mukhopadhyay%2C+A+K">Anand Kumar Mukhopadhyay</a>, <a href="/search/cs?searchtype=author&query=Roy%2C+K">Kaushik Roy</a>, <a href="/search/cs?searchtype=author&query=Sharad%2C+M">Mrigank Sharad</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="1511.09072v1-abstract-short" style="display: inline;"> With ever increasing research on magnetic nano systems it is shown to have great potential in the areas of magnetic storage, biosensing, magnetoresistive insulation etc. In the field of biosensing specifically Spin Valve sensors coupled with Magnetic Nanolabels is showing great promise due to noise immunity and energy efficiency [1]. In this paper we present the application of injection locked bas… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1511.09072v1-abstract-full').style.display = 'inline'; document.getElementById('1511.09072v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1511.09072v1-abstract-full" style="display: none;"> With ever increasing research on magnetic nano systems it is shown to have great potential in the areas of magnetic storage, biosensing, magnetoresistive insulation etc. In the field of biosensing specifically Spin Valve sensors coupled with Magnetic Nanolabels is showing great promise due to noise immunity and energy efficiency [1]. In this paper we present the application of injection locked based Spin Torque Nano Oscillator (STNO) suitable for high resolution energy efficient labeled DNA Detection. The proposed STNO microarray consists of 20 such devices oscillating at different frequencies making it possible to multiplex all the signals using capacitive coupling. Frequency Division Multiplexing can be aided with Time division multiplexing to increase the device integration and decrease the readout time while maintaining the same efficiency in presence of constant input referred noise. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1511.09072v1-abstract-full').style.display = 'none'; document.getElementById('1511.09072v1-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 November, 2015; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2015. </p> </li> </ol> <div class="is-hidden-tablet"> <!-- feedback for mobile only --> <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"> <!-- MetaColumn 1 --> <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> <!-- end MetaColumn 1 --> <!-- MetaColumn 2 --> <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> <!-- end MetaColumn 2 --> </div> </footer> <script src="https://static.arxiv.org/static/base/1.0.0a5/js/member_acknowledgement.js"></script> </body> </html>