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–15 of 15 results for author: <span class="mathjax">Pavan, A</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=Pavan%2C+A">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="Pavan, A"> </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=Pavan%2C+A&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="Pavan, A"> <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/2411.05318">arXiv:2411.05318</a> <span> [<a href="https://arxiv.org/pdf/2411.05318">pdf</a>, <a href="https://arxiv.org/format/2411.05318">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="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Fairness in Monotone $k$-submodular Maximization: Algorithms and Applications </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Zhu%2C+Y">Yanhui Zhu</a>, <a href="/search/cs?searchtype=author&query=Basu%2C+S">Samik Basu</a>, <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A. Pavan</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="2411.05318v1-abstract-short" style="display: inline;"> Submodular optimization has become increasingly prominent in machine learning and fairness has drawn much attention. In this paper, we propose to study the fair $k$-submodular maximization problem and develop a $\frac{1}{3}$-approximation greedy algorithm with a running time of $\mathcal{O}(knB)$. To the best of our knowledge, our work is the first to incorporate fairness in the context of $k$-sub… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.05318v1-abstract-full').style.display = 'inline'; document.getElementById('2411.05318v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2411.05318v1-abstract-full" style="display: none;"> Submodular optimization has become increasingly prominent in machine learning and fairness has drawn much attention. In this paper, we propose to study the fair $k$-submodular maximization problem and develop a $\frac{1}{3}$-approximation greedy algorithm with a running time of $\mathcal{O}(knB)$. To the best of our knowledge, our work is the first to incorporate fairness in the context of $k$-submodular maximization, and our theoretical guarantee matches the best-known $k$-submodular maximization results without fairness constraints. In addition, we have developed a faster threshold-based algorithm that achieves a $(\frac{1}{3} - 蔚)$ approximation with $\mathcal{O}(\frac{kn}蔚 \log \frac{B}蔚)$ evaluations of the function $f$. Furthermore, for both algorithms, we provide approximation guarantees when the $k$-submodular function is not accessible but only can be approximately accessed. We have extensively validated our theoretical findings through empirical research and examined the practical implications of fairness. Specifically, we have addressed the question: ``What is the price of fairness?" through case studies on influence maximization with $k$ topics and sensor placement with $k$ types. The experimental results show that the fairness constraints do not significantly undermine the quality of solutions. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.05318v1-abstract-full').style.display = 'none'; document.getElementById('2411.05318v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 7 November, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 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">17 pages. To appear in IEEE BigData 2024</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2408.04620">arXiv:2408.04620</a> <span> [<a href="https://arxiv.org/pdf/2408.04620">pdf</a>, <a href="https://arxiv.org/format/2408.04620">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> </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.1145/3627673.3679651">10.1145/3627673.3679651 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Regularized Unconstrained Weakly Submodular Maximization </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Zhu%2C+Y">Yanhui Zhu</a>, <a href="/search/cs?searchtype=author&query=Basu%2C+S">Samik Basu</a>, <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A. Pavan</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="2408.04620v2-abstract-short" style="display: inline;"> Submodular optimization finds applications in machine learning and data mining. In this paper, we study the problem of maximizing functions of the form $h = f-c$, where $f$ is a monotone, non-negative, weakly submodular set function and $c$ is a modular function. We design a deterministic approximation algorithm that runs with ${O}(\frac{n}蔚\log \frac{n}{纬蔚})$ oracle calls to function $h$, and out… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2408.04620v2-abstract-full').style.display = 'inline'; document.getElementById('2408.04620v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2408.04620v2-abstract-full" style="display: none;"> Submodular optimization finds applications in machine learning and data mining. In this paper, we study the problem of maximizing functions of the form $h = f-c$, where $f$ is a monotone, non-negative, weakly submodular set function and $c$ is a modular function. We design a deterministic approximation algorithm that runs with ${O}(\frac{n}蔚\log \frac{n}{纬蔚})$ oracle calls to function $h$, and outputs a set ${S}$ such that $h({S}) \geq 纬(1-蔚)f(OPT)-c(OPT)-\frac{c(OPT)}{纬(1-蔚)}\log\frac{f(OPT)}{c(OPT)}$, where $纬$ is the submodularity ratio of $f$. Existing algorithms for this problem either admit a worse approximation ratio or have quadratic runtime. We also present an approximation ratio of our algorithm for this problem with an approximate oracle of $f$. We validate our theoretical results through extensive empirical evaluations on real-world applications, including vertex cover and influence diffusion problems for submodular utility function $f$, and Bayesian A-Optimal design for weakly submodular $f$. Our experimental results demonstrate that our algorithms efficiently achieve high-quality solutions. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2408.04620v2-abstract-full').style.display = 'none'; document.getElementById('2408.04620v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 18 August, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 8 August, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">To appear in CIKM'24. Full paper including omitted proofs</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Proceedings of the 33rd ACM International Conference on Information and Knowledge Management (CIKM 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.08255">arXiv:2405.08255</a> <span> [<a href="https://arxiv.org/pdf/2405.08255">pdf</a>, <a href="https://arxiv.org/ps/2405.08255">ps</a>, <a href="https://arxiv.org/format/2405.08255">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </div> </div> <p class="title is-5 mathjax"> Total Variation Distance for Product Distributions is $\#\mathsf{P}$-Complete </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Gayen%2C+S">Sutanu Gayen</a>, <a href="/search/cs?searchtype=author&query=Meel%2C+K+S">Kuldeep S. Meel</a>, <a href="/search/cs?searchtype=author&query=Myrisiotis%2C+D">Dimitrios Myrisiotis</a>, <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A. Pavan</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</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.08255v1-abstract-short" style="display: inline;"> We show that computing the total variation distance between two product distributions is $\#\mathsf{P}$-complete. This is in stark contrast with other distance measures such as Kullback-Leibler, Chi-square, and Hellinger, which tensorize over the marginals leading to efficient algorithms. </span> <span class="abstract-full has-text-grey-dark mathjax" id="2405.08255v1-abstract-full" style="display: none;"> We show that computing the total variation distance between two product distributions is $\#\mathsf{P}$-complete. This is in stark contrast with other distance measures such as Kullback-Leibler, Chi-square, and Hellinger, which tensorize over the marginals leading to efficient algorithms. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.08255v1-abstract-full').style.display = 'none'; document.getElementById('2405.08255v1-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 May, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">5 pages. An extended version of this paper appeared in the proceedings of IJCAI 2023, under the title "On approximating total variation distance" (see https://www.ijcai.org/proceedings/2023/387 and arXiv:2206.07209)</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2405.05942">arXiv:2405.05942</a> <span> [<a href="https://arxiv.org/pdf/2405.05942">pdf</a>, <a href="https://arxiv.org/format/2405.05942">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> </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.24963/ijcai.2024/783">10.24963/ijcai.2024/783 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Improved Evolutionary Algorithms for Submodular Maximization with Cost Constraints </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Zhu%2C+Y">Yanhui Zhu</a>, <a href="/search/cs?searchtype=author&query=Basu%2C+S">Samik Basu</a>, <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A Pavan</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.05942v2-abstract-short" style="display: inline;"> We present an evolutionary algorithm evo-SMC for the problem of Submodular Maximization under Cost constraints (SMC). Our algorithm achieves $1/2$-approximation with a high probability $1-1/n$ within $\mathcal{O}(n^2K_尾)$ iterations, where $K_尾$ denotes the maximum size of a feasible solution set with cost constraint $尾$. To the best of our knowledge, this is the best approximation guarantee offer… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.05942v2-abstract-full').style.display = 'inline'; document.getElementById('2405.05942v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2405.05942v2-abstract-full" style="display: none;"> We present an evolutionary algorithm evo-SMC for the problem of Submodular Maximization under Cost constraints (SMC). Our algorithm achieves $1/2$-approximation with a high probability $1-1/n$ within $\mathcal{O}(n^2K_尾)$ iterations, where $K_尾$ denotes the maximum size of a feasible solution set with cost constraint $尾$. To the best of our knowledge, this is the best approximation guarantee offered by evolutionary algorithms for this problem. We further refine evo-SMC, and develop st-evo-SMC. This stochastic version yields a significantly faster algorithm while maintaining the approximation ratio of $1/2$, with probability $1-蔚$. The required number of iterations reduces to $\mathcal{O}(nK_尾\log{(1/蔚)}/p)$, where the user defined parameters $p \in (0,1]$ represents the stochasticity probability, and $蔚\in (0,1]$ denotes the error threshold. Finally, the empirical evaluations carried out through extensive experimentation substantiate the efficiency and effectiveness of our proposed algorithms. Our algorithms consistently outperform existing methods, producing higher-quality solutions. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2405.05942v2-abstract-full').style.display = 'none'; document.getElementById('2405.05942v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 18 August, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 9 May, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">IJCAI 2024; 24 pages; including appendix</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-2024) </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2309.09134">arXiv:2309.09134</a> <span> [<a href="https://arxiv.org/pdf/2309.09134">pdf</a>, <a href="https://arxiv.org/ps/2309.09134">ps</a>, <a href="https://arxiv.org/format/2309.09134">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="Discrete Mathematics">cs.DM</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"> Total Variation Distance Meets Probabilistic Inference </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Gayen%2C+S">Sutanu Gayen</a>, <a href="/search/cs?searchtype=author&query=Meel%2C+K+S">Kuldeep S. Meel</a>, <a href="/search/cs?searchtype=author&query=Myrisiotis%2C+D">Dimitrios Myrisiotis</a>, <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A. Pavan</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</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.09134v2-abstract-short" style="display: inline;"> In this paper, we establish a novel connection between total variation (TV) distance estimation and probabilistic inference. In particular, we present an efficient, structure-preserving reduction from relative approximation of TV distance to probabilistic inference over directed graphical models. This reduction leads to a fully polynomial randomized approximation scheme (FPRAS) for estimating TV d… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2309.09134v2-abstract-full').style.display = 'inline'; document.getElementById('2309.09134v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2309.09134v2-abstract-full" style="display: none;"> In this paper, we establish a novel connection between total variation (TV) distance estimation and probabilistic inference. In particular, we present an efficient, structure-preserving reduction from relative approximation of TV distance to probabilistic inference over directed graphical models. This reduction leads to a fully polynomial randomized approximation scheme (FPRAS) for estimating TV distances between same-structure distributions over any class of Bayes nets for which there is an efficient probabilistic inference algorithm. In particular, it leads to an FPRAS for estimating TV distances between distributions that are defined over a common Bayes net of small treewidth. Prior to this work, such approximation schemes only existed for estimating TV distances between product distributions. Our approach employs a new notion of $partial$ couplings of high-dimensional distributions, which might be of independent interest. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2309.09134v2-abstract-full').style.display = 'none'; document.getElementById('2309.09134v2-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 July, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 16 September, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 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">25 pages. This work has been accepted for presentation at the International Conference on Machine Learning (ICML) 2024</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2304.04837">arXiv:2304.04837</a> <span> [<a href="https://arxiv.org/pdf/2304.04837">pdf</a>, <a href="https://arxiv.org/format/2304.04837">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link 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> <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"> Geometry of Rounding: Near Optimal Bounds and a New Neighborhood Sperner's Lemma </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Woude%2C+J+V">Jason Vander Woude</a>, <a href="/search/cs?searchtype=author&query=Dixon%2C+P">Peter Dixon</a>, <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A. Pavan</a>, <a href="/search/cs?searchtype=author&query=Radcliffe%2C+J">Jamie Radcliffe</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2304.04837v1-abstract-short" style="display: inline;"> A partition $\mathcal{P}$ of $\mathbb{R}^d$ is called a $(k,\varepsilon)$-secluded partition if, for every $\vec{p} \in \mathbb{R}^d$, the ball $\overline{B}_{\infty}(\varepsilon, \vec{p})$ intersects at most $k$ members of $\mathcal{P}$. A goal in designing such secluded partitions is to minimize $k$ while making $\varepsilon$ as large as possible. This partition problem has connections to a dive… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2304.04837v1-abstract-full').style.display = 'inline'; document.getElementById('2304.04837v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2304.04837v1-abstract-full" style="display: none;"> A partition $\mathcal{P}$ of $\mathbb{R}^d$ is called a $(k,\varepsilon)$-secluded partition if, for every $\vec{p} \in \mathbb{R}^d$, the ball $\overline{B}_{\infty}(\varepsilon, \vec{p})$ intersects at most $k$ members of $\mathcal{P}$. A goal in designing such secluded partitions is to minimize $k$ while making $\varepsilon$ as large as possible. This partition problem has connections to a diverse range of topics, including deterministic rounding schemes, pseudodeterminism, replicability, as well as Sperner/KKM-type results. In this work, we establish near-optimal relationships between $k$ and $\varepsilon$. We show that, for any bounded measure partitions and for any $d\geq 1$, it must be that $k\geq(1+2\varepsilon)^d$. Thus, when $k=k(d)$ is restricted to ${\rm poly}(d)$, it follows that $\varepsilon=\varepsilon(d)\in O\left(\frac{\ln d}{d}\right)$. This bound is tight up to log factors, as it is known that there exist secluded partitions with $k(d)=d+1$ and $\varepsilon(d)=\frac{1}{2d}$. We also provide new constructions of secluded partitions that work for a broad spectrum of $k(d)$ and $\varepsilon(d)$ parameters. Specifically, we prove that, for any $f:\mathbb{N}\rightarrow\mathbb{N}$, there is a secluded partition with $k(d)=(f(d)+1)^{\lceil\frac{d}{f(d)}\rceil}$ and $\varepsilon(d)=\frac{1}{2f(d)}$. These new partitions are optimal up to $O(\log d)$ factors for various choices of $k(d)$ and $\varepsilon(d)$. Based on the lower bound result, we establish a new neighborhood version of Sperner's lemma over hypercubes, which is of independent interest. In addition, we prove a no-free-lunch theorem about the limitations of rounding schemes in the context of pseudodeterministic/replicable algorithms. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2304.04837v1-abstract-full').style.display = 'none'; document.getElementById('2304.04837v1-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 April, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">ACM Class:</span> G.2.1; F.1.3 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2304.02240">arXiv:2304.02240</a> <span> [<a href="https://arxiv.org/pdf/2304.02240">pdf</a>, <a href="https://arxiv.org/ps/2304.02240">ps</a>, <a href="https://arxiv.org/format/2304.02240">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="Discrete Mathematics">cs.DM</span> </div> </div> <p class="title is-5 mathjax"> List and Certificate Complexities in Replicable Learning </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Dixon%2C+P">Peter Dixon</a>, <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A. Pavan</a>, <a href="/search/cs?searchtype=author&query=Woude%2C+J+V">Jason Vander Woude</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2304.02240v1-abstract-short" style="display: inline;"> We investigate replicable learning algorithms. Ideally, we would like to design algorithms that output the same canonical model over multiple runs, even when different runs observe a different set of samples from the unknown data distribution. In general, such a strong notion of replicability is not achievable. Thus we consider two feasible notions of replicability called list replicability and ce… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2304.02240v1-abstract-full').style.display = 'inline'; document.getElementById('2304.02240v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2304.02240v1-abstract-full" style="display: none;"> We investigate replicable learning algorithms. Ideally, we would like to design algorithms that output the same canonical model over multiple runs, even when different runs observe a different set of samples from the unknown data distribution. In general, such a strong notion of replicability is not achievable. Thus we consider two feasible notions of replicability called list replicability and certificate replicability. Intuitively, these notions capture the degree of (non) replicability. We design algorithms for certain learning problems that are optimal in list and certificate complexity. We establish matching impossibility results. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2304.02240v1-abstract-full').style.display = 'none'; document.getElementById('2304.02240v1-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 April, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">ACM Class:</span> I.2.6; G.2 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2302.12937">arXiv:2302.12937</a> <span> [<a href="https://arxiv.org/pdf/2302.12937">pdf</a>, <a href="https://arxiv.org/ps/2302.12937">ps</a>, <a href="https://arxiv.org/format/2302.12937">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> <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="Databases">cs.DB</span> </div> </div> <p class="title is-5 mathjax"> Constraint Optimization over Semirings </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A. Pavan</a>, <a href="/search/cs?searchtype=author&query=Meel%2C+K+S">Kuldeep S. Meel</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</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.12937v1-abstract-short" style="display: inline;"> Interpretations of logical formulas over semirings have applications in various areas of computer science including logic, AI, databases, and security. Such interpretations provide richer information beyond the truth or falsity of a statement. Examples of such semirings include Viterbi semiring, min-max or access control semiring, tropical semiring, and fuzzy semiring. The present work investiga… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.12937v1-abstract-full').style.display = 'inline'; document.getElementById('2302.12937v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2302.12937v1-abstract-full" style="display: none;"> Interpretations of logical formulas over semirings have applications in various areas of computer science including logic, AI, databases, and security. Such interpretations provide richer information beyond the truth or falsity of a statement. Examples of such semirings include Viterbi semiring, min-max or access control semiring, tropical semiring, and fuzzy semiring. The present work investigates the complexity of constraint optimization problems over semirings. The generic optimization problem we study is the following: Given a propositional formula $\varphi$ over $n$ variable and a semiring $(K,+,\cdot,0,1)$, find the maximum value over all possible interpretations of $\varphi$ over $K$. This can be seen as a generalization of the well-known satisfiability problem. A related problem is to find an interpretation that achieves the maximum value. In this work, we first focus on these optimization problems over the Viterbi semiring, which we call optConfVal and optConf. We show that for general propositional formulas in negation normal form, optConfVal and optConf are in ${\mathrm{FP}}^{\mathrm{NP}}$. We investigate optConf when the input formula $\varphi$ is represented as a CNF. For CNF formulae, we first derive an upper bound on optConfVal as a function of the number of maximum satisfiable clauses. In particular, we show that if $r$ is the maximum number of satisfiable clauses in a CNF formula with $m$ clauses, then its optConfVal is at most $1/4^{m-r}$. Building on this we establish that optConfVal for CNF formulae is hard for the complexity class ${\mathrm{FP}}^{\mathrm{NP}[\log]}$. We also design polynomial-time approximation algorithms and establish an inapproximability for optConfVal. We establish similar complexity results for these optimization problems over other semirings including tropical, fuzzy, and access control semirings. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.12937v1-abstract-full').style.display = 'none'; document.getElementById('2302.12937v1-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 February, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Appeared in AAAI 23</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">ACM Class:</span> F.4.1; F.1.3 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2211.02694">arXiv:2211.02694</a> <span> [<a href="https://arxiv.org/pdf/2211.02694">pdf</a>, <a href="https://arxiv.org/format/2211.02694">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </div> </div> <p class="title is-5 mathjax"> Geometry of Rounding </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Woude%2C+J+V">Jason Vander Woude</a>, <a href="/search/cs?searchtype=author&query=Dixon%2C+P">Peter Dixon</a>, <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A. Pavan</a>, <a href="/search/cs?searchtype=author&query=Radcliffe%2C+J">Jamie Radcliffe</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2211.02694v1-abstract-short" style="display: inline;"> Rounding has proven to be a fundamental tool in theoretical computer science. By observing that rounding and partitioning of $\mathbb{R}^d$ are equivalent, we introduce the following natural partition problem which we call the {\em secluded hypercube partition problem}: Given $k\in \mathbb{N}$ (ideally small) and $蔚>0$ (ideally large), is there a partition of $\mathbb{R}^d$ with unit hypercubes su… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2211.02694v1-abstract-full').style.display = 'inline'; document.getElementById('2211.02694v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2211.02694v1-abstract-full" style="display: none;"> Rounding has proven to be a fundamental tool in theoretical computer science. By observing that rounding and partitioning of $\mathbb{R}^d$ are equivalent, we introduce the following natural partition problem which we call the {\em secluded hypercube partition problem}: Given $k\in \mathbb{N}$ (ideally small) and $蔚>0$ (ideally large), is there a partition of $\mathbb{R}^d$ with unit hypercubes such that for every point $p \in \mathbb{R}^d$, its closed $蔚$-neighborhood (in the $\ell_{\infty}$ norm) intersects at most $k$ hypercubes? We undertake a comprehensive study of this partition problem. We prove that for every $d\in \mathbb{N}$, there is an explicit (and efficiently computable) hypercube partition of $\mathbb{R}^d$ with $k = d+1$ and $蔚= \frac{1}{2d}$. We complement this construction by proving that the value of $k=d+1$ is the best possible (for any $蔚$) for a broad class of ``reasonable'' partitions including hypercube partitions. We also investigate the optimality of the parameter $蔚$ and prove that any partition in this broad class that has $k=d+1$, must have $蔚\leq\frac{1}{2\sqrt{d}}$. These bounds imply limitations of certain deterministic rounding schemes existing in the literature. Furthermore, this general bound is based on the currently known lower bounds for the dissection number of the cube, and improvements to this bound will yield improvements to our bounds. While our work is motivated by the desire to understand rounding algorithms, one of our main conceptual contributions is the introduction of the {\em secluded hypercube partition problem}, which fits well with a long history of investigations by mathematicians on various hypercube partitions/tilings of Euclidean space. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2211.02694v1-abstract-full').style.display = 'none'; document.getElementById('2211.02694v1-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 November, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2022. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">ACM Class:</span> G.2.1; F.1.3 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2206.07209">arXiv:2206.07209</a> <span> [<a href="https://arxiv.org/pdf/2206.07209">pdf</a>, <a href="https://arxiv.org/ps/2206.07209">ps</a>, <a href="https://arxiv.org/format/2206.07209">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="Discrete Mathematics">cs.DM</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.24963/ijcai.2023/387">10.24963/ijcai.2023/387 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> On Approximating Total Variation Distance </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Gayen%2C+S">Sutanu Gayen</a>, <a href="/search/cs?searchtype=author&query=Meel%2C+K+S">Kuldeep S. Meel</a>, <a href="/search/cs?searchtype=author&query=Myrisiotis%2C+D">Dimitrios Myrisiotis</a>, <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A. Pavan</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</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="2206.07209v2-abstract-short" style="display: inline;"> Total variation distance (TV distance) is a fundamental notion of distance between probability distributions. In this work, we introduce and study the problem of computing the TV distance of two product distributions over the domain $\{0,1\}^n$. In particular, we establish the following results. 1. The problem of exactly computing the TV distance of two product distributions is $\#\mathsf{P}$-co… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2206.07209v2-abstract-full').style.display = 'inline'; document.getElementById('2206.07209v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2206.07209v2-abstract-full" style="display: none;"> Total variation distance (TV distance) is a fundamental notion of distance between probability distributions. In this work, we introduce and study the problem of computing the TV distance of two product distributions over the domain $\{0,1\}^n$. In particular, we establish the following results. 1. The problem of exactly computing the TV distance of two product distributions is $\#\mathsf{P}$-complete. This is in stark contrast with other distance measures such as KL, Chi-square, and Hellinger which tensorize over the marginals leading to efficient algorithms. 2. There is a fully polynomial-time deterministic approximation scheme (FPTAS) for computing the TV distance of two product distributions $P$ and $Q$ where $Q$ is the uniform distribution. This result is extended to the case where $Q$ has a constant number of distinct marginals. In contrast, we show that when $P$ and $Q$ are Bayes net distributions, the relative approximation of their TV distance is $\mathsf{NP}$-hard. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2206.07209v2-abstract-full').style.display = 'none'; document.getElementById('2206.07209v2-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 August, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 14 June, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 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, 1 figure</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (2023) Main Track. Pages 3479-3487 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2105.00639">arXiv:2105.00639</a> <span> [<a href="https://arxiv.org/pdf/2105.00639">pdf</a>, <a href="https://arxiv.org/ps/2105.00639">ps</a>, <a href="https://arxiv.org/format/2105.00639">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="Databases">cs.DB</span> </div> </div> <p class="title is-5 mathjax"> Model Counting meets F0 Estimation </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A. Pavan</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</a>, <a href="/search/cs?searchtype=author&query=Bhattacharyya%2C+A">Arnab Bhattacharyya</a>, <a href="/search/cs?searchtype=author&query=Meel%2C+K+S">Kuldeep S. Meel</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2105.00639v1-abstract-short" style="display: inline;"> Constraint satisfaction problems (CSP's) and data stream models are two powerful abstractions to capture a wide variety of problems arising in different domains of computer science. Developments in the two communities have mostly occurred independently and with little interaction between them. In this work, we seek to investigate whether bridging the seeming communication gap between the two commu… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2105.00639v1-abstract-full').style.display = 'inline'; document.getElementById('2105.00639v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2105.00639v1-abstract-full" style="display: none;"> Constraint satisfaction problems (CSP's) and data stream models are two powerful abstractions to capture a wide variety of problems arising in different domains of computer science. Developments in the two communities have mostly occurred independently and with little interaction between them. In this work, we seek to investigate whether bridging the seeming communication gap between the two communities may pave the way to richer fundamental insights. To this end, we focus on two foundational problems: model counting for CSP's and computation of zeroth frequency moments ($F_0$) for data streams. Our investigations lead us to observe striking similarity in the core techniques employed in the algorithmic frameworks that have evolved separately for model counting and $F_0$ computation. We design a recipe for translation of algorithms developed for $F_0$ estimation to that of model counting, resulting in new algorithms for model counting. We then observe that algorithms in the context of distributed streaming can be transformed to distributed algorithms for model counting. We next turn our attention to viewing streaming from the lens of counting and show that framing $F_0$ estimation as a special case of #DNF counting allows us to obtain a general recipe for a rich class of streaming problems, which had been subjected to case-specific analysis in prior works. In particular, our view yields a state-of-the art algorithm for multidimensional range efficient $F_0$ estimation with a simpler analysis. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2105.00639v1-abstract-full').style.display = 'none'; document.getElementById('2105.00639v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 3 May, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2021. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Appears in PODS '21</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.08589">arXiv:2103.08589</a> <span> [<a href="https://arxiv.org/pdf/2103.08589">pdf</a>, <a href="https://arxiv.org/ps/2103.08589">ps</a>, <a href="https://arxiv.org/format/2103.08589">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </div> </div> <p class="title is-5 mathjax"> Promise Problems Meet Pseudodeterminism </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Dixon%2C+P">Peter Dixon</a>, <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A. Pavan</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</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.08589v1-abstract-short" style="display: inline;"> The Acceptance Probability Estimation Problem (APEP) is to additively approximate the acceptance probability of a Boolean circuit. This problem admits a probabilistic approximation scheme. A central question is whether we can design a pseudodeterministic approximation algorithm for this problem: a probabilistic polynomial-time algorithm that outputs a canonical approximation with high probability.… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2103.08589v1-abstract-full').style.display = 'inline'; document.getElementById('2103.08589v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2103.08589v1-abstract-full" style="display: none;"> The Acceptance Probability Estimation Problem (APEP) is to additively approximate the acceptance probability of a Boolean circuit. This problem admits a probabilistic approximation scheme. A central question is whether we can design a pseudodeterministic approximation algorithm for this problem: a probabilistic polynomial-time algorithm that outputs a canonical approximation with high probability. Recently, it was shown that such an algorithm would imply that every approximation algorithm can be made pseudodeterministic (Dixon, Pavan, Vinodchandran; ITCS 2021). The main conceptual contribution of this work is to establish that the existence of a pseudodeterministic algorithm for APEP is fundamentally connected to the relationship between probabilistic promise classes and the corresponding standard complexity classes. In particular, we show the following equivalence: every promise problem in PromiseBPP has a solution in BPP if and only if APEP has a pseudodeterministic algorithm. Based on this intuition, we show that pseudodeterministic algorithms for APEP can shed light on a few central topics in complexity theory such as circuit lowerbounds, probabilistic hierarchy theorems, and multi-pseudodeterminism. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2103.08589v1-abstract-full').style.display = 'none'; document.getElementById('2103.08589v1-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 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">12 pages</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">ACM Class:</span> F.1.2; F.1.3 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1308.2166">arXiv:1308.2166</a> <span> [<a href="https://arxiv.org/pdf/1308.2166">pdf</a>, <a href="https://arxiv.org/format/1308.2166">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Databases">cs.DB</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="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Social and Information Networks">cs.SI</span> </div> </div> <p class="title is-5 mathjax"> Parallel Triangle Counting in Massive Streaming Graphs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Tangwongsan%2C+K">Kanat Tangwongsan</a>, <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A. Pavan</a>, <a href="/search/cs?searchtype=author&query=Tirthapura%2C+S">Srikanta Tirthapura</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="1308.2166v1-abstract-short" style="display: inline;"> The number of triangles in a graph is a fundamental metric, used in social network analysis, link classification and recommendation, and more. Driven by these applications and the trend that modern graph datasets are both large and dynamic, we present the design and implementation of a fast and cache-efficient parallel algorithm for estimating the number of triangles in a massive undirected graph… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1308.2166v1-abstract-full').style.display = 'inline'; document.getElementById('1308.2166v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1308.2166v1-abstract-full" style="display: none;"> The number of triangles in a graph is a fundamental metric, used in social network analysis, link classification and recommendation, and more. Driven by these applications and the trend that modern graph datasets are both large and dynamic, we present the design and implementation of a fast and cache-efficient parallel algorithm for estimating the number of triangles in a massive undirected graph whose edges arrive as a stream. It brings together the benefits of streaming algorithms and parallel algorithms. By building on the streaming algorithms framework, the algorithm has a small memory footprint. By leveraging the paralell cache-oblivious framework, it makes efficient use of the memory hierarchy of modern multicore machines without needing to know its specific parameters. We prove theoretical bounds on accuracy, memory access cost, and parallel runtime complexity, as well as showing empirically that the algorithm yields accurate results and substantial speedups compared to an optimized sequential implementation. (This is an expanded version of a CIKM'13 paper of the same title.) <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1308.2166v1-abstract-full').style.display = 'none'; document.getElementById('1308.2166v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 9 August, 2013; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 2013. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1001.2034">arXiv:1001.2034</a> <span> [<a href="https://arxiv.org/pdf/1001.2034">pdf</a>, <a href="https://arxiv.org/format/1001.2034">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </div> </div> <p class="title is-5 mathjax"> On the Power of Unambiguity in Logspace </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Pavan%2C+A">Aduri Pavan</a>, <a href="/search/cs?searchtype=author&query=Tewari%2C+R">Raghunath Tewari</a>, <a href="/search/cs?searchtype=author&query=Vinodchandran%2C+N+V">N. V. Vinodchandran</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="1001.2034v1-abstract-short" style="display: inline;"> We report progress on the \NL vs \UL problem. [-] We show unconditionally that the complexity class $\ReachFewL\subseteq\UL$. This improves on the earlier known upper bound $\ReachFewL \subseteq \FewL$. [-] We investigate the complexity of min-uniqueness - a central notion in studying the \NL vs \UL problem. We show that min-uniqueness is necessary and sufficient for showing $\NL =\UL$. We revis… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1001.2034v1-abstract-full').style.display = 'inline'; document.getElementById('1001.2034v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1001.2034v1-abstract-full" style="display: none;"> We report progress on the \NL vs \UL problem. [-] We show unconditionally that the complexity class $\ReachFewL\subseteq\UL$. This improves on the earlier known upper bound $\ReachFewL \subseteq \FewL$. [-] We investigate the complexity of min-uniqueness - a central notion in studying the \NL vs \UL problem. We show that min-uniqueness is necessary and sufficient for showing $\NL =\UL$. We revisit the class $\OptL[\log n]$ and show that {\sc ShortestPathLength} - computing the length of the shortest path in a DAG, is complete for $\OptL[\log n]$. We introduce $\UOptL[\log n]$, an unambiguous version of $\OptL[\log n]$, and show that (a) $\NL =\UL$ if and only if $\OptL[\log n] = \UOptL[\log n]$, (b) $\LogFew \leq \UOptL[\log n] \leq \SPL$. [-] We show that the reachability problem over graphs embedded on 3 pages is complete for \NL. This contrasts with the reachability problem over graphs embedded on 2 pages which is logspace equivalent to the reachability problem in planar graphs and hence is in \UL. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1001.2034v1-abstract-full').style.display = 'none'; document.getElementById('1001.2034v1-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, 2010; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2010. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">14 pages, 3 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1001.0117">arXiv:1001.0117</a> <span> [<a href="https://arxiv.org/pdf/1001.0117">pdf</a>, <a href="https://arxiv.org/ps/1001.0117">ps</a>, <a href="https://arxiv.org/format/1001.0117">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </div> </div> <p class="title is-5 mathjax"> Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Gu%2C+X">Xiaoyang Gu</a>, <a href="/search/cs?searchtype=author&query=Hitchcock%2C+J+M">John M. Hitchcock</a>, <a href="/search/cs?searchtype=author&query=Pavan%2C+A">A. Pavan</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="1001.0117v2-abstract-short" style="display: inline;"> This paper presents the following results on sets that are complete for NP. 1. If there is a problem in NP that requires exponential time at almost all lengths, then every many-one NP-complete set is complete under length-increasing reductions that are computed by polynomial-size circuits. 2. If there is a problem in coNP that cannot be solved by polynomial-size nondeterministic circuits, then… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1001.0117v2-abstract-full').style.display = 'inline'; document.getElementById('1001.0117v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1001.0117v2-abstract-full" style="display: none;"> This paper presents the following results on sets that are complete for NP. 1. If there is a problem in NP that requires exponential time at almost all lengths, then every many-one NP-complete set is complete under length-increasing reductions that are computed by polynomial-size circuits. 2. If there is a problem in coNP that cannot be solved by polynomial-size nondeterministic circuits, then every many-one complete set is complete under length-increasing reductions that are computed by polynomial-size circuits. 3. If there exist a one-way permutation that is secure against subexponential-size circuits and there is a hard tally language in NP intersect coNP, then there is a Turing complete language for NP that is not many-one complete. Our first two results use worst-case hardness hypotheses whereas earlier work that showed similar results relied on average-case or almost-everywhere hardness assumptions. The use of average-case and worst-case hypotheses in the last result is unique as previous results obtaining the same consequence relied on almost-everywhere hardness results. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1001.0117v2-abstract-full').style.display = 'none'; document.getElementById('1001.0117v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 3 February, 2010; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 4 January, 2010; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2010. </p> </li> </ol> <div class="is-hidden-tablet">  <span class="help" style="display: inline-block;"><a href="https://github.com/arXiv/arxiv-search/releases">Search v0.5.6 released 2020-02-24</a>  </span> </div> </div> </main> <footer> <div class="columns is-desktop" role="navigation" aria-label="Secondary">  <div class="column"> <div class="columns"> <div class="column"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/about">About</a></li> <li><a href="https://info.arxiv.org/help">Help</a></li> </ul> </div> <div class="column"> <ul class="nav-spaced"> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>contact arXiv</title><desc>Click here to contact arXiv</desc><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg> <a href="https://info.arxiv.org/help/contact.html"> Contact</a> </li> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>subscribe to arXiv mailings</title><desc>Click here to subscribe</desc><path d="M476 3.2L12.5 270.6c-18.1 10.4-15.8 35.6 2.2 43.2L121 358.4l287.3-253.2c5.5-4.9 13.3 2.6 8.6 8.3L176 407v80.5c0 23.6 28.5 32.9 42.5 15.8L282 426l124.6 52.2c14.2 6 30.4-2.9 33-18.2l72-432C515 7.8 493.3-6.8 476 3.2z"/></svg> <a href="https://info.arxiv.org/help/subscribe"> Subscribe</a> </li> </ul> </div> </div> </div>   <div class="column"> <div class="columns"> <div class="column"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/help/license/index.html">Copyright</a></li> <li><a href="https://info.arxiv.org/help/policies/privacy_policy.html">Privacy Policy</a></li> </ul> </div> <div class="column sorry-app-links"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/help/web_accessibility.html">Web Accessibility Assistance</a></li> <li> <p class="help"> <a class="a11y-main-link" href="https://status.arxiv.org" target="_blank">arXiv Operational Status <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 256 512" class="icon filter-dark_grey" role="presentation"><path d="M224.3 273l-136 136c-9.4 9.4-24.6 9.4-33.9 0l-22.6-22.6c-9.4-9.4-9.4-24.6 0-33.9l96.4-96.4-96.4-96.4c-9.4-9.4-9.4-24.6 0-33.9L54.3 103c9.4-9.4 24.6-9.4 33.9 0l136 136c9.5 9.4 9.5 24.6.1 34z"/></svg></a><br> Get status notifications via <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/email/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg>email</a> or <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/slack/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512" class="icon filter-black" role="presentation"><path d="M94.12 315.1c0 25.9-21.16 47.06-47.06 47.06S0 341 0 315.1c0-25.9 21.16-47.06 47.06-47.06h47.06v47.06zm23.72 0c0-25.9 21.16-47.06 47.06-47.06s47.06 21.16 47.06 47.06v117.84c0 25.9-21.16 47.06-47.06 47.06s-47.06-21.16-47.06-47.06V315.1zm47.06-188.98c-25.9 0-47.06-21.16-47.06-47.06S139 32 164.9 32s47.06 21.16 47.06 47.06v47.06H164.9zm0 23.72c25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06H47.06C21.16 243.96 0 222.8 0 196.9s21.16-47.06 47.06-47.06H164.9zm188.98 47.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06h-47.06V196.9zm-23.72 0c0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06V79.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06V196.9zM283.1 385.88c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06v-47.06h47.06zm0-23.72c-25.9 0-47.06-21.16-47.06-47.06 0-25.9 21.16-47.06 47.06-47.06h117.84c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06H283.1z"/></svg>slack</a> </p> </li> </ul> </div> </div> </div>  </div> </footer> <script src="https://static.arxiv.org/static/base/1.0.0a5/js/member_acknowledgement.js"></script> </body> </html>

CINXE.COM

Search | arXiv e-print repository