Data Structures and Algorithms Jun 2022

<!DOCTYPE html> <html lang="en"> <head> <title>Data Structures and Algorithms Jun 2022</title> <meta name="viewport" content="width=device-width, initial-scale=1"> <link rel="apple-touch-icon" sizes="180x180" href="/static/browse/0.3.4/images/icons/apple-touch-icon.png"> <link rel="icon" type="image/png" sizes="32x32" href="/static/browse/0.3.4/images/icons/favicon-32x32.png"> <link rel="icon" type="image/png" sizes="16x16" href="/static/browse/0.3.4/images/icons/favicon-16x16.png"> <link rel="manifest" href="/static/browse/0.3.4/images/icons/site.webmanifest"> <link rel="mask-icon" href="/static/browse/0.3.4/images/icons/safari-pinned-tab.svg" color="#5bbad5"> <meta name="msapplication-TileColor" content="#da532c"> <meta name="theme-color" content="#ffffff"> <link rel="stylesheet" type="text/css" media="screen" href="/static/browse/0.3.4/css/arXiv.css?v=20241206" /> <link rel="stylesheet" type="text/css" media="print" href="/static/browse/0.3.4/css/arXiv-print.css?v=20200611" /> <link rel="stylesheet" type="text/css" media="screen" href="/static/browse/0.3.4/css/browse_search.css" /> <script language="javascript" src="/static/browse/0.3.4/js/accordion.js" /></script> <script src="/static/browse/0.3.4/js/mathjaxToggle.min.js" type="text/javascript"></script> <script type="text/javascript" language="javascript">mathjaxToggle();</script> </head> <body class="with-cu-identity"> <div class="flex-wrap-footer"> <header> <a href="#content" class="is-sr-only">Skip to main content</a>  <div class="columns is-vcentered is-hidden-mobile" id="cu-identity"> <div class="column" id="cu-logo"> <a href="https://www.cornell.edu/"><img src="/static/browse/0.3.4/images/icons/cu/cornell-reduced-white-SMALL.svg" alt="Cornell University" /></a> </div><div class="column" id="support-ack"> <span id="support-ack-url">We gratefully acknowledge support from the Simons Foundation, <a href="https://info.arxiv.org/about/ourmembers.html">member institutions</a>, and all contributors.</span> <a href="https://info.arxiv.org/about/donate.html" class="btn-header-donate">Donate</a> </div> </div> <div id="header" class="is-hidden-mobile"> <a aria-hidden="true" tabindex="-1" href="/IgnoreMe"></a> <div class="header-breadcrumbs"> <a href="/"><img src="/static/browse/0.3.4/images/arxiv-logo-one-color-white.svg" alt="arxiv logo" style="height:40px;"/></a> <span>></span> <a href="/list/cs.DS/recent">cs.DS</a> </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="mobile-header"> <div class="columns is-mobile"> <div class="column logo-arxiv"><a href="https://arxiv.org/"><img src="/static/browse/0.3.4/images/arxiv-logomark-small-white.svg" alt="arXiv logo" style="height:60px;" /></a></div> <div class="column logo-cornell"><a href="https://www.cornell.edu/"> <picture> <source media="(min-width: 501px)" srcset="/static/browse/0.3.4/images/icons/cu/cornell-reduced-white-SMALL.svg 400w" sizes="400w" /> <source srcset="/static/browse/0.3.4/images/icons/cu/cornell_seal_simple_black.svg 2x" /> <img src="/static/browse/0.3.4/images/icons/cu/cornell-reduced-white-SMALL.svg" alt="Cornell University Logo" /> </picture> </a></div> <div class="column nav" id="toggle-container" role="menubar"> <button class="toggle-control"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-white"><title>open search</title><path d="M505 442.7L405.3 343c-4.5-4.5-10.6-7-17-7H372c27.6-35.3 44-79.7 44-128C416 93.1 322.9 0 208 0S0 93.1 0 208s93.1 208 208 208c48.3 0 92.7-16.4 128-44v16.3c0 6.4 2.5 12.5 7 17l99.7 99.7c9.4 9.4 24.6 9.4 33.9 0l28.3-28.3c9.4-9.4 9.4-24.6.1-34zM208 336c-70.7 0-128-57.2-128-128 0-70.7 57.2-128 128-128 70.7 0 128 57.2 128 128 0 70.7-57.2 128-128 128z"/></svg></button> <div class="mobile-toggle-block toggle-target"> <form class="mobile-search-form" method="GET" action="https://arxiv.org/search"> <div class="field has-addons"> <input class="input" type="text" name="query" placeholder="Search..." aria-label="Search term or terms" /> <input type="hidden" name="source" value="header"> <input type="hidden" name="searchtype" value="all"> <button class="button">GO</button> </div> </form> </div> <button class="toggle-control"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512" class="icon filter-white" role="menu"><title>open navigation menu</title><path d="M16 132h416c8.837 0 16-7.163 16-16V76c0-8.837-7.163-16-16-16H16C7.163 60 0 67.163 0 76v40c0 8.837 7.163 16 16 16zm0 160h416c8.837 0 16-7.163 16-16v-40c0-8.837-7.163-16-16-16H16c-8.837 0-16 7.163-16 16v40c0 8.837 7.163 16 16 16zm0 160h416c8.837 0 16-7.163 16-16v-40c0-8.837-7.163-16-16-16H16c-8.837 0-16 7.163-16 16v40c0 8.837 7.163 16 16 16z"/ ></svg></button> <div class="mobile-toggle-block toggle-target"> <nav class="mobile-menu" aria-labelledby="mobilemenulabel"> <h2 id="mobilemenulabel">quick links</h2> <ul> <li><a href="https://arxiv.org/login">Login</a></li> <li><a href="https://info.arxiv.org/help">Help Pages</a></li> <li><a href="https://info.arxiv.org/about">About</a></li> </ul> </nav> </div> </div> </div> </div> </header> <main> <div id="content"> <div id='content-inner'> <div id='dlpage'> <h1>Data Structures and Algorithms</h1> <h2>Authors and titles for June 2022 </h2> <div class='paging'>Total of 167 entries : <span>1-50</span> <a href=/list/cs.DS/2022-06?skip=50&show=50>51-100</a> <a href=/list/cs.DS/2022-06?skip=100&show=50>101-150</a> <a href=/list/cs.DS/2022-06?skip=150&show=50>151-167</a> </div> <div class='morefewer'>Showing up to 50 entries per page: <a href=/list/cs.DS/2022-06?skip=0&show=25 rel="nofollow"> fewer</a> | <a href=/list/cs.DS/2022-06?skip=0&show=100 rel="nofollow"> more</a> | <a href=/list/cs.DS/2022-06?skip=0&show=2000 rel="nofollow"> all</a> </div> <dl id='articles'> <dt> <a name='item1'>[1]</a> <a href ="/abs/2206.00655" title="Abstract" id="2206.00655"> arXiv:2206.00655 </a> [<a href="/pdf/2206.00655" title="Download PDF" id="pdf-2206.00655" aria-labelledby="pdf-2206.00655">pdf</a>, <a href="/format/2206.00655" title="Other formats" id="oth-2206.00655" aria-labelledby="oth-2206.00655">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Learning-Augmented Algorithms for Online TSP on the Line </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Gouleakis,+T">Themis Gouleakis</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Lakis,+K">Konstantinos Lakis</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Shahkarami,+G">Golnoosh Shahkarami</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Machine Learning (cs.LG) </div> </div> </dd> <dt> <a name='item2'>[2]</a> <a href ="/abs/2206.00752" title="Abstract" id="2206.00752"> arXiv:2206.00752 </a> [<a href="/pdf/2206.00752" title="Download PDF" id="pdf-2206.00752" aria-labelledby="pdf-2206.00752">pdf</a>, <a href="/format/2206.00752" title="Other formats" id="oth-2206.00752" aria-labelledby="oth-2206.00752">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Algorithmic Applications of Tree-Cut Width </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Ganian,+R">Robert Ganian</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Kim,+E+J">Eun Jung Kim</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Szeider,+S">Stefan Szeider</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> Full version to appear in the Siam Journal on Discrete Mathematics </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span> </div> </div> </dd> <dt> <a name='item3'>[3]</a> <a href ="/abs/2206.00781" title="Abstract" id="2206.00781"> arXiv:2206.00781 </a> [<a href="/pdf/2206.00781" title="Download PDF" id="pdf-2206.00781" aria-labelledby="pdf-2206.00781">pdf</a>, <a href="/format/2206.00781" title="Other formats" id="oth-2206.00781" aria-labelledby="oth-2206.00781">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Near-Optimal Search Time in $未$-Optimal Space, and Vice Versa </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Kociumaka,+T">Tomasz Kociumaka</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Navarro,+G">Gonzalo Navarro</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Olivares,+F">Francisco Olivares</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span> </div> </div> </dd> <dt> <a name='item4'>[4]</a> <a href ="/abs/2206.01077" title="Abstract" id="2206.01077"> arXiv:2206.01077 </a> [<a href="/pdf/2206.01077" title="Download PDF" id="pdf-2206.01077" aria-labelledby="pdf-2206.01077">pdf</a>, <a href="/format/2206.01077" title="Other formats" id="oth-2206.01077" aria-labelledby="oth-2206.01077">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> The Power of Amortized Recourse for Online Graph Problems </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Liu,+H">Hsiang-Hsuan Liu</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Toole-Charignon,+J">Jonathan Toole-Charignon</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span> </div> </div> </dd> <dt> <a name='item5'>[5]</a> <a href ="/abs/2206.01149" title="Abstract" id="2206.01149"> arXiv:2206.01149 </a> [<a href="/pdf/2206.01149" title="Download PDF" id="pdf-2206.01149" aria-labelledby="pdf-2206.01149">pdf</a>, <a href="/format/2206.01149" title="Other formats" id="oth-2206.01149" aria-labelledby="oth-2206.01149">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Kurpicz,+F">Florian Kurpicz</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span> </div> </div> </dd> <dt> <a name='item6'>[6]</a> <a href ="/abs/2206.01270" title="Abstract" id="2206.01270"> arXiv:2206.01270 </a> [<a href="/pdf/2206.01270" title="Download PDF" id="pdf-2206.01270" aria-labelledby="pdf-2206.01270">pdf</a>, <a href="/format/2206.01270" title="Other formats" id="oth-2206.01270" aria-labelledby="oth-2206.01270">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Braverman,+M">Mark Braverman</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Derakhshan,+M">Mahsa Derakhshan</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Lovett,+A+M">Antonio Molina Lovett</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span> </div> </div> </dd> <dt> <a name='item7'>[7]</a> <a href ="/abs/2206.01360" title="Abstract" id="2206.01360"> arXiv:2206.01360 </a> [<a href="/pdf/2206.01360" title="Download PDF" id="pdf-2206.01360" aria-labelledby="pdf-2206.01360">pdf</a>, <a href="/format/2206.01360" title="Other formats" id="oth-2206.01360" aria-labelledby="oth-2206.01360">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Balancing Flow Time and Energy Consumption </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Davies,+S">Sami Davies</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Khuller,+S">Samir Khuller</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Zhang,+S">Shirley Zhang</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span> </div> </div> </dd> <dt> <a name='item8'>[8]</a> <a href ="/abs/2206.01382" title="Abstract" id="2206.01382"> arXiv:2206.01382 </a> [<a href="/pdf/2206.01382" title="Download PDF" id="pdf-2206.01382" aria-labelledby="pdf-2206.01382">pdf</a>, <a href="/format/2206.01382" title="Other formats" id="oth-2206.01382" aria-labelledby="oth-2206.01382">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Falconn++: A Locality-sensitive Filtering Approach for Approximate Nearest Neighbor Search </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Pham,+N">Ninh Pham</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Liu,+T">Tao Liu</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> To appear in NeurIPS 2022 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Computer Vision and Pattern Recognition (cs.CV) </div> </div> </dd> <dt> <a name='item9'>[9]</a> <a href ="/abs/2206.01568" title="Abstract" id="2206.01568"> arXiv:2206.01568 </a> [<a href="/pdf/2206.01568" title="Download PDF" id="pdf-2206.01568" aria-labelledby="pdf-2206.01568">pdf</a>, <a href="/format/2206.01568" title="Other formats" id="oth-2206.01568" aria-labelledby="oth-2206.01568">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Improved Deterministic Connectivity in Massively Parallel Computation </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Fischer,+M">Manuela Fischer</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Giliberti,+J">Jeff Giliberti</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Grunau,+C">Christoph Grunau</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> Accepted at DISC 2022 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Distributed, Parallel, and Cluster Computing (cs.DC) </div> </div> </dd> <dt> <a name='item10'>[10]</a> <a href ="/abs/2206.01688" title="Abstract" id="2206.01688"> arXiv:2206.01688 </a> [<a href="/pdf/2206.01688" title="Download PDF" id="pdf-2206.01688" aria-labelledby="pdf-2206.01688">pdf</a>, <a href="/format/2206.01688" title="Other formats" id="oth-2206.01688" aria-labelledby="oth-2206.01688">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> L-systems for Measuring Repetitiveness* </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Navarro,+G">Gonzalo Navarro</a> (1 and 2), <a href="https://arxiv.org/search/cs?searchtype=author&query=Urbina,+C">Cristian Urbina</a> (1 and 2) ((1) University of Chile, (2) CeBiB)</div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> Funded in part by Basal Funds FB0001, Fondecyt Grant 1-200038, and a Conicyt Doctoral Scholarship, ANID, Chile </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Formal Languages and Automata Theory (cs.FL) </div> </div> </dd> <dt> <a name='item11'>[11]</a> <a href ="/abs/2206.01706" title="Abstract" id="2206.01706"> arXiv:2206.01706 </a> [<a href="/pdf/2206.01706" title="Download PDF" id="pdf-2206.01706" aria-labelledby="pdf-2206.01706">pdf</a>, <a href="/format/2206.01706" title="Other formats" id="oth-2206.01706" aria-labelledby="oth-2206.01706">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Weighted Model Counting with Twin-Width </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Ganian,+R">Robert Ganian</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Pokr%C3%BDvka,+F">Filip Pokr媒vka</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Schidler,+A">Andr茅 Schidler</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Simonov,+K">Kirill Simonov</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Szeider,+S">Stefan Szeider</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span> </div> </div> </dd> <dt> <a name='item12'>[12]</a> <a href ="/abs/2206.02872" title="Abstract" id="2206.02872"> arXiv:2206.02872 </a> [<a href="/pdf/2206.02872" title="Download PDF" id="pdf-2206.02872" aria-labelledby="pdf-2206.02872">pdf</a>, <a href="https://arxiv.org/html/2206.02872v3" title="View HTML" id="html-2206.02872" aria-labelledby="html-2206.02872" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2206.02872" title="Other formats" id="oth-2206.02872" aria-labelledby="oth-2206.02872">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Optimal Adjacency Labels for Subgraphs of Cartesian Products </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Esperet,+L">Louis Esperet</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Harms,+N">Nathaniel Harms</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Zamaraev,+V">Viktor Zamaraev</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 13 pages, revised version </div> <div class='list-journal-ref'><span class='descriptor'>Journal-ref:</span> SIAM Journal on Discrete Mathematics 38(3) (2024), 2181-2193 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Combinatorics (math.CO) </div> </div> </dd> <dt> <a name='item13'>[13]</a> <a href ="/abs/2206.03097" title="Abstract" id="2206.03097"> arXiv:2206.03097 </a> [<a href="/pdf/2206.03097" title="Download PDF" id="pdf-2206.03097" aria-labelledby="pdf-2206.03097">pdf</a>, <a href="/format/2206.03097" title="Other formats" id="oth-2206.03097" aria-labelledby="oth-2206.03097">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Locality-sensitive bucketing functions for the edit distance </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Chen,+K">Ke Chen</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Shao,+M">Mingfu Shao</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 12 pages, 2 figures. To be published in WABI 2022, revised according to reviewers' comments </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span> </div> </div> </dd> <dt> <a name='item14'>[14]</a> <a href ="/abs/2206.03242" title="Abstract" id="2206.03242"> arXiv:2206.03242 </a> [<a href="/pdf/2206.03242" title="Download PDF" id="pdf-2206.03242" aria-labelledby="pdf-2206.03242">pdf</a>, <a href="/format/2206.03242" title="Other formats" id="oth-2206.03242" aria-labelledby="oth-2206.03242">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Fast Exact String to D-Texts Alignments </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Mwaniki,+N+M">Njagi Moses Mwaniki</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Garrison,+E">Erik Garrison</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Pisanti,+N">Nadia Pisanti</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Genomics (q-bio.GN) </div> </div> </dd> <dt> <a name='item15'>[15]</a> <a href ="/abs/2206.03319" title="Abstract" id="2206.03319"> arXiv:2206.03319 </a> [<a href="/pdf/2206.03319" title="Download PDF" id="pdf-2206.03319" aria-labelledby="pdf-2206.03319">pdf</a>, <a href="/format/2206.03319" title="Other formats" id="oth-2206.03319" aria-labelledby="oth-2206.03319">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> A Differentially Private Linear-Time fPTAS for the Minimum Enclosing Ball Problem </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Mahpud,+B">Bar Mahpud</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Sheffet,+O">Or Sheffet</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span> </div> </div> </dd> <dt> <a name='item16'>[16]</a> <a href ="/abs/2206.03441" title="Abstract" id="2206.03441"> arXiv:2206.03441 </a> [<a href="/pdf/2206.03441" title="Download PDF" id="pdf-2206.03441" aria-labelledby="pdf-2206.03441">pdf</a>, <a href="https://arxiv.org/html/2206.03441v2" title="View HTML" id="html-2206.03441" aria-labelledby="html-2206.03441" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2206.03441" title="Other formats" id="oth-2206.03441" aria-labelledby="oth-2206.03441">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Robust Sparse Mean Estimation via Sum of Squares </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Diakonikolas,+I">Ilias Diakonikolas</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Kane,+D+M">Daniel M. Kane</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Karmalkar,+S">Sushrut Karmalkar</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Pensia,+A">Ankit Pensia</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Pittas,+T">Thanasis Pittas</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> Fixed minor oversight in runtime calculation </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Machine Learning (cs.LG); Statistics Theory (math.ST); Machine Learning (stat.ML) </div> </div> </dd> <dt> <a name='item17'>[17]</a> <a href ="/abs/2206.04387" title="Abstract" id="2206.04387"> arXiv:2206.04387 </a> [<a href="/pdf/2206.04387" title="Download PDF" id="pdf-2206.04387" aria-labelledby="pdf-2206.04387">pdf</a>, <a href="/format/2206.04387" title="Other formats" id="oth-2206.04387" aria-labelledby="oth-2206.04387">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Kernelization for Feedback Vertex Set via Elimination Distance to a Forest </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Dekker,+D">David Dekker</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Jansen,+B+M+P">Bart M. P. Jansen</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 40 pages, 4 figures. To be published in the Proceedings of WG2022 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span> </div> </div> </dd> <dt> <a name='item18'>[18]</a> <a href ="/abs/2206.04451" title="Abstract" id="2206.04451"> arXiv:2206.04451 </a> [<a href="/pdf/2206.04451" title="Download PDF" id="pdf-2206.04451" aria-labelledby="pdf-2206.04451">pdf</a>, <a href="/format/2206.04451" title="Other formats" id="oth-2206.04451" aria-labelledby="oth-2206.04451">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Deep kernelization for the Tree Bisection and Reconnnect (TBR) distance in phylogenetics </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Kelk,+S">Steven Kelk</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Linz,+S">Simone Linz</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Meuwese,+R">Ruben Meuwese</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 38 pages. In this version a figure has been added, some references have been added, some small typo's have been fixed and the introduction and conclusion have been slightly extended. Submitted for journal review </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Combinatorics (math.CO); Populations and Evolution (q-bio.PE) </div> </div> </dd> <dt> <a name='item19'>[19]</a> <a href ="/abs/2206.04549" title="Abstract" id="2206.04549"> arXiv:2206.04549 </a> [<a href="/pdf/2206.04549" title="Download PDF" id="pdf-2206.04549" aria-labelledby="pdf-2206.04549">pdf</a>, <a href="/format/2206.04549" title="Other formats" id="oth-2206.04549" aria-labelledby="oth-2206.04549">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Spencer's theorem in nearly input-sparsity time </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Jain,+V">Vishesh Jain</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Sah,+A">Ashwin Sah</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Sawhney,+M">Mehtaab Sawhney</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 18 pages; comments welcome </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Optimization and Control (math.OC); Probability (math.PR) </div> </div> </dd> <dt> <a name='item20'>[20]</a> <a href ="/abs/2206.04589" title="Abstract" id="2206.04589"> arXiv:2206.04589 </a> [<a href="/pdf/2206.04589" title="Download PDF" id="pdf-2206.04589" aria-labelledby="pdf-2206.04589">pdf</a>, <a href="/format/2206.04589" title="Other formats" id="oth-2206.04589" aria-labelledby="oth-2206.04589">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Diakonikolas,+I">Ilias Diakonikolas</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Kane,+D+M">Daniel M. Kane</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Sun,+Y">Yuxin Sun</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> To appear in COLT 2022 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Machine Learning (cs.LG); Statistics Theory (math.ST); Machine Learning (stat.ML) </div> </div> </dd> <dt> <a name='item21'>[21]</a> <a href ="/abs/2206.04883" title="Abstract" id="2206.04883"> arXiv:2206.04883 </a> [<a href="/pdf/2206.04883" title="Download PDF" id="pdf-2206.04883" aria-labelledby="pdf-2206.04883">pdf</a>, <a href="/format/2206.04883" title="Other formats" id="oth-2206.04883" aria-labelledby="oth-2206.04883">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> On the Complexity of Sampling Redistricting Plans </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Charikar,+M">Moses Charikar</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Liu,+P">Paul Liu</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Liu,+T">Tianyu Liu</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Vuong,+T">Thuy-Duong Vuong</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> Correcting the definition of Markov chain to sample from spanning tree distribution </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Computational Geometry (cs.CG) </div> </div> </dd> <dt> <a name='item22'>[22]</a> <a href ="/abs/2206.05174" title="Abstract" id="2206.05174"> arXiv:2206.05174 </a> [<a href="/pdf/2206.05174" title="Download PDF" id="pdf-2206.05174" aria-labelledby="pdf-2206.05174">pdf</a>, <a href="/format/2206.05174" title="Other formats" id="oth-2206.05174" aria-labelledby="oth-2206.05174">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Dory,+M">Michal Dory</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Ghaffari,+M">Mohsen Ghaffari</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Ilchi,+S">Saeed Ilchi</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> PODC 2022 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Distributed, Parallel, and Cluster Computing (cs.DC) </div> </div> </dd> <dt> <a name='item23'>[23]</a> <a href ="/abs/2206.05245" title="Abstract" id="2206.05245"> arXiv:2206.05245 </a> [<a href="/pdf/2206.05245" title="Download PDF" id="pdf-2206.05245" aria-labelledby="pdf-2206.05245">pdf</a>, <a href="https://arxiv.org/html/2206.05245v2" title="View HTML" id="html-2206.05245" aria-labelledby="html-2206.05245" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2206.05245" title="Other formats" id="oth-2206.05245" aria-labelledby="oth-2206.05245">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Diakonikolas,+I">Ilias Diakonikolas</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Kane,+D+M">Daniel M. Kane</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Karmalkar,+S">Sushrut Karmalkar</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Pensia,+A">Ankit Pensia</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Pittas,+T">Thanasis Pittas</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> Added fact about taking roots in SoS proofs (Fact 2.9) </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Machine Learning (cs.LG); Statistics Theory (math.ST); Machine Learning (stat.ML) </div> </div> </dd> <dt> <a name='item24'>[24]</a> <a href ="/abs/2206.05579" title="Abstract" id="2206.05579"> arXiv:2206.05579 </a> [<a href="/pdf/2206.05579" title="Download PDF" id="pdf-2206.05579" aria-labelledby="pdf-2206.05579">pdf</a>, <a href="https://arxiv.org/html/2206.05579v4" title="View HTML" id="html-2206.05579" aria-labelledby="html-2206.05579" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2206.05579" title="Other formats" id="oth-2206.05579" aria-labelledby="oth-2206.05579">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Online Paging with Heterogeneous Cache Slots </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Chrobak,+M">Marek Chrobak</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Haney,+S">Samuel Haney</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Liaee,+M">Mehraneh Liaee</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Panigrahi,+D">Debmalya Panigrahi</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Rajaraman,+R">Rajmohan Rajaraman</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Sundaram,+R">Ravi Sundaram</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Young,+N+E">Neal E. Young</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> conference and journal versions appear in STACS 2023 and Algorithmica (2004) </div> <div class='list-journal-ref'><span class='descriptor'>Journal-ref:</span> Algorithmica (2004) </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span> </div> </div> </dd> <dt> <a name='item25'>[25]</a> <a href ="/abs/2206.05597" title="Abstract" id="2206.05597"> arXiv:2206.05597 </a> [<a href="/pdf/2206.05597" title="Download PDF" id="pdf-2206.05597" aria-labelledby="pdf-2206.05597">pdf</a>, <a href="/format/2206.05597" title="Other formats" id="oth-2206.05597" aria-labelledby="oth-2206.05597">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Lower Bounds for Sorting 16, 17, and 18 Elements </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Stober,+F">Florian Stober</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Wei%C3%9F,+A">Armin Wei脽</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span> </div> </div> </dd> <dt> <a name='item26'>[26]</a> <a href ="/abs/2206.05947" title="Abstract" id="2206.05947"> arXiv:2206.05947 </a> [<a href="/pdf/2206.05947" title="Download PDF" id="pdf-2206.05947" aria-labelledby="pdf-2206.05947">pdf</a>, <a href="/format/2206.05947" title="Other formats" id="oth-2206.05947" aria-labelledby="oth-2206.05947">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Lazy and Fast Greedy MAP Inference for Determinantal Point Process </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Hemmi,+S">Shinichi Hemmi</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Oki,+T">Taihei Oki</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Sakaue,+S">Shinsaku Sakaue</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Fujii,+K">Kaito Fujii</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Iwata,+S">Satoru Iwata</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Machine Learning (cs.LG) </div> </div> </dd> <dt> <a name='item27'>[27]</a> <a href ="/abs/2206.06053" title="Abstract" id="2206.06053"> arXiv:2206.06053 </a> [<a href="/pdf/2206.06053" title="Download PDF" id="pdf-2206.06053" aria-labelledby="pdf-2206.06053">pdf</a>, <a href="/format/2206.06053" title="Other formats" id="oth-2206.06053" aria-labelledby="oth-2206.06053">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> KATKA: A KRAKEN-like tool with $k$ given at query time </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Gagie,+T">Travis Gagie</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Kashgouli,+S">Sana Kashgouli</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Langmead,+B">Ben Langmead</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span> </div> </div> </dd> <dt> <a name='item28'>[28]</a> <a href ="/abs/2206.06102" title="Abstract" id="2206.06102"> arXiv:2206.06102 </a> [<a href="/pdf/2206.06102" title="Download PDF" id="pdf-2206.06102" aria-labelledby="pdf-2206.06102">pdf</a>, <a href="/format/2206.06102" title="Other formats" id="oth-2206.06102" aria-labelledby="oth-2206.06102">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Bin stretching with migration on two hierarchical machines </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Akaria,+I">Islam Akaria</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Epstein,+L">Leah Epstein</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Discrete Mathematics (cs.DM); Combinatorics (math.CO); Optimization and Control (math.OC) </div> </div> </dd> <dt> <a name='item29'>[29]</a> <a href ="/abs/2206.06223" title="Abstract" id="2206.06223"> arXiv:2206.06223 </a> [<a href="/pdf/2206.06223" title="Download PDF" id="pdf-2206.06223" aria-labelledby="pdf-2206.06223">pdf</a>, <a href="/format/2206.06223" title="Other formats" id="oth-2206.06223" aria-labelledby="oth-2206.06223">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Pursuing More Effective Graph Spectral Sparsifiers via Approximate Trace Reduction </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Liu,+Z">Zhiqiang Liu</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Yu,+W">Wenjian Yu</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 7 pages, 2 figures. to appear at DAC'2022 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Numerical Analysis (math.NA); Spectral Theory (math.SP) </div> </div> </dd> <dt> <a name='item30'>[30]</a> <a href ="/abs/2206.06299" title="Abstract" id="2206.06299"> arXiv:2206.06299 </a> [<a href="/pdf/2206.06299" title="Download PDF" id="pdf-2206.06299" aria-labelledby="pdf-2206.06299">pdf</a>, <a href="/format/2206.06299" title="Other formats" id="oth-2206.06299" aria-labelledby="oth-2206.06299">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> An adversarially robust data-market for spatial, crowd-sourced data </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Kharman,+A+M">Aida Manzano Kharman</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Jursitzky,+C">Christian Jursitzky</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Zhou,+Q">Quan Zhou</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Ferraro,+P">Pietro Ferraro</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Marecek,+J">Jakub Marecek</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Pinson,+P">Pierre Pinson</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Shorten,+R">Robert Shorten</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 13 pages, 7 figures </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span> </div> </div> </dd> <dt> <a name='item31'>[31]</a> <a href ="/abs/2206.06744" title="Abstract" id="2206.06744"> arXiv:2206.06744 </a> [<a href="/pdf/2206.06744" title="Download PDF" id="pdf-2206.06744" aria-labelledby="pdf-2206.06744">pdf</a>, <a href="/format/2206.06744" title="Other formats" id="oth-2206.06744" aria-labelledby="oth-2206.06744">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Counting Markov Equivalent Directed Acyclic Graphs Consistent with Background Knowledge </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Sharma,+V+S">Vidya Sagar Sharma</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 24 pages, 1 figure, and 2 tables </div> <div class='list-journal-ref'><span class='descriptor'>Journal-ref:</span> 39th Conference on Uncertainty in Artificial Intelligence (UAI-2023) </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Artificial Intelligence (cs.AI); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Machine Learning (cs.LG) </div> </div> </dd> <dt> <a name='item32'>[32]</a> <a href ="/abs/2206.06924" title="Abstract" id="2206.06924"> arXiv:2206.06924 </a> [<a href="/pdf/2206.06924" title="Download PDF" id="pdf-2206.06924" aria-labelledby="pdf-2206.06924">pdf</a>, <a href="/format/2206.06924" title="Other formats" id="oth-2206.06924" aria-labelledby="oth-2206.06924">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> The Maximum Linear Arrangement Problem for trees under projectivity and planarity </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Alemany-Puig,+L">Llu铆s Alemany-Puig</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Esteban,+J+L">Juan Luis Esteban</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Ferrer-i-Cancho,+R">Ramon Ferrer-i-Cancho</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> The fourth version is incorrect. We are sure the right files were uploaded but for whatever reason, it looks like we uploaded the wrong files. The abstract in the fourth version is correct though </div> <div class='list-journal-ref'><span class='descriptor'>Journal-ref:</span> Information Processing Letters 183, 106400 (2024) </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Computation and Language (cs.CL); Discrete Mathematics (cs.DM) </div> </div> </dd> <dt> <a name='item33'>[33]</a> <a href ="/abs/2206.06988" title="Abstract" id="2206.06988"> arXiv:2206.06988 </a> [<a href="/pdf/2206.06988" title="Download PDF" id="pdf-2206.06988" aria-labelledby="pdf-2206.06988">pdf</a>, <a href="/format/2206.06988" title="Other formats" id="oth-2206.06988" aria-labelledby="oth-2206.06988">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> The Complexity of Finding Fair Many-to-One Matchings </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Boehmer,+N">Niclas Boehmer</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Koana,+T">Tomohiro Koana</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> Accepted to ICALP'22 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Discrete Mathematics (cs.DM); Computer Science and Game Theory (cs.GT) </div> </div> </dd> <dt> <a name='item34'>[34]</a> <a href ="/abs/2206.07052" title="Abstract" id="2206.07052"> arXiv:2206.07052 </a> [<a href="/pdf/2206.07052" title="Download PDF" id="pdf-2206.07052" aria-labelledby="pdf-2206.07052">pdf</a>, <a href="/format/2206.07052" title="Other formats" id="oth-2206.07052" aria-labelledby="oth-2206.07052">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Sequential Optimization Numbers and Conjecture about Edge-Symmetry and Weight-Symmetry Shortest Weight-Constrained Path </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Hui,+Z">Zile Hui</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span> </div> </div> </dd> <dt> <a name='item35'>[35]</a> <a href ="/abs/2206.07209" title="Abstract" id="2206.07209"> arXiv:2206.07209 </a> [<a href="/pdf/2206.07209" title="Download PDF" id="pdf-2206.07209" aria-labelledby="pdf-2206.07209">pdf</a>, <a href="/format/2206.07209" title="Other formats" id="oth-2206.07209" aria-labelledby="oth-2206.07209">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> On Approximating Total Variation Distance </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Bhattacharyya,+A">Arnab Bhattacharyya</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Gayen,+S">Sutanu Gayen</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Meel,+K+S">Kuldeep S. Meel</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Myrisiotis,+D">Dimitrios Myrisiotis</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Pavan,+A">A. Pavan</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Vinodchandran,+N+V">N. V. Vinodchandran</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 20 pages, 1 figure </div> <div class='list-journal-ref'><span class='descriptor'>Journal-ref:</span> Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (2023) Main Track. Pages 3479-3487 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Computational Complexity (cs.CC); Discrete Mathematics (cs.DM) </div> </div> </dd> <dt> <a name='item36'>[36]</a> <a href ="/abs/2206.07250" title="Abstract" id="2206.07250"> arXiv:2206.07250 </a> [<a href="/pdf/2206.07250" title="Download PDF" id="pdf-2206.07250" aria-labelledby="pdf-2206.07250">pdf</a>, <a href="/format/2206.07250" title="Other formats" id="oth-2206.07250" aria-labelledby="oth-2206.07250">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Makarychev,+Y">Yury Makarychev</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Manoj,+N+S">Naren Sarayu Manoj</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Ovsiankin,+M">Max Ovsiankin</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> Accepted to COLT 2022 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Computational Geometry (cs.CG) </div> </div> </dd> <dt> <a name='item37'>[37]</a> <a href ="/abs/2206.07286" title="Abstract" id="2206.07286"> arXiv:2206.07286 </a> [<a href="/pdf/2206.07286" title="Download PDF" id="pdf-2206.07286" aria-labelledby="pdf-2206.07286">pdf</a>, <a href="/format/2206.07286" title="Other formats" id="oth-2206.07286" aria-labelledby="oth-2206.07286">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Faster Decomposition of Weighted Graphs into Cliques using Fisher's Inequality </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Jain,+S">Shweta Jain</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Mizutani,+Y">Yosuke Mizutani</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Sullivan,+B">Blair Sullivan</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 11 pages, 7 figures </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Discrete Mathematics (cs.DM) </div> </div> </dd> <dt> <a name='item38'>[38]</a> <a href ="/abs/2206.07554" title="Abstract" id="2206.07554"> arXiv:2206.07554 </a> [<a href="/pdf/2206.07554" title="Download PDF" id="pdf-2206.07554" aria-labelledby="pdf-2206.07554">pdf</a>, <a href="/format/2206.07554" title="Other formats" id="oth-2206.07554" aria-labelledby="oth-2206.07554">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Assadi,+S">Sepehr Assadi</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Chatziafratis,+V">Vaggos Chatziafratis</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=%C5%81%C4%85cki,+J">Jakub 艁膮cki</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Mirrokni,+V">Vahab Mirrokni</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Wang,+C">Chen Wang</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> Full version of the paper accepted to COLT 2022. 55 pages, 3 figures </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span> </div> </div> </dd> <dt> <a name='item39'>[39]</a> <a href ="/abs/2206.07633" title="Abstract" id="2206.07633"> arXiv:2206.07633 </a> [<a href="/pdf/2206.07633" title="Download PDF" id="pdf-2206.07633" aria-labelledby="pdf-2206.07633">pdf</a>, <a href="/format/2206.07633" title="Other formats" id="oth-2206.07633" aria-labelledby="oth-2206.07633">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Sublinear Algorithms for Hierarchical Clustering </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Agarwal,+A">Arpit Agarwal</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Khanna,+S">Sanjeev Khanna</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Li,+H">Huan Li</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Patil,+P">Prathamesh Patil</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Machine Learning (cs.LG) </div> </div> </dd> <dt> <a name='item40'>[40]</a> <a href ="/abs/2206.07672" title="Abstract" id="2206.07672"> arXiv:2206.07672 </a> [<a href="/pdf/2206.07672" title="Download PDF" id="pdf-2206.07672" aria-labelledby="pdf-2206.07672">pdf</a>, <a href="/format/2206.07672" title="Other formats" id="oth-2206.07672" aria-labelledby="oth-2206.07672">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Reconstructing Ultrametric Trees from Noisy Experiments </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Arunachaleswaran,+E+R">Eshwar Ram Arunachaleswaran</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=De,+A">Anindya De</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Kannan,+S">Sampath Kannan</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span> </div> </div> </dd> <dt> <a name='item41'>[41]</a> <a href ="/abs/2206.08187" title="Abstract" id="2206.08187"> arXiv:2206.08187 </a> [<a href="/pdf/2206.08187" title="Download PDF" id="pdf-2206.08187" aria-labelledby="pdf-2206.08187">pdf</a>, <a href="https://arxiv.org/html/2206.08187v3" title="View HTML" id="html-2206.08187" aria-labelledby="html-2206.08187" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2206.08187" title="Other formats" id="oth-2206.08187" aria-labelledby="oth-2206.08187">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Approximating optimization problems in graphs with locational uncertainty </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Bougeret,+M">Marin Bougeret</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Omer,+J">J茅r茅my Omer</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Poss,+M">Michael Poss</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> arXiv admin note: substantial text overlap with <a href="https://arxiv.org/abs/2109.00389" data-arxiv-id="2109.00389" class="link-https">arXiv:2109.00389</a> </div> <div class='list-journal-ref'><span class='descriptor'>Journal-ref:</span> Discrete Mathematics & Theoretical Computer Science, vol. 26:3, Combinatorics (December 17, 2024) dmtcs:11175 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span> </div> </div> </dd> <dt> <a name='item42'>[42]</a> <a href ="/abs/2206.08495" title="Abstract" id="2206.08495"> arXiv:2206.08495 </a> [<a href="/pdf/2206.08495" title="Download PDF" id="pdf-2206.08495" aria-labelledby="pdf-2206.08495">pdf</a>, <a href="/format/2206.08495" title="Other formats" id="oth-2206.08495" aria-labelledby="oth-2206.08495">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Yankee Swap: a Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Viswanathan,+V">Vignesh Viswanathan</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Zick,+Y">Yair Zick</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Artificial Intelligence (cs.AI); Computer Science and Game Theory (cs.GT) </div> </div> </dd> <dt> <a name='item43'>[43]</a> <a href ="/abs/2206.08646" title="Abstract" id="2206.08646"> arXiv:2206.08646 </a> [<a href="/pdf/2206.08646" title="Download PDF" id="pdf-2206.08646" aria-labelledby="pdf-2206.08646">pdf</a>, <a href="/format/2206.08646" title="Other formats" id="oth-2206.08646" aria-labelledby="oth-2206.08646">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Scalable Differentially Private Clustering via Hierarchically Separated Trees </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Cohen-Addad,+V">Vincent Cohen-Addad</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Epasto,+A">Alessandro Epasto</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Lattanzi,+S">Silvio Lattanzi</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Mirrokni,+V">Vahab Mirrokni</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Munoz,+A">Andres Munoz</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Saulpic,+D">David Saulpic</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Schwiegelshohn,+C">Chris Schwiegelshohn</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Vassilvitskii,+S">Sergei Vassilvitskii</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> To appear at KDD'22 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Cryptography and Security (cs.CR); Machine Learning (cs.LG) </div> </div> </dd> <dt> <a name='item44'>[44]</a> <a href ="/abs/2206.09204" title="Abstract" id="2206.09204"> arXiv:2206.09204 </a> [<a href="/pdf/2206.09204" title="Download PDF" id="pdf-2206.09204" aria-labelledby="pdf-2206.09204">pdf</a>, <a href="/format/2206.09204" title="Other formats" id="oth-2206.09204" aria-labelledby="oth-2206.09204">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Hsieh,+J">Jun-Ting Hsieh</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Kothari,+P+K">Pravesh K. Kothari</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Computational Complexity (cs.CC) </div> </div> </dd> <dt> <a name='item45'>[45]</a> <a href ="/abs/2206.09384" title="Abstract" id="2206.09384"> arXiv:2206.09384 </a> [<a href="/pdf/2206.09384" title="Download PDF" id="pdf-2206.09384" aria-labelledby="pdf-2206.09384">pdf</a>, <a href="/format/2206.09384" title="Other formats" id="oth-2206.09384" aria-labelledby="oth-2206.09384">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Sampling from Log-Concave Distributions over Polytopes via a Soft-Threshold Dikin Walk </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Mangoubi,+O">Oren Mangoubi</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Vishnoi,+N+K">Nisheeth K. Vishnoi</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> arXiv admin note: substantial text overlap with <a href="https://arxiv.org/abs/2111.04089" data-arxiv-id="2111.04089" class="link-https">arXiv:2111.04089</a> </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Machine Learning (cs.LG); Probability (math.PR); Machine Learning (stat.ML) </div> </div> </dd> <dt> <a name='item46'>[46]</a> <a href ="/abs/2206.09563" title="Abstract" id="2206.09563"> arXiv:2206.09563 </a> [<a href="/pdf/2206.09563" title="Download PDF" id="pdf-2206.09563" aria-labelledby="pdf-2206.09563">pdf</a>, <a href="https://arxiv.org/html/2206.09563v6" title="View HTML" id="html-2206.09563" aria-labelledby="html-2206.09563" rel="noopener noreferrer" target="_blank">html</a>, <a href="/format/2206.09563" title="Other formats" id="oth-2206.09563" aria-labelledby="oth-2206.09563">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Chen,+Y">Yixin Chen</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Dey,+T">Tonmoy Dey</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Kuhnle,+A">Alan Kuhnle</a></div> <div class='list-journal-ref'><span class='descriptor'>Journal-ref:</span> Journal of Artificial Intelligence Research 80 (2024): 1575-1622 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Distributed, Parallel, and Cluster Computing (cs.DC); Machine Learning (cs.LG) </div> </div> </dd> <dt> <a name='item47'>[47]</a> <a href ="/abs/2206.09884" title="Abstract" id="2206.09884"> arXiv:2206.09884 </a> [<a href="/pdf/2206.09884" title="Download PDF" id="pdf-2206.09884" aria-labelledby="pdf-2206.09884">pdf</a>, <a href="/format/2206.09884" title="Other formats" id="oth-2206.09884" aria-labelledby="oth-2206.09884">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Finding $k$-Secluded Trees Faster </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Donkers,+H">Huib Donkers</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Jansen,+B+M">Bart M.P. Jansen</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=de+Kroon,+J+J">Jari J.H. de Kroon</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Computational Complexity (cs.CC) </div> </div> </dd> <dt> <a name='item48'>[48]</a> <a href ="/abs/2206.10287" title="Abstract" id="2206.10287"> arXiv:2206.10287 </a> [<a href="/pdf/2206.10287" title="Download PDF" id="pdf-2206.10287" aria-labelledby="pdf-2206.10287">pdf</a>, <a href="/format/2206.10287" title="Other formats" id="oth-2206.10287" aria-labelledby="oth-2206.10287">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Superiority of Instantaneous Decisions in Thin Dynamic Matching Markets </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=B%C3%A4umler,+J">Johannes B盲umler</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Bullinger,+M">Martin Bullinger</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Kober,+S">Stefan Kober</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Zhu,+D">Donghao Zhu</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> Appears in the 24th ACM Conference on Economics and Computation (EC), 2023 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Theoretical Economics (econ.TH) </div> </div> </dd> <dt> <a name='item49'>[49]</a> <a href ="/abs/2206.10383" title="Abstract" id="2206.10383"> arXiv:2206.10383 </a> [<a href="/pdf/2206.10383" title="Download PDF" id="pdf-2206.10383" aria-labelledby="pdf-2206.10383">pdf</a>, <a href="/format/2206.10383" title="Other formats" id="oth-2206.10383" aria-labelledby="oth-2206.10383">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> The Complexity of the Co-Occurrence Problem </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Bille,+P">Philip Bille</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=G%C3%B8rtz,+I+L">Inge Li G酶rtz</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Stordalen,+T">Tord Stordalen</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span> </div> </div> </dd> <dt> <a name='item50'>[50]</a> <a href ="/abs/2206.10681" title="Abstract" id="2206.10681"> arXiv:2206.10681 </a> [<a href="/pdf/2206.10681" title="Download PDF" id="pdf-2206.10681" aria-labelledby="pdf-2206.10681">pdf</a>, <a href="/format/2206.10681" title="Other formats" id="oth-2206.10681" aria-labelledby="oth-2206.10681">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Near-Linear $\varepsilon$-Emulators for Planar Graphs </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Chang,+H">Hsien-Chih Chang</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Krauthgamer,+R">Robert Krauthgamer</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Tan,+Z">Zihan Tan</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> Conference version appeared in STOC 2022 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Data Structures and Algorithms (cs.DS)</span>; Computational Geometry (cs.CG); Discrete Mathematics (cs.DM) </div> </div> </dd> </dl> <div class='paging'>Total of 167 entries : <span>1-50</span> <a href=/list/cs.DS/2022-06?skip=50&show=50>51-100</a> <a href=/list/cs.DS/2022-06?skip=100&show=50>101-150</a> <a href=/list/cs.DS/2022-06?skip=150&show=50>151-167</a> </div> <div class='morefewer'>Showing up to 50 entries per page: <a href=/list/cs.DS/2022-06?skip=0&show=25 rel="nofollow"> fewer</a> | <a href=/list/cs.DS/2022-06?skip=0&show=100 rel="nofollow"> more</a> | <a href=/list/cs.DS/2022-06?skip=0&show=2000 rel="nofollow"> all</a> </div> </div> </div> </div> </main> <footer style="clear: both;"> <div class="columns is-desktop" role="navigation" aria-label="Secondary" style="margin: -0.75em -0.75em 0.75em -0.75em">  <div class="column" style="padding: 0;"> <div class="columns"> <div class="column"> <ul style="list-style: none; line-height: 2;"> <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 style="list-style: none; line-height: 2;"> <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" style="padding: 0;"> <div class="columns"> <div class="column"> <ul style="list-style: none; line-height: 2;"> <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 style="list-style: none; line-height: 2;"> <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> </div> <script src="/static/base/1.0.1/js/member_acknowledgement.js"></script> </body> </html>

CINXE.COM

Data Structures and Algorithms Jun 2022