Computational Complexity Mar 2020

<!DOCTYPE html> <html lang="en"> <head> <title>Computational Complexity Mar 2020</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.CC/recent">cs.CC</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>Computational Complexity</h1> <h2>Authors and titles for March 2020 </h2> <div class='paging'>Total of 50 entries </div> <div class='morefewer'>Showing up to 50 entries per page: <a href=/list/cs.CC/2020-03?skip=0&show=25 rel="nofollow"> fewer</a> | <span style="color: #454545">more</span> | <span style="color: #454545">all</span> </div> <dl id='articles'> <dt> <a name='item1'>[1]</a> <a href ="/abs/2003.00336" title="Abstract" id="2003.00336"> arXiv:2003.00336 </a> [<a href="/pdf/2003.00336" title="Download PDF" id="pdf-2003.00336" aria-labelledby="pdf-2003.00336">pdf</a>, <a href="/format/2003.00336" title="Other formats" id="oth-2003.00336" aria-labelledby="oth-2003.00336">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Three-dimensional matching is NP-Hard </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Kushagra,+S">Shrinu Kushagra</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span> </div> </div> </dd> <dt> <a name='item2'>[2]</a> <a href ="/abs/2003.00669" title="Abstract" id="2003.00669"> arXiv:2003.00669 </a> [<a href="/pdf/2003.00669" title="Download PDF" id="pdf-2003.00669" aria-labelledby="pdf-2003.00669">pdf</a>, <a href="/format/2003.00669" title="Other formats" id="oth-2003.00669" aria-labelledby="oth-2003.00669">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Hardness of Sparse Sets and Minimal Circuit Size Problem </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Fu,+B">Bin Fu</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span> </div> </div> </dd> <dt> <a name='item3'>[3]</a> <a href ="/abs/2003.01591" title="Abstract" id="2003.01591"> arXiv:2003.01591 </a> [<a href="/pdf/2003.01591" title="Download PDF" id="pdf-2003.01591" aria-labelledby="pdf-2003.01591">pdf</a>, <a href="/format/2003.01591" title="Other formats" id="oth-2003.01591" aria-labelledby="oth-2003.01591">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Direct Product Primality Testing of Graphs is GI-hard </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Calderoni,+L">Luca Calderoni</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Margara,+L">Luciano Margara</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Marzolla,+M">Moreno Marzolla</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span>; Combinatorics (math.CO) </div> </div> </dd> <dt> <a name='item4'>[4]</a> <a href ="/abs/2003.02323" title="Abstract" id="2003.02323"> arXiv:2003.02323 </a> [<a href="/pdf/2003.02323" title="Download PDF" id="pdf-2003.02323" aria-labelledby="pdf-2003.02323">pdf</a>, <a href="/format/2003.02323" title="Other formats" id="oth-2003.02323" aria-labelledby="oth-2003.02323">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Towards a Complexity-theoretic Understanding of Restarts in SAT solvers </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Li,+C">Chunxiao Li</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Fleming,+N">Noah Fleming</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Vinyals,+M">Marc Vinyals</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Pitassi,+T">Toniann Pitassi</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Ganesh,+V">Vijay Ganesh</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span> </div> </div> </dd> <dt> <a name='item5'>[5]</a> <a href ="/abs/2003.02524" title="Abstract" id="2003.02524"> arXiv:2003.02524 </a> [<a href="/pdf/2003.02524" title="Download PDF" id="pdf-2003.02524" aria-labelledby="pdf-2003.02524">pdf</a>, <a href="/format/2003.02524" title="Other formats" id="oth-2003.02524" aria-labelledby="oth-2003.02524">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Characterizations and approximability of hard counting classes below #P </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Bakali,+E">Eleni Bakali</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Chalki,+A">Aggeliki Chalki</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Pagourtzis,+A">Aris Pagourtzis</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 18 pages, 5 figures, to be published in the proceedings of TAMC2020 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span> </div> </div> </dd> <dt> <a name='item6'>[6]</a> <a href ="/abs/2003.03019" title="Abstract" id="2003.03019"> arXiv:2003.03019 </a> [<a href="/pdf/2003.03019" title="Download PDF" id="pdf-2003.03019" aria-labelledby="pdf-2003.03019">pdf</a>, <a href="/format/2003.03019" title="Other formats" id="oth-2003.03019" aria-labelledby="oth-2003.03019">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Barriers for rectangular matrix multiplication </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Christandl,+M">Matthias Christandl</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Gall,+F+L">Fran莽ois Le Gall</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Lysikov,+V">Vladimir Lysikov</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Zuiddam,+J">Jeroen Zuiddam</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span>; Commutative Algebra (math.AC) </div> </div> </dd> <dt> <a name='item7'>[7]</a> <a href ="/abs/2003.03595" title="Abstract" id="2003.03595"> arXiv:2003.03595 </a> [<a href="/pdf/2003.03595" title="Download PDF" id="pdf-2003.03595" aria-labelledby="pdf-2003.03595">pdf</a>, <a href="/format/2003.03595" title="Other formats" id="oth-2003.03595" aria-labelledby="oth-2003.03595">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> The Fine-Grained Complexity of Computing the Tutte Polynomial of a Linear Matroid </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Bj%C3%B6rklund,+A">Andreas Bj枚rklund</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Kaski,+P">Petteri Kaski</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> This version adds Theorem 4 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span>; Data Structures and Algorithms (cs.DS); Combinatorics (math.CO) </div> </div> </dd> <dt> <a name='item8'>[8]</a> <a href ="/abs/2003.04834" title="Abstract" id="2003.04834"> arXiv:2003.04834 </a> [<a href="/pdf/2003.04834" title="Download PDF" id="pdf-2003.04834" aria-labelledby="pdf-2003.04834">pdf</a>, <a href="/format/2003.04834" title="Other formats" id="oth-2003.04834" aria-labelledby="oth-2003.04834">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Algebraic Branching Programs, Border Complexity, and Tangent Spaces </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Bl%C3%A4ser,+M">Markus Bl盲ser</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Ikenmeyer,+C">Christian Ikenmeyer</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Mahajan,+M">Meena Mahajan</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Pandey,+A">Anurag Pandey</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Saurabh,+N">Nitin Saurabh</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span> </div> </div> </dd> <dt> <a name='item9'>[9]</a> <a href ="/abs/2003.05152" title="Abstract" id="2003.05152"> arXiv:2003.05152 </a> [<a href="/pdf/2003.05152" title="Download PDF" id="pdf-2003.05152" aria-labelledby="pdf-2003.05152">pdf</a>, <a href="/format/2003.05152" title="Other formats" id="oth-2003.05152" aria-labelledby="oth-2003.05152">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> A generalized Sylvester-Gallai type theorem for quadratic polynomials </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Peleg,+S">Shir Peleg</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Shpilka,+A">Amir Shpilka</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span>; Computational Geometry (cs.CG) </div> </div> </dd> <dt> <a name='item10'>[10]</a> <a href ="/abs/2003.05269" title="Abstract" id="2003.05269"> arXiv:2003.05269 </a> [<a href="/pdf/2003.05269" title="Download PDF" id="pdf-2003.05269" aria-labelledby="pdf-2003.05269">pdf</a>, <a href="/format/2003.05269" title="Other formats" id="oth-2003.05269" aria-labelledby="oth-2003.05269">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> On Function Description </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Vuckovac,+R">Rade Vuckovac</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 16 pages, 5 figures </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span> </div> </div> </dd> <dt> <a name='item11'>[11]</a> <a href ="/abs/2003.05582" title="Abstract" id="2003.05582"> arXiv:2003.05582 </a> [<a href="/pdf/2003.05582" title="Download PDF" id="pdf-2003.05582" aria-labelledby="pdf-2003.05582">pdf</a>, <a href="/format/2003.05582" title="Other formats" id="oth-2003.05582" aria-labelledby="oth-2003.05582">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> $位_\infty$ & Maximum Variance Embedding: Measuring and Optimizing Connectivity of A Graph Metric </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Farhadi,+M">Majid Farhadi</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Louis,+A">Anand Louis</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Singh,+M">Mohit Singh</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Tetali,+P">Prasad Tetali</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span>; Data Structures and Algorithms (cs.DS) </div> </div> </dd> <dt> <a name='item12'>[12]</a> <a href ="/abs/2003.05874" title="Abstract" id="2003.05874"> arXiv:2003.05874 </a> [<a href="/pdf/2003.05874" title="Download PDF" id="pdf-2003.05874" aria-labelledby="pdf-2003.05874">pdf</a>, <a href="/format/2003.05874" title="Other formats" id="oth-2003.05874" aria-labelledby="oth-2003.05874">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> New Exponential Size Lower Bounds against Depth Four Circuits of Bounded Individual Degree </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Chillara,+S">Suryajith Chillara</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span> </div> </div> </dd> <dt> <a name='item13'>[13]</a> <a href ="/abs/2003.06993" title="Abstract" id="2003.06993"> arXiv:2003.06993 </a> [<a href="/pdf/2003.06993" title="Download PDF" id="pdf-2003.06993" aria-labelledby="pdf-2003.06993">pdf</a>, <a href="/format/2003.06993" title="Other formats" id="oth-2003.06993" aria-labelledby="oth-2003.06993">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Space Hardness of Solving Structured Linear Systems </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Huang,+X">Xuangui Huang</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span> </div> </div> </dd> <dt> <a name='item14'>[14]</a> <a href ="/abs/2003.07190" title="Abstract" id="2003.07190"> arXiv:2003.07190 </a> [<a href="/pdf/2003.07190" title="Download PDF" id="pdf-2003.07190" aria-labelledby="pdf-2003.07190">pdf</a>, <a href="/format/2003.07190" title="Other formats" id="oth-2003.07190" aria-labelledby="oth-2003.07190">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> On the parameterized complexity of 2-partitions </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Andersen,+J+B">Jonas Bamse Andersen</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Bang-Jensen,+J">J酶rgen Bang-Jensen</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Yeo,+A">Anders Yeo</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span> </div> </div> </dd> <dt> <a name='item15'>[15]</a> <a href ="/abs/2003.07487" title="Abstract" id="2003.07487"> arXiv:2003.07487 </a> [<a href="/pdf/2003.07487" title="Download PDF" id="pdf-2003.07487" aria-labelledby="pdf-2003.07487">pdf</a>, <a href="/format/2003.07487" title="Other formats" id="oth-2003.07487" aria-labelledby="oth-2003.07487">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Sandwiches for Promise Constraint Satisfaction </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Deng,+G">Guofeng Deng</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Sai,+E+E">Ezzeddine El Sai</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Manders,+T">Trevor Manders</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Mayr,+P">Peter Mayr</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Nakkirt,+P">Poramate Nakkirt</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Sparks,+A">Athena Sparks</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span> </div> </div> </dd> <dt> <a name='item16'>[16]</a> <a href ="/abs/2003.07903" title="Abstract" id="2003.07903"> arXiv:2003.07903 </a> [<a href="/pdf/2003.07903" title="Download PDF" id="pdf-2003.07903" aria-labelledby="pdf-2003.07903">pdf</a>, <a href="/format/2003.07903" title="Other formats" id="oth-2003.07903" aria-labelledby="oth-2003.07903">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Hardness of Bounded Distance Decoding on Lattices in $\ell_p$ Norms </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Bennett,+H">Huck Bennett</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Peikert,+C">Chris Peikert</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span>; Data Structures and Algorithms (cs.DS) </div> </div> </dd> <dt> <a name='item17'>[17]</a> <a href ="/abs/2003.08331" title="Abstract" id="2003.08331"> arXiv:2003.08331 </a> [<a href="/pdf/2003.08331" title="Download PDF" id="pdf-2003.08331" aria-labelledby="pdf-2003.08331">pdf</a>, <a href="/format/2003.08331" title="Other formats" id="oth-2003.08331" aria-labelledby="oth-2003.08331">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Tatamibari is NP-complete </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Adler,+A">Aviv Adler</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Bosboom,+J">Jeffrey Bosboom</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Demaine,+E+D">Erik D. Demaine</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Demaine,+M+L">Martin L. Demaine</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Liu,+Q+C">Quanquan C. Liu</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Lynch,+J">Jayson Lynch</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 26 pages, 21 figures. New discussion of safe placement of wires in Sections 3.2 and 3.5. To appear at the 10th International Conference on Fun with Algorithms (FUN 2020) </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span>; Computational Geometry (cs.CG) </div> </div> </dd> <dt> <a name='item18'>[18]</a> <a href ="/abs/2003.09791" title="Abstract" id="2003.09791"> arXiv:2003.09791 </a> [<a href="/pdf/2003.09791" title="Download PDF" id="pdf-2003.09791" aria-labelledby="pdf-2003.09791">pdf</a>, <a href="/format/2003.09791" title="Other formats" id="oth-2003.09791" aria-labelledby="oth-2003.09791">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> A "Proof" of $P\neq NP$ </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Lin,+T">Tianrong Lin</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> Withdrawn, since $\mathbb{N}\subseteq S$ and the mathmaticans do not acknowledge that $\mathbb{N}$ is bounded from above which is very crucial. See <a href="https://arxiv.org/abs/2110.06211" data-arxiv-id="2110.06211" class="link-https">arXiv:2110.06211</a> </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span> </div> </div> </dd> <dt> <a name='item19'>[19]</a> <a href ="/abs/2003.09877" title="Abstract" id="2003.09877"> arXiv:2003.09877 </a> [<a href="/pdf/2003.09877" title="Download PDF" id="pdf-2003.09877" aria-labelledby="pdf-2003.09877">pdf</a>, <a href="/format/2003.09877" title="Other formats" id="oth-2003.09877" aria-labelledby="oth-2003.09877">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Remscrim,+Z">Zachary Remscrim</a> (University of Chicago)</div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> In ITCS 2021 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span> </div> </div> </dd> <dt> <a name='item20'>[20]</a> <a href ="/abs/2003.09879" title="Abstract" id="2003.09879"> arXiv:2003.09879 </a> [<a href="/pdf/2003.09879" title="Download PDF" id="pdf-2003.09879" aria-labelledby="pdf-2003.09879">pdf</a>, <a href="/format/2003.09879" title="Other formats" id="oth-2003.09879" aria-labelledby="oth-2003.09879">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> The Power of a Single Qubit: Two-way Quantum Finite Automata and the Word Problem </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Remscrim,+Z">Zachary Remscrim</a> (MIT)</div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> To appear in ICALP 2020 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span>; Quantum Physics (quant-ph) </div> </div> </dd> <dt> <a name='item21'>[21]</a> <a href ="/abs/2003.09914" title="Abstract" id="2003.09914"> arXiv:2003.09914 </a> [<a href="/pdf/2003.09914" title="Download PDF" id="pdf-2003.09914" aria-labelledby="pdf-2003.09914">pdf</a>, <a href="/format/2003.09914" title="Other formats" id="oth-2003.09914" aria-labelledby="oth-2003.09914">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> 1 x 1 Rush Hour with Fixed Blocks is PSPACE-complete </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Brunner,+J">Josh Brunner</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Chung,+L">Lily Chung</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Demaine,+E+D">Erik D. Demaine</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Hendrickson,+D">Dylan Hendrickson</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Hesterberg,+A">Adam Hesterberg</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Suhl,+A">Adam Suhl</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Zeff,+A">Avi Zeff</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 15 pages, 11 figures. Improved figures and writing. To appear at FUN 2020 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span>; Computational Geometry (cs.CG) </div> </div> </dd> <dt> <a name='item22'>[22]</a> <a href ="/abs/2003.10000" title="Abstract" id="2003.10000"> arXiv:2003.10000 </a> [<a href="/pdf/2003.10000" title="Download PDF" id="pdf-2003.10000" aria-labelledby="pdf-2003.10000">pdf</a>, <a href="/format/2003.10000" title="Other formats" id="oth-2003.10000" aria-labelledby="oth-2003.10000">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> The Computational Complexity of Evil Hangman </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Barbay,+J">J茅r茅my Barbay</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Subercaseaux,+B">Bernardo Subercaseaux</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 13 pages, 4 figures, Accepted at FUN2020 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span> </div> </div> </dd> <dt> <a name='item23'>[23]</a> <a href ="/abs/2003.10230" title="Abstract" id="2003.10230"> arXiv:2003.10230 </a> [<a href="/pdf/2003.10230" title="Download PDF" id="pdf-2003.10230" aria-labelledby="pdf-2003.10230">pdf</a>, <a href="/format/2003.10230" title="Other formats" id="oth-2003.10230" aria-labelledby="oth-2003.10230">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Failure of Feasible Disjunction Property for $k$-DNF Resolution and NP-hardness of Automating It </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Garl%C3%ADk,+M">Michal Garl铆k</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> arXiv admin note: text overlap with <a href="https://arxiv.org/abs/1905.12372" data-arxiv-id="1905.12372" class="link-https">arXiv:1905.12372</a> </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span>; Logic (math.LO) </div> </div> </dd> <dt> <a name='item24'>[24]</a> <a href ="/abs/2003.11351" title="Abstract" id="2003.11351"> arXiv:2003.11351 </a> [<a href="/pdf/2003.11351" title="Download PDF" id="pdf-2003.11351" aria-labelledby="pdf-2003.11351">pdf</a>, <a href="/format/2003.11351" title="Other formats" id="oth-2003.11351" aria-labelledby="oth-2003.11351">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Topology and adjunction in promise constraint satisfaction </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Krokhin,+A">Andrei Krokhin</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Opr%C5%A1al,+J">Jakub Opr拧al</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Wrochna,+M">Marcin Wrochna</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=%C5%BDivn%C3%BD,+S">Stanislav 沤ivn媒</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> This merges and subsumes <a href="https://arxiv.org/abs/1904.03214" data-arxiv-id="1904.03214" class="link-https">arXiv:1904.03214</a> and <a href="https://arxiv.org/abs/1907.00872" data-arxiv-id="1907.00872" class="link-https">arXiv:1907.00872</a>. After reviews </div> <div class='list-journal-ref'><span class='descriptor'>Journal-ref:</span> SIAM Journal on Computing 52(1) (2023) 38-79 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span>; Discrete Mathematics (cs.DM); Logic in Computer Science (cs.LO); Algebraic Topology (math.AT) </div> </div> </dd> <dt> <a name='item25'>[25]</a> <a href ="/abs/2003.11764" title="Abstract" id="2003.11764"> arXiv:2003.11764 </a> [<a href="/pdf/2003.11764" title="Download PDF" id="pdf-2003.11764" aria-labelledby="pdf-2003.11764">pdf</a>, <a href="/format/2003.11764" title="Other formats" id="oth-2003.11764" aria-labelledby="oth-2003.11764">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> No-Rainbow Problem and the Surjective Constraint Satisfaction Problem </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Zhuk,+D">Dmitriy Zhuk</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span>; Logic in Computer Science (cs.LO); Rings and Algebras (math.RA) </div> </div> </dd> <dt> <a name='item26'>[26]</a> <a href ="/abs/2003.11974" title="Abstract" id="2003.11974"> arXiv:2003.11974 </a> [<a href="/pdf/2003.11974" title="Download PDF" id="pdf-2003.11974" aria-labelledby="pdf-2003.11974">pdf</a>, <a href="/format/2003.11974" title="Other formats" id="oth-2003.11974" aria-labelledby="oth-2003.11974">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> A Topological Characterization of Modulo-$p$ Arguments and Implications for Necklace Splitting </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Filos-Ratsikas,+A">Aris Filos-Ratsikas</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Hollender,+A">Alexandros Hollender</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Sotiraki,+K">Katerina Sotiraki</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Zampetakis,+M">Manolis Zampetakis</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> v2: improved presentation based on reviewer comments and suggestions </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span>; Computational Geometry (cs.CG); Discrete Mathematics (cs.DM) </div> </div> </dd> <dt> <a name='item27'>[27]</a> <a href ="/abs/2003.12938" title="Abstract" id="2003.12938"> arXiv:2003.12938 </a> [<a href="/pdf/2003.12938" title="Download PDF" id="pdf-2003.12938" aria-labelledby="pdf-2003.12938">pdf</a>, <a href="/format/2003.12938" title="Other formats" id="oth-2003.12938" aria-labelledby="oth-2003.12938">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> A Polynomial Degree Bound on Equations of Non-rigid Matrices and Small Linear Circuits </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Kumar,+M">Mrinal Kumar</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Volk,+B+L">Ben Lee Volk</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span>; Algebraic Geometry (math.AG) </div> </div> </dd> <dt> <a name='item28'>[28]</a> <a href ="/abs/2003.13065" title="Abstract" id="2003.13065"> arXiv:2003.13065 </a> [<a href="/pdf/2003.13065" title="Download PDF" id="pdf-2003.13065" aria-labelledby="pdf-2003.13065">pdf</a>, <a href="/format/2003.13065" title="Other formats" id="oth-2003.13065" aria-labelledby="oth-2003.13065">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Two combinatorial MA-complete problems </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Aharonov,+D">Dorit Aharonov</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Grilo,+A+B">Alex B. Grilo</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> Minor changes; Published in the proceedings of ITCS 2021 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span> </div> </div> </dd> <dt> <a name='item29'>[29]</a> <a href ="/abs/2003.13558" title="Abstract" id="2003.13558"> arXiv:2003.13558 </a> [<a href="/pdf/2003.13558" title="Download PDF" id="pdf-2003.13558" aria-labelledby="pdf-2003.13558">pdf</a>, <a href="/format/2003.13558" title="Other formats" id="oth-2003.13558" aria-labelledby="oth-2003.13558">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> A faster algorithm for the FSSP in one-dimensional CA with multiple speeds </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Worsch,+T">Thomas Worsch</a> (Karlsruhe Institute of Technology)</div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 11 pages, 3 figures </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Complexity (cs.CC)</span>; Formal Languages and Automata Theory (cs.FL); Cellular Automata and Lattice Gases (nlin.CG) </div> </div> </dd> <dt> <a name='item30'>[30]</a> <a href ="/abs/2003.00314" title="Abstract" id="2003.00314"> arXiv:2003.00314 </a> (cross-list from math.NT) [<a href="/pdf/2003.00314" title="Download PDF" id="pdf-2003.00314" aria-labelledby="pdf-2003.00314">pdf</a>, <a href="/format/2003.00314" title="Other formats" id="oth-2003.00314" aria-labelledby="oth-2003.00314">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> A complexity chasm for solving univariate sparse polynomial equations over $p$-adic fields </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Rojas,+J+M">J. Maurice Rojas</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Zhu,+Y">Yuyu Zhu</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 19 pages, 3 figures. This version contains an Appendix missing from the ISSAC 2021 conference version, as well as some corrections and improvements </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Number Theory (math.NT)</span>; Computational Complexity (cs.CC); Symbolic Computation (cs.SC) </div> </div> </dd> <dt> <a name='item31'>[31]</a> <a href ="/abs/2003.00644" title="Abstract" id="2003.00644"> arXiv:2003.00644 </a> (cross-list from cs.LO) [<a href="/pdf/2003.00644" title="Download PDF" id="pdf-2003.00644" aria-labelledby="pdf-2003.00644">pdf</a>, <a href="/format/2003.00644" title="Other formats" id="oth-2003.00644" aria-labelledby="oth-2003.00644">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Descriptive complexity of real computation and probabilistic independence logic </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Hannula,+M">Miika Hannula</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Kontinen,+J">Juha Kontinen</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Van+den+Bussche,+J">Jan Van den Bussche</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Virtema,+J">Jonni Virtema</a></div> <div class='list-journal-ref'><span class='descriptor'>Journal-ref:</span> Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2020. Association for Computing Machinery, New York, NY, USA, 550-563 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Logic in Computer Science (cs.LO)</span>; Computational Complexity (cs.CC); Logic (math.LO) </div> </div> </dd> <dt> <a name='item32'>[32]</a> <a href ="/abs/2003.00963" title="Abstract" id="2003.00963"> arXiv:2003.00963 </a> (cross-list from math.OC) [<a href="/pdf/2003.00963" title="Download PDF" id="pdf-2003.00963" aria-labelledby="pdf-2003.00963">pdf</a>, <a href="/format/2003.00963" title="Other formats" id="oth-2003.00963" aria-labelledby="oth-2003.00963">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Piecewise Linear Valued Constraint Satisfaction Problems with Fixed Number of Variables </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Bodirsky,+M">Manuel Bodirsky</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Mamino,+M">Marcello Mamino</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Viola,+C">Caterina Viola</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 10 pages. Accepted for presentation at CTW2020 and publication in AIRO Springer Series </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Optimization and Control (math.OC)</span>; Computational Complexity (cs.CC); Logic in Computer Science (cs.LO) </div> </div> </dd> <dt> <a name='item33'>[33]</a> <a href ="/abs/2003.02583" title="Abstract" id="2003.02583"> arXiv:2003.02583 </a> (cross-list from cs.CG) [<a href="/pdf/2003.02583" title="Download PDF" id="pdf-2003.02583" aria-labelledby="pdf-2003.02583">pdf</a>, <a href="/format/2003.02583" title="Other formats" id="oth-2003.02583" aria-labelledby="oth-2003.02583">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Maximum Clique in Disk-Like Intersection Graphs </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Bonnet,+%C3%89">脡douard Bonnet</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Grelier,+N">Nicolas Grelier</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Miltzow,+T">Tillmann Miltzow</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 23 pages, 5 figures </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Geometry (cs.CG)</span>; Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS) </div> </div> </dd> <dt> <a name='item34'>[34]</a> <a href ="/abs/2003.02866" title="Abstract" id="2003.02866"> arXiv:2003.02866 </a> (cross-list from cs.DS) [<a href="/pdf/2003.02866" title="Download PDF" id="pdf-2003.02866" aria-labelledby="pdf-2003.02866">pdf</a>, <a href="/format/2003.02866" title="Other formats" id="oth-2003.02866" aria-labelledby="oth-2003.02866">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Linear-Time Parameterized Algorithms with Limited Local Resources </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Chen,+J">Jianer Chen</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Guo,+Y">Ying Guo</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Huang,+Q">Qin Huang</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='item35'>[35]</a> <a href ="/abs/2003.02962" title="Abstract" id="2003.02962"> arXiv:2003.02962 </a> (cross-list from math.RT) [<a href="/pdf/2003.02962" title="Download PDF" id="pdf-2003.02962" aria-labelledby="pdf-2003.02962">pdf</a>, <a href="/format/2003.02962" title="Other formats" id="oth-2003.02962" aria-labelledby="oth-2003.02962">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Simultaneous robust subspace recovery and semi-stability of quiver representations </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Chindris,+C">Calin Chindris</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Kline,+D">Daniel Kline</a></div> <div class='list-journal-ref'><span class='descriptor'>Journal-ref:</span> Journal of Algebra, Volume 577, 1 July 2021, Pages 210-236 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Representation Theory (math.RT)</span>; Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS) </div> </div> </dd> <dt> <a name='item36'>[36]</a> <a href ="/abs/2003.04438" title="Abstract" id="2003.04438"> arXiv:2003.04438 </a> (cross-list from math.OC) [<a href="/pdf/2003.04438" title="Download PDF" id="pdf-2003.04438" aria-labelledby="pdf-2003.04438">pdf</a>, <a href="/format/2003.04438" title="Other formats" id="oth-2003.04438" aria-labelledby="oth-2003.04438">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> On the computational complexity of uncapacitated multi-plant lot-sizing problems </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Cunha,+J+O">J. O. Cunha</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Kramer,+H+H">H. H. Kramer</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Melo,+R+A">R. A. Melo</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Optimization and Control (math.OC)</span>; Computational Complexity (cs.CC) </div> </div> </dd> <dt> <a name='item37'>[37]</a> <a href ="/abs/2003.05023" title="Abstract" id="2003.05023"> arXiv:2003.05023 </a> (cross-list from math.OC) [<a href="/pdf/2003.05023" title="Download PDF" id="pdf-2003.05023" aria-labelledby="pdf-2003.05023">pdf</a>, <a href="/format/2003.05023" title="Other formats" id="oth-2003.05023" aria-labelledby="oth-2003.05023">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Complexity of branch-and-bound and cutting planes in mixed-integer optimization </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Basu,+A">Amitabh Basu</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Conforti,+M">Michele Conforti</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Di+Summa,+M">Marco Di Summa</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Jiang,+H">Hongyi Jiang</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Optimization and Control (math.OC)</span>; Computational Complexity (cs.CC) </div> </div> </dd> <dt> <a name='item38'>[38]</a> <a href ="/abs/2003.05119" title="Abstract" id="2003.05119"> arXiv:2003.05119 </a> (cross-list from cs.AI) [<a href="/pdf/2003.05119" title="Download PDF" id="pdf-2003.05119" aria-labelledby="pdf-2003.05119">pdf</a>, <a href="/format/2003.05119" title="Other formats" id="oth-2003.05119" aria-labelledby="oth-2003.05119">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Magic: the Gathering is as Hard as Arithmetic </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Biderman,+S">Stella Biderman</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> pre-print, currently under review </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Artificial Intelligence (cs.AI)</span>; Computational Complexity (cs.CC); Logic in Computer Science (cs.LO) </div> </div> </dd> <dt> <a name='item39'>[39]</a> <a href ="/abs/2003.05575" title="Abstract" id="2003.05575"> arXiv:2003.05575 </a> (cross-list from cs.DC) [<a href="/pdf/2003.05575" title="Download PDF" id="pdf-2003.05575" aria-labelledby="pdf-2003.05575">pdf</a>, <a href="/format/2003.05575" title="Other formats" id="oth-2003.05575" aria-labelledby="oth-2003.05575">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Topology Dependent Bounds For FAQs </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Langberg,+M">Michael Langberg</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Li,+S">Shi Li</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Jayaraman,+S+V+M">Sai Vikneshwar Mani Jayaraman</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Rudra,+A">Atri Rudra</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> A conference version was presented at PODS 2019 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Distributed, Parallel, and Cluster Computing (cs.DC)</span>; Computational Complexity (cs.CC); Databases (cs.DB) </div> </div> </dd> <dt> <a name='item40'>[40]</a> <a href ="/abs/2003.05706" title="Abstract" id="2003.05706"> arXiv:2003.05706 </a> (cross-list from math.DS) [<a href="/pdf/2003.05706" title="Download PDF" id="pdf-2003.05706" aria-labelledby="pdf-2003.05706">pdf</a>, <a href="/format/2003.05706" title="Other formats" id="oth-2003.05706" aria-labelledby="oth-2003.05706">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Four heads are better than three </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Salo,+V">Ville Salo</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 14 pages </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Dynamical Systems (math.DS)</span>; Computational Complexity (cs.CC); Formal Languages and Automata Theory (cs.FL); Group Theory (math.GR); Logic (math.LO) </div> </div> </dd> <dt> <a name='item41'>[41]</a> <a href ="/abs/2003.05913" title="Abstract" id="2003.05913"> arXiv:2003.05913 </a> (cross-list from cs.GT) [<a href="/pdf/2003.05913" title="Download PDF" id="pdf-2003.05913" aria-labelledby="pdf-2003.05913">pdf</a>, <a href="/format/2003.05913" title="Other formats" id="oth-2003.05913" aria-labelledby="oth-2003.05913">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Escaping Cannibalization? Correlation-Robust Pricing for a Unit-Demand Buyer </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Babaioff,+M">Moshe Babaioff</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Feldman,+M">Michal Feldman</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Gonczarowski,+Y+A">Yannai A. Gonczarowski</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Lucier,+B">Brendan Lucier</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Talgam-Cohen,+I">Inbal Talgam-Cohen</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computer Science and Game Theory (cs.GT)</span>; Computational Complexity (cs.CC); Theoretical Economics (econ.TH) </div> </div> </dd> <dt> <a name='item42'>[42]</a> <a href ="/abs/2003.06879" title="Abstract" id="2003.06879"> arXiv:2003.06879 </a> (cross-list from cs.GT) [<a href="/pdf/2003.06879" title="Download PDF" id="pdf-2003.06879" aria-labelledby="pdf-2003.06879">pdf</a>, <a href="/format/2003.06879" title="Other formats" id="oth-2003.06879" aria-labelledby="oth-2003.06879">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Selecting Voting Locations for Fun and Profit </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Fitzsimmons,+Z">Zack Fitzsimmons</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Lev,+O">Omer Lev</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computer Science and Game Theory (cs.GT)</span>; Computational Complexity (cs.CC); Multiagent Systems (cs.MA) </div> </div> </dd> <dt> <a name='item43'>[43]</a> <a href ="/abs/2003.07345" title="Abstract" id="2003.07345"> arXiv:2003.07345 </a> (cross-list from math.FA) [<a href="/pdf/2003.07345" title="Download PDF" id="pdf-2003.07345" aria-labelledby="pdf-2003.07345">pdf</a>, <a href="/format/2003.07345" title="Other formats" id="oth-2003.07345" aria-labelledby="oth-2003.07345">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Symmetric Grothendieck inequality </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Friedland,+S">Shmuel Friedland</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Lim,+L">Lek-Heng Lim</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 42 pages </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Functional Analysis (math.FA)</span>; Computational Complexity (cs.CC) </div> </div> </dd> <dt> <a name='item44'>[44]</a> <a href ="/abs/2003.08329" title="Abstract" id="2003.08329"> arXiv:2003.08329 </a> (cross-list from cs.CG) [<a href="/pdf/2003.08329" title="Download PDF" id="pdf-2003.08329" aria-labelledby="pdf-2003.08329">pdf</a>, <a href="/format/2003.08329" title="Other formats" id="oth-2003.08329" aria-labelledby="oth-2003.08329">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> A Generalization of Self-Improving Algorithms </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Cheng,+S">Siu-Wing Cheng</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Chiu,+M">Man-Kwun Chiu</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Jin,+K">Kai Jin</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Wong,+M+T">Man Ting Wong</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Geometry (cs.CG)</span>; Computational Complexity (cs.CC) </div> </div> </dd> <dt> <a name='item45'>[45]</a> <a href ="/abs/2003.09266" title="Abstract" id="2003.09266"> arXiv:2003.09266 </a> (cross-list from cs.CG) [<a href="/pdf/2003.09266" title="Download PDF" id="pdf-2003.09266" aria-labelledby="pdf-2003.09266">pdf</a>, <a href="/format/2003.09266" title="Other formats" id="oth-2003.09266" aria-labelledby="oth-2003.09266">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Computational Complexity of the $伪$-Ham-Sandwich Problem </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Chiu,+M">Man-Kwun Chiu</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Choudhary,+A">Aruni Choudhary</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Mulzer,+W">Wolfgang Mulzer</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Computational Geometry (cs.CG)</span>; Computational Complexity (cs.CC) </div> </div> </dd> <dt> <a name='item46'>[46]</a> <a href ="/abs/2003.09532" title="Abstract" id="2003.09532"> arXiv:2003.09532 </a> (cross-list from cs.DC) [<a href="/pdf/2003.09532" title="Download PDF" id="pdf-2003.09532" aria-labelledby="pdf-2003.09532">pdf</a>, <a href="/format/2003.09532" title="Other formats" id="oth-2003.09532" aria-labelledby="oth-2003.09532">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Message complexity of population protocols </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Amir,+T">Talley Amir</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Aspnes,+J">James Aspnes</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Doty,+D">David Doty</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Eftekhari,+M">Mahsa Eftekhari</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Severson,+E">Eric Severson</a></div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Distributed, Parallel, and Cluster Computing (cs.DC)</span>; Computational Complexity (cs.CC) </div> </div> </dd> <dt> <a name='item47'>[47]</a> <a href ="/abs/2003.10570" title="Abstract" id="2003.10570"> arXiv:2003.10570 </a> (cross-list from cs.DS) [<a href="/pdf/2003.10570" title="Download PDF" id="pdf-2003.10570" aria-labelledby="pdf-2003.10570">pdf</a>, <a href="/format/2003.10570" title="Other formats" id="oth-2003.10570" aria-labelledby="oth-2003.10570">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> On the complexity of Broadcast Domination and Multipacking in digraphs </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Foucaud,+F">Florent Foucaud</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Gras,+B">Benjamin Gras</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Perez,+A">Anthony Perez</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Sikora,+F">Florian Sikora</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> Extended abstract to appear in proceedings of IWOCA 2020 </div> <div class='list-journal-ref'><span class='descriptor'>Journal-ref:</span> Algorithmica 83(9):2651-2677, 2021 </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/2003.10712" title="Abstract" id="2003.10712"> arXiv:2003.10712 </a> (cross-list from quant-ph) [<a href="/pdf/2003.10712" title="Download PDF" id="pdf-2003.10712" aria-labelledby="pdf-2003.10712">pdf</a>, <a href="/format/2003.10712" title="Other formats" id="oth-2003.10712" aria-labelledby="oth-2003.10712">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Information-theoretically-sound non-interactive classical verification of quantum computing with trusted center </div> <div class='list-authors'><a href="https://arxiv.org/search/quant-ph?searchtype=author&query=Morimae,+T">Tomoyuki Morimae</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> 14 pages, no figure </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Quantum Physics (quant-ph)</span>; Computational Complexity (cs.CC); Cryptography and Security (cs.CR) </div> </div> </dd> <dt> <a name='item49'>[49]</a> <a href ="/abs/2003.11313" title="Abstract" id="2003.11313"> arXiv:2003.11313 </a> (cross-list from cs.DM) [<a href="/pdf/2003.11313" title="Download PDF" id="pdf-2003.11313" aria-labelledby="pdf-2003.11313">pdf</a>, <a href="/format/2003.11313" title="Other formats" id="oth-2003.11313" aria-labelledby="oth-2003.11313">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> Fair allocation of indivisible items with conflict graphs </div> <div class='list-authors'><a href="https://arxiv.org/search/cs?searchtype=author&query=Chiarelli,+N">Nina Chiarelli</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Krnc,+M">Matja啪 Krnc</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Milani%C4%8D,+M">Martin Milani膷</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Pferschy,+U">Ulrich Pferschy</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Piva%C4%8D,+N">Nevena Piva膷</a>, <a href="https://arxiv.org/search/cs?searchtype=author&query=Schauer,+J">Joachim Schauer</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> A preliminary version containing some of the results presented here appeared in the proceedings of IWOCA 2020 </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Discrete Mathematics (cs.DM)</span>; Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC) </div> </div> </dd> <dt> <a name='item50'>[50]</a> <a href ="/abs/2003.11951" title="Abstract" id="2003.11951"> arXiv:2003.11951 </a> (cross-list from math.OC) [<a href="/pdf/2003.11951" title="Download PDF" id="pdf-2003.11951" aria-labelledby="pdf-2003.11951">pdf</a>, <a href="/format/2003.11951" title="Other formats" id="oth-2003.11951" aria-labelledby="oth-2003.11951">other</a>] </dt> <dd> <div class='meta'> <div class='list-title mathjax'><span class='descriptor'>Title:</span> On the Complexity and Approximability of Optimal Sensor Selection and Attack for Kalman Filtering </div> <div class='list-authors'><a href="https://arxiv.org/search/math?searchtype=author&query=Ye,+L">Lintao Ye</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Woodford,+N">Nathaniel Woodford</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Roy,+S">Sandip Roy</a>, <a href="https://arxiv.org/search/math?searchtype=author&query=Sundaram,+S">Shreyas Sundaram</a></div> <div class='list-comments mathjax'><span class='descriptor'>Comments:</span> arXiv admin note: text overlap with <a href="https://arxiv.org/abs/1711.01920" data-arxiv-id="1711.01920" class="link-https">arXiv:1711.01920</a> </div> <div class='list-subjects'><span class='descriptor'>Subjects:</span> <span class="primary-subject">Optimization and Control (math.OC)</span>; Computational Complexity (cs.CC); Systems and Control (eess.SY) </div> </div> </dd> </dl> <div class='paging'>Total of 50 entries </div> <div class='morefewer'>Showing up to 50 entries per page: <a href=/list/cs.CC/2020-03?skip=0&show=25 rel="nofollow"> fewer</a> | <span style="color: #454545">more</span> | <span style="color: #454545">all</span> </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

Computational Complexity Mar 2020