Search | arXiv e-print repository

<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"/> <meta name="viewport" content="width=device-width, initial-scale=1"/>  <link rel="apple-touch-icon" sizes="180x180" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/apple-touch-icon.png"> <link rel="icon" type="image/png" sizes="32x32" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon-32x32.png"> <link rel="icon" type="image/png" sizes="16x16" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon-16x16.png"> <link rel="manifest" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/site.webmanifest"> <link rel="mask-icon" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/safari-pinned-tab.svg" color="#b31b1b"> <link rel="shortcut icon" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon.ico"> <meta name="msapplication-TileColor" content="#b31b1b"> <meta name="msapplication-config" content="images/icons/browserconfig.xml"> <meta name="theme-color" content="#b31b1b">  <title>Search | arXiv e-print repository</title> <script defer src="https://static.arxiv.org/static/base/1.0.0a5/fontawesome-free-5.11.2-web/js/all.js"></script> <link rel="stylesheet" href="https://static.arxiv.org/static/base/1.0.0a5/css/arxivstyle.css" /> <script type="text/x-mathjax-config"> MathJax.Hub.Config({ messageStyle: "none", extensions: ["tex2jax.js"], jax: ["input/TeX", "output/HTML-CSS"], tex2jax: { inlineMath: [ ['$','$'], ["\$","\$"] ], displayMath: [ ['$$','$$'], ["\\[","\\]"] ], processEscapes: true, ignoreClass: '.*', processClass: 'mathjax.*' }, TeX: { extensions: ["AMSmath.js", "AMSsymbols.js", "noErrors.js"], noErrors: { inlineDelimiters: ["$","$"], multiLine: false, style: { "font-size": "normal", "border": "" } } }, "HTML-CSS": { availableFonts: ["TeX"] } }); </script> <script src='//static.arxiv.org/MathJax-2.7.3/MathJax.js'></script> <script src="https://static.arxiv.org/static/base/1.0.0a5/js/notification.js"></script> <link rel="stylesheet" href="https://static.arxiv.org/static/search/0.5.6/css/bulma-tooltip.min.css" /> <link rel="stylesheet" href="https://static.arxiv.org/static/search/0.5.6/css/search.css" /> <script src="https://code.jquery.com/jquery-3.2.1.slim.min.js" integrity="sha256-k2WSCIexGzOj3Euiig+TlR8gA0EmPjuc79OEeY5L45g=" crossorigin="anonymous"></script> <script src="https://static.arxiv.org/static/search/0.5.6/js/fieldset.js"></script> <style> radio#cf-customfield_11400 { display: none; } </style> </head> <body> <header><a href="#main-container" class="is-sr-only">Skip to main content</a>  <div class="attribution level is-marginless" role="banner"> <div class="level-left"> <a class="level-item" href="https://cornell.edu/"><img src="https://static.arxiv.org/static/base/1.0.0a5/images/cornell-reduced-white-SMALL.svg" alt="Cornell University" width="200" aria-label="logo" /></a> </div> <div class="level-right is-marginless"><p class="sponsors level-item is-marginless"><span id="support-ack-url">We gratefully acknowledge support from<br /> the Simons Foundation, <a href="https://info.arxiv.org/about/ourmembers.html">member institutions</a>, and all contributors. <a href="https://info.arxiv.org/about/donate.html">Donate</a></span></p></div> </div>  <div class="identity level is-marginless"> <div class="level-left"> <div class="level-item"> <a class="arxiv" href="https://arxiv.org/" aria-label="arxiv-logo"> <img src="https://static.arxiv.org/static/base/1.0.0a5/images/arxiv-logo-one-color-white.svg" aria-label="logo" alt="arxiv logo" width="85" style="width:85px;"/> </a> </div> </div> <div class="search-block level-right"> <form class="level-item mini-search" method="GET" action="https://arxiv.org/search"> <div class="field has-addons"> <div class="control"> <input class="input is-small" type="text" name="query" placeholder="Search..." aria-label="Search term or terms" /> <p class="help"><a href="https://info.arxiv.org/help">Help</a> | <a href="https://arxiv.org/search/advanced">Advanced Search</a></p> </div> <div class="control"> <div class="select is-small"> <select name="searchtype" aria-label="Field to search"> <option value="all" selected="selected">All fields</option> <option value="title">Title</option> <option value="author">Author</option> <option value="abstract">Abstract</option> <option value="comments">Comments</option> <option value="journal_ref">Journal reference</option> <option value="acm_class">ACM classification</option> <option value="msc_class">MSC classification</option> <option value="report_num">Report number</option> <option value="paper_id">arXiv identifier</option> <option value="doi">DOI</option> <option value="orcid">ORCID</option> <option value="author_id">arXiv author ID</option> <option value="help">Help pages</option> <option value="full_text">Full text</option> </select> </div> </div> <input type="hidden" name="source" value="header"> <button class="button is-small is-cul-darker">Search</button> </div> </form> </div> </div>  <div class="container"> <div class="user-tools is-size-7 has-text-right has-text-weight-bold" role="navigation" aria-label="User menu"> <a href="https://arxiv.org/login">Login</a> </div> </div> </header> <main class="container" id="main-container"> <div class="level is-marginless"> <div class="level-left"> <h1 class="title is-clearfix"> Showing 1–25 of 25 results for author: <span class="mathjax">Efrat, A</span> </h1> </div> <div class="level-right is-hidden-mobile">  <span class="help" style="display: inline-block;"><a href="https://github.com/arXiv/arxiv-search/releases">Search v0.5.6 released 2020-02-24</a>  </span> </div> </div> <div class="content"> <form method="GET" action="/search/cs" aria-role="search"> Searching in archive <strong>cs</strong>. <a href="/search/?searchtype=author&query=Efrat%2C+A">Search in all archives.</a> <div class="field has-addons-tablet"> <div class="control is-expanded"> <label for="query" class="hidden-label">Search term or terms</label> <input class="input is-medium" id="query" name="query" placeholder="Search term..." type="text" value="Efrat, A"> </div> <div class="select control is-medium"> <label class="is-hidden" for="searchtype">Field</label> <select class="is-medium" id="searchtype" name="searchtype"><option value="all">All fields</option><option value="title">Title</option><option selected value="author">Author(s)</option><option value="abstract">Abstract</option><option value="comments">Comments</option><option value="journal_ref">Journal reference</option><option value="acm_class">ACM classification</option><option value="msc_class">MSC classification</option><option value="report_num">Report number</option><option value="paper_id">arXiv identifier</option><option value="doi">DOI</option><option value="orcid">ORCID</option><option value="license">License (URI)</option><option value="author_id">arXiv author ID</option><option value="help">Help pages</option><option value="full_text">Full text</option></select> </div> <div class="control"> <button class="button is-link is-medium">Search</button> </div> </div> <div class="field"> <div class="control is-size-7"> <label class="radio"> <input checked id="abstracts-0" name="abstracts" type="radio" value="show"> Show abstracts </label> <label class="radio"> <input id="abstracts-1" name="abstracts" type="radio" value="hide"> Hide abstracts </label> </div> </div> <div class="is-clearfix" style="height: 2.5em"> <div class="is-pulled-right"> <a href="/search/advanced?terms-0-term=Efrat%2C+A&terms-0-field=author&size=50&order=-announced_date_first">Advanced Search</a> </div> </div> <input type="hidden" name="order" value="-announced_date_first"> <input type="hidden" name="size" value="50"> </form> <div class="level breathe-horizontal"> <div class="level-left"> <form method="GET" action="/search/"> <div style="display: none;"> <select id="searchtype" name="searchtype"><option value="all">All fields</option><option value="title">Title</option><option selected value="author">Author(s)</option><option value="abstract">Abstract</option><option value="comments">Comments</option><option value="journal_ref">Journal reference</option><option value="acm_class">ACM classification</option><option value="msc_class">MSC classification</option><option value="report_num">Report number</option><option value="paper_id">arXiv identifier</option><option value="doi">DOI</option><option value="orcid">ORCID</option><option value="license">License (URI)</option><option value="author_id">arXiv author ID</option><option value="help">Help pages</option><option value="full_text">Full text</option></select> <input id="query" name="query" type="text" value="Efrat, A"> <ul id="abstracts"><li><input checked id="abstracts-0" name="abstracts" type="radio" value="show"> <label for="abstracts-0">Show abstracts</label></li><li><input id="abstracts-1" name="abstracts" type="radio" value="hide"> <label for="abstracts-1">Hide abstracts</label></li></ul> </div> <div class="box field is-grouped is-grouped-multiline level-item"> <div class="control"> <span class="select is-small"> <select id="size" name="size"><option value="25">25</option><option selected value="50">50</option><option value="100">100</option><option value="200">200</option></select> </span> <label for="size">results per page</label>. </div> <div class="control"> <label for="order">Sort results by</label> <span class="select is-small"> <select id="order" name="order"><option selected value="-announced_date_first">Announcement date (newest first)</option><option value="announced_date_first">Announcement date (oldest first)</option><option value="-submitted_date">Submission date (newest first)</option><option value="submitted_date">Submission date (oldest first)</option><option value="">Relevance</option></select> </span> </div> <div class="control"> <button class="button is-small is-link">Go</button> </div> </div> </form> </div> </div> <ol class="breathe-horizontal" start="1"> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2309.07055">arXiv:2309.07055</a> <span> [<a href="https://arxiv.org/pdf/2309.07055">pdf</a>, <a href="https://arxiv.org/format/2309.07055">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computers and Society">cs.CY</span> </div> </div> <p class="title is-5 mathjax"> Unraveling the Geography of Infection Spread: Harnessing Super-Agents for Predictive Modeling </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Sikaroudi%2C+A+M+E">Amir Mohammad Esmaieeli Sikaroudi</a>, <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Alon Efrat</a>, <a href="/search/cs?searchtype=author&query=Chertkov%2C+M">Michael Chertkov</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2309.07055v5-abstract-short" style="display: inline;"> Our study presents an intermediate-level modeling approach that bridges the gap between complex Agent-Based Models (ABMs) and traditional compartmental models for infectious diseases. We introduce "super-agents" to simulate infection spread in cities, reducing computational complexity while retaining individual-level interactions. This approach leverages real-world mobility data and strategic geos… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2309.07055v5-abstract-full').style.display = 'inline'; document.getElementById('2309.07055v5-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2309.07055v5-abstract-full" style="display: none;"> Our study presents an intermediate-level modeling approach that bridges the gap between complex Agent-Based Models (ABMs) and traditional compartmental models for infectious diseases. We introduce "super-agents" to simulate infection spread in cities, reducing computational complexity while retaining individual-level interactions. This approach leverages real-world mobility data and strategic geospatial tessellations for efficiency. Voronoi Diagram tessellations, based on specific street network locations, outperform standard Census Block Group tessellations, and a hybrid approach balances accuracy and efficiency. Benchmarking against existing ABMs highlights key optimizations. This research improves disease modeling in urban areas, aiding public health strategies in scenarios requiring geographic specificity and high computational efficiency. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2309.07055v5-abstract-full').style.display = 'none'; document.getElementById('2309.07055v5-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 9 March, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 13 September, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2305.14196">arXiv:2305.14196</a> <span> [<a href="https://arxiv.org/pdf/2305.14196">pdf</a>, <a href="https://arxiv.org/format/2305.14196">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Artificial Intelligence">cs.AI</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> ZeroSCROLLS: A Zero-Shot Benchmark for Long Text Understanding </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Shaham%2C+U">Uri Shaham</a>, <a href="/search/cs?searchtype=author&query=Ivgi%2C+M">Maor Ivgi</a>, <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Avia Efrat</a>, <a href="/search/cs?searchtype=author&query=Berant%2C+J">Jonathan Berant</a>, <a href="/search/cs?searchtype=author&query=Levy%2C+O">Omer Levy</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2305.14196v3-abstract-short" style="display: inline;"> We introduce ZeroSCROLLS, a zero-shot benchmark for natural language understanding over long texts, which contains only test and small validation sets, without training data. We adapt six tasks from the SCROLLS benchmark, and add four new datasets, including two novel information fusing tasks, such as aggregating the percentage of positive reviews. Using ZeroSCROLLS, we conduct a comprehensive eva… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.14196v3-abstract-full').style.display = 'inline'; document.getElementById('2305.14196v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2305.14196v3-abstract-full" style="display: none;"> We introduce ZeroSCROLLS, a zero-shot benchmark for natural language understanding over long texts, which contains only test and small validation sets, without training data. We adapt six tasks from the SCROLLS benchmark, and add four new datasets, including two novel information fusing tasks, such as aggregating the percentage of positive reviews. Using ZeroSCROLLS, we conduct a comprehensive evaluation of both open-source and closed large language models, finding that Claude outperforms ChatGPT, and that GPT-4 achieves the highest average score. However, there is still room for improvement on multiple open challenges in ZeroSCROLLS, such as aggregation tasks, where models struggle to pass the naive baseline. As the state of the art is a moving target, we invite researchers to evaluate their ideas on the live ZeroSCROLLS leaderboard. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.14196v3-abstract-full').style.display = 'none'; document.getElementById('2305.14196v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 17 December, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 23 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Findings of EMNLP 2023</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2305.11206">arXiv:2305.11206</a> <span> [<a href="https://arxiv.org/pdf/2305.11206">pdf</a>, <a href="https://arxiv.org/format/2305.11206">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Artificial Intelligence">cs.AI</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> </div> </div> <p class="title is-5 mathjax"> LIMA: Less Is More for Alignment </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Zhou%2C+C">Chunting Zhou</a>, <a href="/search/cs?searchtype=author&query=Liu%2C+P">Pengfei Liu</a>, <a href="/search/cs?searchtype=author&query=Xu%2C+P">Puxin Xu</a>, <a href="/search/cs?searchtype=author&query=Iyer%2C+S">Srini Iyer</a>, <a href="/search/cs?searchtype=author&query=Sun%2C+J">Jiao Sun</a>, <a href="/search/cs?searchtype=author&query=Mao%2C+Y">Yuning Mao</a>, <a href="/search/cs?searchtype=author&query=Ma%2C+X">Xuezhe Ma</a>, <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Avia Efrat</a>, <a href="/search/cs?searchtype=author&query=Yu%2C+P">Ping Yu</a>, <a href="/search/cs?searchtype=author&query=Yu%2C+L">Lili Yu</a>, <a href="/search/cs?searchtype=author&query=Zhang%2C+S">Susan Zhang</a>, <a href="/search/cs?searchtype=author&query=Ghosh%2C+G">Gargi Ghosh</a>, <a href="/search/cs?searchtype=author&query=Lewis%2C+M">Mike Lewis</a>, <a href="/search/cs?searchtype=author&query=Zettlemoyer%2C+L">Luke Zettlemoyer</a>, <a href="/search/cs?searchtype=author&query=Levy%2C+O">Omer Levy</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2305.11206v1-abstract-short" style="display: inline;"> Large language models are trained in two stages: (1) unsupervised pretraining from raw text, to learn general-purpose representations, and (2) large scale instruction tuning and reinforcement learning, to better align to end tasks and user preferences. We measure the relative importance of these two stages by training LIMA, a 65B parameter LLaMa language model fine-tuned with the standard supervis… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.11206v1-abstract-full').style.display = 'inline'; document.getElementById('2305.11206v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2305.11206v1-abstract-full" style="display: none;"> Large language models are trained in two stages: (1) unsupervised pretraining from raw text, to learn general-purpose representations, and (2) large scale instruction tuning and reinforcement learning, to better align to end tasks and user preferences. We measure the relative importance of these two stages by training LIMA, a 65B parameter LLaMa language model fine-tuned with the standard supervised loss on only 1,000 carefully curated prompts and responses, without any reinforcement learning or human preference modeling. LIMA demonstrates remarkably strong performance, learning to follow specific response formats from only a handful of examples in the training data, including complex queries that range from planning trip itineraries to speculating about alternate history. Moreover, the model tends to generalize well to unseen tasks that did not appear in the training data. In a controlled human study, responses from LIMA are either equivalent or strictly preferred to GPT-4 in 43% of cases; this statistic is as high as 58% when compared to Bard and 65% versus DaVinci003, which was trained with human feedback. Taken together, these results strongly suggest that almost all knowledge in large language models is learned during pretraining, and only limited instruction tuning data is necessary to teach models to produce high quality output. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.11206v1-abstract-full').style.display = 'none'; document.getElementById('2305.11206v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 18 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2211.02069">arXiv:2211.02069</a> <span> [<a href="https://arxiv.org/pdf/2211.02069">pdf</a>, <a href="https://arxiv.org/format/2211.02069">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Artificial Intelligence">cs.AI</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> </div> </div> <p class="title is-5 mathjax"> LMentry: A Language Model Benchmark of Elementary Language Tasks </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Avia Efrat</a>, <a href="/search/cs?searchtype=author&query=Honovich%2C+O">Or Honovich</a>, <a href="/search/cs?searchtype=author&query=Levy%2C+O">Omer Levy</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2211.02069v2-abstract-short" style="display: inline;"> As the performance of large language models rapidly improves, benchmarks are getting larger and more complex as well. We present LMentry, a benchmark that avoids this "arms race" by focusing on a compact set of tasks that are trivial to humans, e.g. writing a sentence containing a specific word, identifying which words in a list belong to a specific category, or choosing which of two words is long… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2211.02069v2-abstract-full').style.display = 'inline'; document.getElementById('2211.02069v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2211.02069v2-abstract-full" style="display: none;"> As the performance of large language models rapidly improves, benchmarks are getting larger and more complex as well. We present LMentry, a benchmark that avoids this "arms race" by focusing on a compact set of tasks that are trivial to humans, e.g. writing a sentence containing a specific word, identifying which words in a list belong to a specific category, or choosing which of two words is longer. LMentry is specifically designed to provide quick and interpretable insights into the capabilities and robustness of large language models. Our experiments reveal a wide variety of failure cases that, while immediately obvious to humans, pose a considerable challenge for large language models, including OpenAI's latest 175B-parameter instruction-tuned model, TextDavinci002. LMentry complements contemporary evaluation approaches of large language models, providing a quick, automatic, and easy-to-run "unit test", without resorting to large benchmark suites of complex tasks. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2211.02069v2-abstract-full').style.display = 'none'; document.getElementById('2211.02069v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 19 December, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 3 November, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2022. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">minor results updates</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2206.04615">arXiv:2206.04615</a> <span> [<a href="https://arxiv.org/pdf/2206.04615">pdf</a>, <a href="https://arxiv.org/format/2206.04615">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Artificial Intelligence">cs.AI</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computers and Society">cs.CY</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Srivastava%2C+A">Aarohi Srivastava</a>, <a href="/search/cs?searchtype=author&query=Rastogi%2C+A">Abhinav Rastogi</a>, <a href="/search/cs?searchtype=author&query=Rao%2C+A">Abhishek Rao</a>, <a href="/search/cs?searchtype=author&query=Shoeb%2C+A+A+M">Abu Awal Md Shoeb</a>, <a href="/search/cs?searchtype=author&query=Abid%2C+A">Abubakar Abid</a>, <a href="/search/cs?searchtype=author&query=Fisch%2C+A">Adam Fisch</a>, <a href="/search/cs?searchtype=author&query=Brown%2C+A+R">Adam R. Brown</a>, <a href="/search/cs?searchtype=author&query=Santoro%2C+A">Adam Santoro</a>, <a href="/search/cs?searchtype=author&query=Gupta%2C+A">Aditya Gupta</a>, <a href="/search/cs?searchtype=author&query=Garriga-Alonso%2C+A">Adri脿 Garriga-Alonso</a>, <a href="/search/cs?searchtype=author&query=Kluska%2C+A">Agnieszka Kluska</a>, <a href="/search/cs?searchtype=author&query=Lewkowycz%2C+A">Aitor Lewkowycz</a>, <a href="/search/cs?searchtype=author&query=Agarwal%2C+A">Akshat Agarwal</a>, <a href="/search/cs?searchtype=author&query=Power%2C+A">Alethea Power</a>, <a href="/search/cs?searchtype=author&query=Ray%2C+A">Alex Ray</a>, <a href="/search/cs?searchtype=author&query=Warstadt%2C+A">Alex Warstadt</a>, <a href="/search/cs?searchtype=author&query=Kocurek%2C+A+W">Alexander W. Kocurek</a>, <a href="/search/cs?searchtype=author&query=Safaya%2C+A">Ali Safaya</a>, <a href="/search/cs?searchtype=author&query=Tazarv%2C+A">Ali Tazarv</a>, <a href="/search/cs?searchtype=author&query=Xiang%2C+A">Alice Xiang</a>, <a href="/search/cs?searchtype=author&query=Parrish%2C+A">Alicia Parrish</a>, <a href="/search/cs?searchtype=author&query=Nie%2C+A">Allen Nie</a>, <a href="/search/cs?searchtype=author&query=Hussain%2C+A">Aman Hussain</a>, <a href="/search/cs?searchtype=author&query=Askell%2C+A">Amanda Askell</a>, <a href="/search/cs?searchtype=author&query=Dsouza%2C+A">Amanda Dsouza</a> , et al. (426 additional authors not shown) </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2206.04615v3-abstract-short" style="display: inline;"> Language models demonstrate both quantitative improvement and new qualitative capabilities with increasing scale. Despite their potentially transformative impact, these new capabilities are as yet poorly characterized. In order to inform future research, prepare for disruptive new model capabilities, and ameliorate socially harmful effects, it is vital that we understand the present and near-futur… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2206.04615v3-abstract-full').style.display = 'inline'; document.getElementById('2206.04615v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2206.04615v3-abstract-full" style="display: none;"> Language models demonstrate both quantitative improvement and new qualitative capabilities with increasing scale. Despite their potentially transformative impact, these new capabilities are as yet poorly characterized. In order to inform future research, prepare for disruptive new model capabilities, and ameliorate socially harmful effects, it is vital that we understand the present and near-future capabilities and limitations of language models. To address this challenge, we introduce the Beyond the Imitation Game benchmark (BIG-bench). BIG-bench currently consists of 204 tasks, contributed by 450 authors across 132 institutions. Task topics are diverse, drawing problems from linguistics, childhood development, math, common-sense reasoning, biology, physics, social bias, software development, and beyond. BIG-bench focuses on tasks that are believed to be beyond the capabilities of current language models. We evaluate the behavior of OpenAI's GPT models, Google-internal dense transformer architectures, and Switch-style sparse transformers on BIG-bench, across model sizes spanning millions to hundreds of billions of parameters. In addition, a team of human expert raters performed all tasks in order to provide a strong baseline. Findings include: model performance and calibration both improve with scale, but are poor in absolute terms (and when compared with rater performance); performance is remarkably similar across model classes, though with benefits from sparsity; tasks that improve gradually and predictably commonly involve a large knowledge or memorization component, whereas tasks that exhibit "breakthrough" behavior at a critical scale often involve multiple steps or components, or brittle metrics; social bias typically increases with scale in settings with ambiguous context, but this can be improved with prompting. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2206.04615v3-abstract-full').style.display = 'none'; document.getElementById('2206.04615v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 12 June, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 9 June, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2022. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">27 pages, 17 figures + references and appendices, repo: https://github.com/google/BIG-bench</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Transactions on Machine Learning Research, May/2022, https://openreview.net/forum?id=uyTL5Bvosj </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2201.03533">arXiv:2201.03533</a> <span> [<a href="https://arxiv.org/pdf/2201.03533">pdf</a>, <a href="https://arxiv.org/format/2201.03533">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Artificial Intelligence">cs.AI</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> SCROLLS: Standardized CompaRison Over Long Language Sequences </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Shaham%2C+U">Uri Shaham</a>, <a href="/search/cs?searchtype=author&query=Segal%2C+E">Elad Segal</a>, <a href="/search/cs?searchtype=author&query=Ivgi%2C+M">Maor Ivgi</a>, <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Avia Efrat</a>, <a href="/search/cs?searchtype=author&query=Yoran%2C+O">Ori Yoran</a>, <a href="/search/cs?searchtype=author&query=Haviv%2C+A">Adi Haviv</a>, <a href="/search/cs?searchtype=author&query=Gupta%2C+A">Ankit Gupta</a>, <a href="/search/cs?searchtype=author&query=Xiong%2C+W">Wenhan Xiong</a>, <a href="/search/cs?searchtype=author&query=Geva%2C+M">Mor Geva</a>, <a href="/search/cs?searchtype=author&query=Berant%2C+J">Jonathan Berant</a>, <a href="/search/cs?searchtype=author&query=Levy%2C+O">Omer Levy</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2201.03533v2-abstract-short" style="display: inline;"> NLP benchmarks have largely focused on short texts, such as sentences and paragraphs, even though long texts comprise a considerable amount of natural language in the wild. We introduce SCROLLS, a suite of tasks that require reasoning over long texts. We examine existing long-text datasets, and handpick ones where the text is naturally long, while prioritizing tasks that involve synthesizing infor… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2201.03533v2-abstract-full').style.display = 'inline'; document.getElementById('2201.03533v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2201.03533v2-abstract-full" style="display: none;"> NLP benchmarks have largely focused on short texts, such as sentences and paragraphs, even though long texts comprise a considerable amount of natural language in the wild. We introduce SCROLLS, a suite of tasks that require reasoning over long texts. We examine existing long-text datasets, and handpick ones where the text is naturally long, while prioritizing tasks that involve synthesizing information across the input. SCROLLS contains summarization, question answering, and natural language inference tasks, covering multiple domains, including literature, science, business, and entertainment. Initial baselines, including Longformer Encoder-Decoder, indicate that there is ample room for improvement on SCROLLS. We make all datasets available in a unified text-to-text format and host a live leaderboard to facilitate research on model architecture and pretraining methods. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2201.03533v2-abstract-full').style.display = 'none'; document.getElementById('2201.03533v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 11 October, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 10 January, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2022. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">EMNLP 2022</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2109.04517">arXiv:2109.04517</a> <span> [<a href="https://arxiv.org/pdf/2109.04517">pdf</a>, <a href="https://arxiv.org/format/2109.04517">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Social and Information Networks">cs.SI</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Physics and Society">physics.soc-ph</span> </div> </div> <p class="title is-5 mathjax"> Prediction and Prevention of Pandemics via Graphical Model Inference and Convex Programming </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Krechetov%2C+M">Mikhail Krechetov</a>, <a href="/search/cs?searchtype=author&query=Sikaroudi%2C+A+M+E">Amir Mohammad Esmaieeli Sikaroudi</a>, <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Alon Efrat</a>, <a href="/search/cs?searchtype=author&query=Polishchuk%2C+V">Valentin Polishchuk</a>, <a href="/search/cs?searchtype=author&query=Chertkov%2C+M">Michael Chertkov</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2109.04517v2-abstract-short" style="display: inline;"> Hard-to-predict bursts of COVID-19 pandemic revealed significance of statistical modeling which would resolve spatio-temporal correlations over geographical areas, for example spread of the infection over a city with census tract granularity. In this manuscript, we provide algorithmic answers to the following two inter-related public health challenges. (1) Inference Challenge: assuming that there… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2109.04517v2-abstract-full').style.display = 'inline'; document.getElementById('2109.04517v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2109.04517v2-abstract-full" style="display: none;"> Hard-to-predict bursts of COVID-19 pandemic revealed significance of statistical modeling which would resolve spatio-temporal correlations over geographical areas, for example spread of the infection over a city with census tract granularity. In this manuscript, we provide algorithmic answers to the following two inter-related public health challenges. (1) Inference Challenge: assuming that there are $N$ census blocks (nodes) in the city, and given an initial infection at any set of nodes, what is the probability for a subset of census blocks to become infected by the time the spread of the infection burst is stabilized? (2) Prevention Challenge: What is the minimal control action one can take to minimize the infected part of the stabilized state footprint? To answer the challenges, we build a Graphical Model of pandemic of the attractive Ising (pair-wise, binary) type, where each node represents a census track and each edge factor represents the strength of the pairwise interaction between a pair of nodes. We show that almost all attractive Ising Models on dense graphs result in either of the two modes for the most probable state: either all nodes which were not infected initially became infected, or all the initially uninfected nodes remain uninfected. This bi-modal solution of the Inference Challenge allows us to re-state the Prevention Challenge as the following tractable convex programming: for the bare Ising Model with pair-wise and bias factors representing the system without prevention measures, such that the MAP state is fully infected for at least one of the initial infection patterns, find the closest, in $l_1$ norm, set of factors resulting in all the MAP states of the Ising model, with the optimal prevention measures applied, to become safe. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2109.04517v2-abstract-full').style.display = 'none'; document.getElementById('2109.04517v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 26 April, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 9 September, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2021. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2108.05857">arXiv:2108.05857</a> <span> [<a href="https://arxiv.org/pdf/2108.05857">pdf</a>, <a href="https://arxiv.org/format/2108.05857">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> </div> </div> <p class="title is-5 mathjax"> How Optimal is Greedy Decoding for Extractive Question Answering? </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Castel%2C+O">Or Castel</a>, <a href="/search/cs?searchtype=author&query=Ram%2C+O">Ori Ram</a>, <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Avia Efrat</a>, <a href="/search/cs?searchtype=author&query=Levy%2C+O">Omer Levy</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2108.05857v2-abstract-short" style="display: inline;"> Fine-tuned language models use greedy decoding to answer reading comprehension questions with relative success. However, this approach does not ensure that the answer is a span in the given passage, nor does it guarantee that it is the most probable one. Does greedy decoding actually perform worse than an algorithm that does adhere to these properties? To study the performance and optimality of gr… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2108.05857v2-abstract-full').style.display = 'inline'; document.getElementById('2108.05857v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2108.05857v2-abstract-full" style="display: none;"> Fine-tuned language models use greedy decoding to answer reading comprehension questions with relative success. However, this approach does not ensure that the answer is a span in the given passage, nor does it guarantee that it is the most probable one. Does greedy decoding actually perform worse than an algorithm that does adhere to these properties? To study the performance and optimality of greedy decoding, we present exact-extract, a decoding algorithm that efficiently finds the most probable answer span in the context. We compare the performance of T5 with both decoding algorithms on zero-shot and few-shot extractive question answering. When no training examples are available, exact-extract significantly outperforms greedy decoding. However, greedy decoding quickly converges towards the performance of exact-extract with the introduction of a few training examples, becoming more extractive and increasingly likelier to generate the most probable span as the training set grows. We also show that self-supervised training can bias the model towards extractive behavior, increasing performance in the zero-shot setting without resorting to annotated examples. Overall, our results suggest that pretrained language models are so good at adapting to extractive question answering, that it is often enough to fine-tune on a small training set for the greedy algorithm to emulate the optimal decoding strategy. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2108.05857v2-abstract-full').style.display = 'none'; document.getElementById('2108.05857v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 8 November, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 12 August, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 2021. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">AKBC 2022 12 pages, 3 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2103.01242">arXiv:2103.01242</a> <span> [<a href="https://arxiv.org/pdf/2103.01242">pdf</a>, <a href="https://arxiv.org/format/2103.01242">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Artificial Intelligence">cs.AI</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">stat.ML</span> </div> </div> <p class="title is-5 mathjax"> Cryptonite: A Cryptic Crossword Benchmark for Extreme Ambiguity in Language </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Avia Efrat</a>, <a href="/search/cs?searchtype=author&query=Shaham%2C+U">Uri Shaham</a>, <a href="/search/cs?searchtype=author&query=Kilman%2C+D">Dan Kilman</a>, <a href="/search/cs?searchtype=author&query=Levy%2C+O">Omer Levy</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2103.01242v2-abstract-short" style="display: inline;"> Current NLP datasets targeting ambiguity can be solved by a native speaker with relative ease. We present Cryptonite, a large-scale dataset based on cryptic crosswords, which is both linguistically complex and naturally sourced. Each example in Cryptonite is a cryptic clue, a short phrase or sentence with a misleading surface reading, whose solving requires disambiguating semantic, syntactic, and… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2103.01242v2-abstract-full').style.display = 'inline'; document.getElementById('2103.01242v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2103.01242v2-abstract-full" style="display: none;"> Current NLP datasets targeting ambiguity can be solved by a native speaker with relative ease. We present Cryptonite, a large-scale dataset based on cryptic crosswords, which is both linguistically complex and naturally sourced. Each example in Cryptonite is a cryptic clue, a short phrase or sentence with a misleading surface reading, whose solving requires disambiguating semantic, syntactic, and phonetic wordplays, as well as world knowledge. Cryptic clues pose a challenge even for experienced solvers, though top-tier experts can solve them with almost 100% accuracy. Cryptonite is a challenging task for current models; fine-tuning T5-Large on 470k cryptic clues achieves only 7.6% accuracy, on par with the accuracy of a rule-based clue solver (8.6%). <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2103.01242v2-abstract-full').style.display = 'none'; document.getElementById('2103.01242v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 1 November, 2021; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 1 March, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2021. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">EMNLP 2021</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2010.11982">arXiv:2010.11982</a> <span> [<a href="https://arxiv.org/pdf/2010.11982">pdf</a>, <a href="https://arxiv.org/format/2010.11982">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Artificial Intelligence">cs.AI</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> </div> </div> <p class="title is-5 mathjax"> The Turking Test: Can Language Models Understand Instructions? </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Avia Efrat</a>, <a href="/search/cs?searchtype=author&query=Levy%2C+O">Omer Levy</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2010.11982v1-abstract-short" style="display: inline;"> Supervised machine learning provides the learner with a set of input-output examples of the target task. Humans, however, can also learn to perform new tasks from instructions in natural language. Can machines learn to understand instructions as well? We present the Turking Test, which examines a model's ability to follow natural language instructions of varying complexity. These range from simple… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2010.11982v1-abstract-full').style.display = 'inline'; document.getElementById('2010.11982v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2010.11982v1-abstract-full" style="display: none;"> Supervised machine learning provides the learner with a set of input-output examples of the target task. Humans, however, can also learn to perform new tasks from instructions in natural language. Can machines learn to understand instructions as well? We present the Turking Test, which examines a model's ability to follow natural language instructions of varying complexity. These range from simple tasks, like retrieving the nth word of a sentence, to ones that require creativity, such as generating examples for SNLI and SQuAD in place of human intelligence workers ("turkers"). Despite our lenient evaluation methodology, we observe that a large pretrained language model performs poorly across all tasks. Analyzing the model's error patterns reveals that the model tends to ignore explicit instructions and often generates outputs that cannot be construed as an attempt to solve the task. While it is not yet clear whether instruction understanding can be captured by traditional language models, the sheer expressivity of instruction understanding makes it an appealing alternative to the rising few-shot inference paradigm. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2010.11982v1-abstract-full').style.display = 'none'; document.getElementById('2010.11982v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 22 October, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2020. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2008.10192">arXiv:2008.10192</a> <span> [<a href="https://arxiv.org/pdf/2008.10192">pdf</a>, <a href="https://arxiv.org/format/2008.10192">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Geometry">cs.CG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> </div> </div> <p class="title is-5 mathjax"> Polygons with Prescribed Angles in 2D and 3D </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Alon Efrat</a>, <a href="/search/cs?searchtype=author&query=Fulek%2C+R">Radoslav Fulek</a>, <a href="/search/cs?searchtype=author&query=Kobourov%2C+S">Stephen Kobourov</a>, <a href="/search/cs?searchtype=author&query=T%C3%B3th%2C+C+D">Csaba D. T贸th</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2008.10192v2-abstract-short" style="display: inline;"> We consider the construction of a polygon $P$ with $n$ vertices whose turning angles at the vertices are given by a sequence $A=(伪_0,\ldots, 伪_{n-1})$, $伪_i\in (-蟺,蟺)$, for $i\in\{0,\ldots, n-1\}$. The problem of realizing $A$ by a polygon can be seen as that of constructing a straight-line drawing of a graph with prescribed angles at vertices, and hence, it is a special case of the well studied p… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2008.10192v2-abstract-full').style.display = 'inline'; document.getElementById('2008.10192v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2008.10192v2-abstract-full" style="display: none;"> We consider the construction of a polygon $P$ with $n$ vertices whose turning angles at the vertices are given by a sequence $A=(伪_0,\ldots, 伪_{n-1})$, $伪_i\in (-蟺,蟺)$, for $i\in\{0,\ldots, n-1\}$. The problem of realizing $A$ by a polygon can be seen as that of constructing a straight-line drawing of a graph with prescribed angles at vertices, and hence, it is a special case of the well studied problem of constructing an \emph{angle graph}. In 2D, we characterize sequences $A$ for which every generic polygon $P\subset \mathbb{R}^2$ realizing $A$ has at least $c$ crossings, for every $c\in \mathbb{N}$, and describe an efficient algorithm that constructs, for a given sequence $A$, a generic polygon $P\subset \mathbb{R}^2$ that realizes $A$ with the minimum number of crossings. In 3D, we describe an efficient algorithm that tests whether a given sequence $A$ can be realized by a (not necessarily generic) polygon $P\subset \mathbb{R}^3$, and for every realizable sequence the algorithm finds a realization. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2008.10192v2-abstract-full').style.display = 'none'; document.getElementById('2008.10192v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 1 November, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 24 August, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 2020. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">15 pages, 9 figures, a new section about self-intersecting realizations in 3D</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2001.08773">arXiv:2001.08773</a> <span> [<a href="https://arxiv.org/pdf/2001.08773">pdf</a>, <a href="https://arxiv.org/format/2001.08773">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Cryptography and Security">cs.CR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Geometry">cs.CG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Databases">cs.DB</span> </div> </div> <p class="title is-5 mathjax"> Data Inference from Encrypted Databases: A Multi-dimensional Order-Preserving Matching Approach </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Pan%2C+Y">Yanjun Pan</a>, <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Alon Efrat</a>, <a href="/search/cs?searchtype=author&query=Li%2C+M">Ming Li</a>, <a href="/search/cs?searchtype=author&query=Wang%2C+B">Boyang Wang</a>, <a href="/search/cs?searchtype=author&query=Quan%2C+H">Hanyu Quan</a>, <a href="/search/cs?searchtype=author&query=Mitchell%2C+J">Joseph Mitchell</a>, <a href="/search/cs?searchtype=author&query=Gao%2C+J">Jie Gao</a>, <a href="/search/cs?searchtype=author&query=Arkin%2C+E">Esther Arkin</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2001.08773v1-abstract-short" style="display: inline;"> Due to increasing concerns of data privacy, databases are being encrypted before they are stored on an untrusted server. To enable search operations on the encrypted data, searchable encryption techniques have been proposed. Representative schemes use order-preserving encryption (OPE) for supporting efficient Boolean queries on encrypted databases. Yet, recent works showed the possibility of infer… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2001.08773v1-abstract-full').style.display = 'inline'; document.getElementById('2001.08773v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2001.08773v1-abstract-full" style="display: none;"> Due to increasing concerns of data privacy, databases are being encrypted before they are stored on an untrusted server. To enable search operations on the encrypted data, searchable encryption techniques have been proposed. Representative schemes use order-preserving encryption (OPE) for supporting efficient Boolean queries on encrypted databases. Yet, recent works showed the possibility of inferring plaintext data from OPE-encrypted databases, merely using the order-preserving constraints, or combined with an auxiliary plaintext dataset with similar frequency distribution. So far, the effectiveness of such attacks is limited to single-dimensional dense data (most values from the domain are encrypted), but it remains challenging to achieve it on high-dimensional datasets (e.g., spatial data) which are often sparse in nature. In this paper, for the first time, we study data inference attacks on multi-dimensional encrypted databases (with 2-D as a special case). We formulate it as a 2-D order-preserving matching problem and explore both unweighted and weighted cases, where the former maximizes the number of points matched using only order information and the latter further considers points with similar frequencies. We prove that the problem is NP-hard, and then propose a greedy algorithm, along with a polynomial-time algorithm with approximation guarantees. Experimental results on synthetic and real-world datasets show that the data recovery rate is significantly enhanced compared with the previous 1-D matching algorithm. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2001.08773v1-abstract-full').style.display = 'none'; document.getElementById('2001.08773v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 23 January, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2020. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">11 pages, 4 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1909.13375">arXiv:1909.13375</a> <span> [<a href="https://arxiv.org/pdf/1909.13375">pdf</a>, <a href="https://arxiv.org/format/1909.13375">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> </div> </div> <p class="title is-5 mathjax"> A Simple and Effective Model for Answering Multi-span Questions </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Segal%2C+E">Elad Segal</a>, <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Avia Efrat</a>, <a href="/search/cs?searchtype=author&query=Shoham%2C+M">Mor Shoham</a>, <a href="/search/cs?searchtype=author&query=Globerson%2C+A">Amir Globerson</a>, <a href="/search/cs?searchtype=author&query=Berant%2C+J">Jonathan Berant</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1909.13375v4-abstract-short" style="display: inline;"> Models for reading comprehension (RC) commonly restrict their output space to the set of all single contiguous spans from the input, in order to alleviate the learning problem and avoid the need for a model that generates text explicitly. However, forcing an answer to be a single span can be restrictive, and some recent datasets also include multi-span questions, i.e., questions whose answer is a… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1909.13375v4-abstract-full').style.display = 'inline'; document.getElementById('1909.13375v4-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1909.13375v4-abstract-full" style="display: none;"> Models for reading comprehension (RC) commonly restrict their output space to the set of all single contiguous spans from the input, in order to alleviate the learning problem and avoid the need for a model that generates text explicitly. However, forcing an answer to be a single span can be restrictive, and some recent datasets also include multi-span questions, i.e., questions whose answer is a set of non-contiguous spans in the text. Naturally, models that return single spans cannot answer these questions. In this work, we propose a simple architecture for answering multi-span questions by casting the task as a sequence tagging problem, namely, predicting for each input token whether it should be part of the output or not. Our model substantially improves performance on span extraction questions from DROP and Quoref by 9.9 and 5.5 EM points respectively. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1909.13375v4-abstract-full').style.display = 'none'; document.getElementById('1909.13375v4-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 5 October, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 29 September, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2019. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">EMNLP 2020</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1902.06875">arXiv:1902.06875</a> <span> [<a href="https://arxiv.org/pdf/1902.06875">pdf</a>, <a href="https://arxiv.org/format/1902.06875">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Geometry">cs.CG</span> </div> </div> <p class="title is-5 mathjax"> Euclidean TSP, Motorcycle Graphs, and Other New Applications of Nearest-Neighbor Chains </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Mamano%2C+N">Nil Mamano</a>, <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Alon Efrat</a>, <a href="/search/cs?searchtype=author&query=Eppstein%2C+D">David Eppstein</a>, <a href="/search/cs?searchtype=author&query=Frishberg%2C+D">Daniel Frishberg</a>, <a href="/search/cs?searchtype=author&query=Goodrich%2C+M">Michael Goodrich</a>, <a href="/search/cs?searchtype=author&query=Kobourov%2C+S">Stephen Kobourov</a>, <a href="/search/cs?searchtype=author&query=Matias%2C+P">Pedro Matias</a>, <a href="/search/cs?searchtype=author&query=Polishchuk%2C+V">Valentin Polishchuk</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1902.06875v3-abstract-short" style="display: inline;"> We show new applications of the nearest-neighbor chain algorithm, a technique that originated in agglomerative hierarchical clustering. We apply it to a diverse class of geometric problems: we construct the greedy multi-fragment tour for Euclidean TSP in $O(n\log n)$ time in any fixed dimension and for Steiner TSP in planar graphs in $O(n\sqrt{n}\log n)$ time; we compute motorcycle graphs (which a… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1902.06875v3-abstract-full').style.display = 'inline'; document.getElementById('1902.06875v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1902.06875v3-abstract-full" style="display: none;"> We show new applications of the nearest-neighbor chain algorithm, a technique that originated in agglomerative hierarchical clustering. We apply it to a diverse class of geometric problems: we construct the greedy multi-fragment tour for Euclidean TSP in $O(n\log n)$ time in any fixed dimension and for Steiner TSP in planar graphs in $O(n\sqrt{n}\log n)$ time; we compute motorcycle graphs (which are a central part in straight skeleton algorithms) in $O(n^{4/3+\varepsilon})$ time for any $\varepsilon>0$; we introduce a narcissistic variant of the $k$-attribute stable matching model, and solve it in $O(n^{2-4/(k(1+\varepsilon)+2)})$ time; we give a linear-time $2$-approximation for a 1D geometric set cover problem with applications to radio station placement. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1902.06875v3-abstract-full').style.display = 'none'; document.getElementById('1902.06875v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 2 December, 2019; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 18 February, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2019. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">35 pages, 10 figures; v2: minor improvements, added Figure 1, and author order as in paper. v3: added funding acknowledgement</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> I.3.5 <span class="has-text-black-bis has-text-weight-semibold">ACM Class:</span> I.3.5 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1811.11700">arXiv:1811.11700</a> <span> [<a href="https://arxiv.org/pdf/1811.11700">pdf</a>, <a href="https://arxiv.org/format/1811.11700">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Approximation algorithms for the vertex-weighted grade-of-service Steiner tree problem </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Sahneh%2C+F+D">Faryad Darabi Sahneh</a>, <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Alon Efrat</a>, <a href="/search/cs?searchtype=author&query=Kobourov%2C+S">Stephen Kobourov</a>, <a href="/search/cs?searchtype=author&query=Krieger%2C+S">Spencer Krieger</a>, <a href="/search/cs?searchtype=author&query=Spence%2C+R">Richard Spence</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1811.11700v2-abstract-short" style="display: inline;"> Given a graph $G = (V,E)$ and a subset $T \subseteq V$ of terminals, a \emph{Steiner tree} of $G$ is a tree that spans $T$. In the vertex-weighted Steiner tree (VST) problem, each vertex is assigned a non-negative weight, and the goal is to compute a minimum weight Steiner tree of $G$. We study a natural generalization of the VST problem motivated by multi-level graph construction, the \emph{ver… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1811.11700v2-abstract-full').style.display = 'inline'; document.getElementById('1811.11700v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1811.11700v2-abstract-full" style="display: none;"> Given a graph $G = (V,E)$ and a subset $T \subseteq V$ of terminals, a \emph{Steiner tree} of $G$ is a tree that spans $T$. In the vertex-weighted Steiner tree (VST) problem, each vertex is assigned a non-negative weight, and the goal is to compute a minimum weight Steiner tree of $G$. We study a natural generalization of the VST problem motivated by multi-level graph construction, the \emph{vertex-weighted grade-of-service Steiner tree problem} (V-GSST), which can be stated as follows: given a graph $G$ and terminals $T$, where each terminal $v \in T$ requires a facility of a minimum grade of service $R(v)\in \{1,2,\ldots\ell\}$, compute a Steiner tree $G'$ by installing facilities on a subset of vertices, such that any two vertices requiring a certain grade of service are connected by a path in $G'$ with the minimum grade of service or better. Facilities of higher grade are more costly than facilities of lower grade. Multi-level variants such as this one can be useful in network design problems where vertices may require facilities of varying priority. While similar problems have been studied in the edge-weighted case, they have not been studied as well in the more general vertex-weighted case. We first describe a simple heuristic for the V-GSST problem whose approximation ratio depends on $\ell$, the number of grades of service. We then generalize the greedy algorithm of [Klein \& Ravi, 1995] to show that the V-GSST problem admits a $(2 \ln |T|)$-approximation, where $T$ is the set of terminals requiring some facility. This result is surprising, as it shows that the (seemingly harder) multi-grade problem can be approximated as well as the VST problem, and that the approximation ratio does not depend on the number of grades of service. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1811.11700v2-abstract-full').style.display = 'none'; document.getElementById('1811.11700v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 3 May, 2019; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 28 November, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2018. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1804.02627">arXiv:1804.02627</a> <span> [<a href="https://arxiv.org/pdf/1804.02627">pdf</a>, <a href="https://arxiv.org/format/1804.02627">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1145/3368621">10.1145/3368621 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Multi-Level Steiner Trees </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Ahmed%2C+R">Reyan Ahmed</a>, <a href="/search/cs?searchtype=author&query=Angelini%2C+P">Patrizio Angelini</a>, <a href="/search/cs?searchtype=author&query=Sahneh%2C+F+D">Faryad Darabi Sahneh</a>, <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Alon Efrat</a>, <a href="/search/cs?searchtype=author&query=Glickenstein%2C+D">David Glickenstein</a>, <a href="/search/cs?searchtype=author&query=Gronemann%2C+M">Martin Gronemann</a>, <a href="/search/cs?searchtype=author&query=Heinsohn%2C+N">Niklas Heinsohn</a>, <a href="/search/cs?searchtype=author&query=Kobourov%2C+S+G">Stephen G. Kobourov</a>, <a href="/search/cs?searchtype=author&query=Spence%2C+R">Richard Spence</a>, <a href="/search/cs?searchtype=author&query=Watkins%2C+J">Joseph Watkins</a>, <a href="/search/cs?searchtype=author&query=Wolff%2C+A">Alexander Wolff</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1804.02627v2-abstract-short" style="display: inline;"> In the classical Steiner tree problem, given an undirected, connected graph $G=(V,E)$ with non-negative edge costs and a set of \emph{terminals} $T\subseteq V$, the objective is to find a minimum-cost tree $E' \subseteq E$ that spans the terminals. The problem is APX-hard; the best known approximation algorithm has a ratio of $蟻= \ln(4)+\varepsilon < 1.39$. In this paper, we study a natural genera… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1804.02627v2-abstract-full').style.display = 'inline'; document.getElementById('1804.02627v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1804.02627v2-abstract-full" style="display: none;"> In the classical Steiner tree problem, given an undirected, connected graph $G=(V,E)$ with non-negative edge costs and a set of \emph{terminals} $T\subseteq V$, the objective is to find a minimum-cost tree $E' \subseteq E$ that spans the terminals. The problem is APX-hard; the best known approximation algorithm has a ratio of $蟻= \ln(4)+\varepsilon < 1.39$. In this paper, we study a natural generalization, the \emph{multi-level Steiner tree} (MLST) problem: given a nested sequence of terminals $T_{\ell} \subset \dots \subset T_1 \subseteq V$, compute nested trees $E_{\ell}\subseteq \dots \subseteq E_1\subseteq E$ that span the corresponding terminal sets with minimum total cost. The MLST problem and variants thereof have been studied under various names including Multi-level Network Design, Quality-of-Service Multicast tree, Grade-of-Service Steiner tree, and Multi-Tier tree. Several approximation results are known. We first present two simple $O(\ell)$-approximation heuristics. Based on these, we introduce a rudimentary composite algorithm that generalizes the above heuristics, and determine its approximation ratio by solving a linear program. We then present a method that guarantees the same approximation ratio using at most $2\ell$ Steiner tree computations. We compare these heuristics experimentally on various instances of up to 500 vertices using three different network generation models. We also present various integer linear programming (ILP) formulations for the MLST problem, and compare their running times on these instances. To our knowledge, the composite algorithm achieves the best approximation ratio for up to $\ell=100$ levels, which is sufficient for most applications such as network visualization or designing multi-level infrastructure. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1804.02627v2-abstract-full').style.display = 'none'; document.getElementById('1804.02627v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 26 November, 2018; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 8 April, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2018. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">This paper has been accepted in 17th International Symposium on Experimental Algorithms (SEA 2018)</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> ACM Journal of Experimental Algorithmics 24(1):2.5:1-2.5:22 (2019) </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1703.01544">arXiv:1703.01544</a> <span> [<a href="https://arxiv.org/pdf/1703.01544">pdf</a>, <a href="https://arxiv.org/format/1703.01544">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Geometry">cs.CG</span> </div> </div> <p class="title is-5 mathjax"> L-Graphs and Monotone L-Graphs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Ahmed%2C+A+R">Abu Reyan Ahmed</a>, <a href="/search/cs?searchtype=author&query=De+Luca%2C+F">Felice De Luca</a>, <a href="/search/cs?searchtype=author&query=Devkota%2C+S">Sabin Devkota</a>, <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Alon Efrat</a>, <a href="/search/cs?searchtype=author&query=Hossain%2C+M+I">Md Iqbal Hossain</a>, <a href="/search/cs?searchtype=author&query=Kobourov%2C+S">Stephen Kobourov</a>, <a href="/search/cs?searchtype=author&query=Li%2C+J">Jixian Li</a>, <a href="/search/cs?searchtype=author&query=Salma%2C+S+A">Sammi Abida Salma</a>, <a href="/search/cs?searchtype=author&query=Welch%2C+E">Eric Welch</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1703.01544v1-abstract-short" style="display: inline;"> In an $\mathsf{L}$-embedding of a graph, each vertex is represented by an $\mathsf{L}$-segment, and two segments intersect each other if and only if the corresponding vertices are adjacent in the graph. If the corner of each $\mathsf{L}$-segment in an $\mathsf{L}$-embedding lies on a straight line, we call it a monotone $\mathsf{L}$-embedding. In this paper we give a full characterization of monot… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1703.01544v1-abstract-full').style.display = 'inline'; document.getElementById('1703.01544v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1703.01544v1-abstract-full" style="display: none;"> In an $\mathsf{L}$-embedding of a graph, each vertex is represented by an $\mathsf{L}$-segment, and two segments intersect each other if and only if the corresponding vertices are adjacent in the graph. If the corner of each $\mathsf{L}$-segment in an $\mathsf{L}$-embedding lies on a straight line, we call it a monotone $\mathsf{L}$-embedding. In this paper we give a full characterization of monotone $\mathsf{L}$-embeddings by introducing a new class of graphs which we call "non-jumping" graphs. We show that a graph admits a monotone $\mathsf{L}$-embedding if and only if the graph is a non-jumping graph. Further, we show that outerplanar graphs, convex bipartite graphs, interval graphs, 3-leaf power graphs, and complete graphs are subclasses of non-jumping graphs. Finally, we show that distance-hereditary graphs and $k$-leaf power graphs ($k\le 4$) admit $\mathsf{L}$-embeddings. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1703.01544v1-abstract-full').style.display = 'none'; document.getElementById('1703.01544v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 4 March, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2017. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1511.02525">arXiv:1511.02525</a> <span> [<a href="https://arxiv.org/pdf/1511.02525">pdf</a>, <a href="https://arxiv.org/format/1511.02525">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Improved Approximation Algorithms for Relay Placement </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Alon Efrat</a>, <a href="/search/cs?searchtype=author&query=Fekete%2C+S+P">S谩ndor P. Fekete</a>, <a href="/search/cs?searchtype=author&query=Mitchell%2C+J+S+B">Joseph S. B. Mitchell</a>, <a href="/search/cs?searchtype=author&query=Polishchuk%2C+V">Valentin Polishchuk</a>, <a href="/search/cs?searchtype=author&query=Suomela%2C+J">Jukka Suomela</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1511.02525v1-abstract-short" style="display: inline;"> In the relay placement problem the input is a set of sensors and a number $r \ge 1$, the communication range of a relay. In the one-tier version of the problem the objective is to place a minimum number of relays so that between every pair of sensors there is a path through sensors and/or relays such that the consecutive vertices of the path are within distance $r$ if both vertices are relays and… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1511.02525v1-abstract-full').style.display = 'inline'; document.getElementById('1511.02525v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1511.02525v1-abstract-full" style="display: none;"> In the relay placement problem the input is a set of sensors and a number $r \ge 1$, the communication range of a relay. In the one-tier version of the problem the objective is to place a minimum number of relays so that between every pair of sensors there is a path through sensors and/or relays such that the consecutive vertices of the path are within distance $r$ if both vertices are relays and within distance 1 otherwise. The two-tier version adds the restrictions that the path must go through relays, and not through sensors. We present a 3.11-approximation algorithm for the one-tier version and a PTAS for the two-tier version. We also show that the one-tier version admits no PTAS, assuming P $\ne$ NP. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1511.02525v1-abstract-full').style.display = 'none'; document.getElementById('1511.02525v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 8 November, 2015; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2015. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">1+29 pages, 12 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1409.0296">arXiv:1409.0296</a> <span> [<a href="https://arxiv.org/pdf/1409.0296">pdf</a>, <a href="https://arxiv.org/format/1409.0296">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computers and Society">cs.CY</span> </div> </div> <p class="title is-5 mathjax"> A Mobile Food Recommendation System Based on The Traffic Light Diet </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Johnson%2C+T">Thienne Johnson</a>, <a href="/search/cs?searchtype=author&query=Vergara%2C+J">Jorge Vergara</a>, <a href="/search/cs?searchtype=author&query=Doll%2C+C">Chelsea Doll</a>, <a href="/search/cs?searchtype=author&query=Kramer%2C+M">Madison Kramer</a>, <a href="/search/cs?searchtype=author&query=Sundararaman%2C+G">Gayathri Sundararaman</a>, <a href="/search/cs?searchtype=author&query=Rajendran%2C+H">Harsha Rajendran</a>, <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Alon Efrat</a>, <a href="/search/cs?searchtype=author&query=Hingle%2C+M">Melanie Hingle</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1409.0296v1-abstract-short" style="display: inline;"> Innovative, real-time solutions are needed to address the mismatch between the demand for and supply of critical information to inform and motivate diet and health-related behavior change. Research suggests that interventions using mobile health technologies hold great promise for influencing knowledge, attitudes, and behaviors related to energy balance. The objective of this paper is to present i… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1409.0296v1-abstract-full').style.display = 'inline'; document.getElementById('1409.0296v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1409.0296v1-abstract-full" style="display: none;"> Innovative, real-time solutions are needed to address the mismatch between the demand for and supply of critical information to inform and motivate diet and health-related behavior change. Research suggests that interventions using mobile health technologies hold great promise for influencing knowledge, attitudes, and behaviors related to energy balance. The objective of this paper is to present insights related to the development and testing of a mobile food recommendation system targeting fast food restaurants. The system is designed to provide consumers with information about energy density of food options combined with tips for healthier choices when dining out, accessible through a mobile phone. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1409.0296v1-abstract-full').style.display = 'none'; document.getElementById('1409.0296v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 1 September, 2014; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2014. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/0912.4115">arXiv:0912.4115</a> <span> [<a href="https://arxiv.org/pdf/0912.4115">pdf</a>, <a href="https://arxiv.org/format/0912.4115">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Networking and Internet Architecture">cs.NI</span> </div> </div> <p class="title is-5 mathjax"> On Channel-Discontinuity-Constraint Routing in Wireless Networks </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Sankararaman%2C+S">Swaminathan Sankararaman</a>, <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Alon Efrat</a>, <a href="/search/cs?searchtype=author&query=Ramasubramanian%2C+S">Srinivasan Ramasubramanian</a>, <a href="/search/cs?searchtype=author&query=Agarwal%2C+P+K">Pankaj K. Agarwal</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="0912.4115v2-abstract-short" style="display: inline;"> Multi-channel wireless networks are increasingly being employed as infrastructure networks, e.g. in metro areas. Nodes in these networks frequently employ directional antennas to improve spatial throughput. In such networks, given a source and destination, it is of interest to compute an optimal path and channel assignment on every link in the path such that the path bandwidth is the same as tha… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('0912.4115v2-abstract-full').style.display = 'inline'; document.getElementById('0912.4115v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="0912.4115v2-abstract-full" style="display: none;"> Multi-channel wireless networks are increasingly being employed as infrastructure networks, e.g. in metro areas. Nodes in these networks frequently employ directional antennas to improve spatial throughput. In such networks, given a source and destination, it is of interest to compute an optimal path and channel assignment on every link in the path such that the path bandwidth is the same as that of the link bandwidth and such a path satisfies the constraint that no two consecutive links on the path are assigned the same channel, referred to as "Channel Discontinuity Constraint" (CDC). CDC-paths are also quite useful for TDMA system, where preferably every consecutive links along a path are assigned different time slots. This paper contains several contributions. We first present an $O(N^{2})$ distributed algorithm for discovering the shortest CDC-path between given source and destination. This improves the running time of the $O(N^{3})$ centralized algorithm of Ahuja et al. for finding the minimum-weight CDC-path. Our second result is a generalized $t$-spanner for CDC-path; For any $胃>0$ we show how to construct a sub-network containing only $O(\frac{N}胃)$ edges, such that that length of shortest CDC-paths between arbitrary sources and destinations increases by only a factor of at most $(1-2\sin{\tfrac胃{2}})^{-2}$. We propose a novel algorithm to compute the spanner in a distributed manner using only $O(n\log{n})$ messages. An important conclusion of this scheme is in the case of directional antennas are used. In this case, it is enough to consider only the two closest nodes in each cone. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('0912.4115v2-abstract-full').style.display = 'none'; document.getElementById('0912.4115v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 26 February, 2010; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 21 December, 2009; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2009. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/0911.4332">arXiv:0911.4332</a> <span> [<a href="https://arxiv.org/pdf/0911.4332">pdf</a>, <a href="https://arxiv.org/format/0911.4332">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Networking and Internet Architecture">cs.NI</span> </div> </div> <p class="title is-5 mathjax"> Scheduling Sensors for Guaranteed Sparse Coverage </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Sankararaman%2C+S">Swaminathan Sankararaman</a>, <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Alon Efrat</a>, <a href="/search/cs?searchtype=author&query=Ramasubramanian%2C+S">Srinivasan Ramasubramanian</a>, <a href="/search/cs?searchtype=author&query=Taheri%2C+J">Javad Taheri</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="0911.4332v2-abstract-short" style="display: inline;"> Sensor networks are particularly applicable to the tracking of objects in motion. For such applications, it may not necessary that the whole region be covered by sensors as long as the uncovered region is not too large. This notion has been formalized by Balasubramanian et.al. as the problem of $魏$-weak coverage. This model of coverage provides guarantees about the regions in which the objects m… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('0911.4332v2-abstract-full').style.display = 'inline'; document.getElementById('0911.4332v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="0911.4332v2-abstract-full" style="display: none;"> Sensor networks are particularly applicable to the tracking of objects in motion. For such applications, it may not necessary that the whole region be covered by sensors as long as the uncovered region is not too large. This notion has been formalized by Balasubramanian et.al. as the problem of $魏$-weak coverage. This model of coverage provides guarantees about the regions in which the objects may move undetected. In this paper, we analyse the theoretical aspects of the problem and provide guarantees about the lifetime achievable. We introduce a number of practical algorithms and analyse their significance. The main contribution is a novel linear programming based algorithm which provides near-optimal lifetime. Through extensive experimentation, we analyse the performance of these algorithms based on several parameters defined. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('0911.4332v2-abstract-full').style.display = 'none'; document.getElementById('0911.4332v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 26 February, 2010; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 23 November, 2009; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2009. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/cs/0605102">arXiv:cs/0605102</a> <span> [<a href="https://arxiv.org/pdf/cs/0605102">pdf</a>, <a href="https://arxiv.org/ps/cs/0605102">ps</a>, <a href="https://arxiv.org/format/cs/0605102">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Geometry">cs.CG</span> </div> </div> <p class="title is-5 mathjax"> Restricted Strip Covering and the Sensor Cover Problem </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Buchsbaum%2C+A+L">Adam L. Buchsbaum</a>, <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Alon Efrat</a>, <a href="/search/cs?searchtype=author&query=Jain%2C+S">Shaili Jain</a>, <a href="/search/cs?searchtype=author&query=Venkatasubramanian%2C+S">Suresh Venkatasubramanian</a>, <a href="/search/cs?searchtype=author&query=Yi%2C+K">Ke Yi</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="cs/0605102v1-abstract-short" style="display: inline;"> Given a set of objects with durations (jobs) that cover a base region, can we schedule the jobs to maximize the duration the original region remains covered? We call this problem the sensor cover problem. This problem arises in the context of covering a region with sensors. For example, suppose you wish to monitor activity along a fence by sensors placed at various fixed locations. Each sensor h… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('cs/0605102v1-abstract-full').style.display = 'inline'; document.getElementById('cs/0605102v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="cs/0605102v1-abstract-full" style="display: none;"> Given a set of objects with durations (jobs) that cover a base region, can we schedule the jobs to maximize the duration the original region remains covered? We call this problem the sensor cover problem. This problem arises in the context of covering a region with sensors. For example, suppose you wish to monitor activity along a fence by sensors placed at various fixed locations. Each sensor has a range and limited battery life. The problem is to schedule when to turn on the sensors so that the fence is fully monitored for as long as possible. This one dimensional problem involves intervals on the real line. Associating a duration to each yields a set of rectangles in space and time, each specified by a pair of fixed horizontal endpoints and a height. The objective is to assign a position to each rectangle to maximize the height at which the spanning interval is fully covered. We call this one dimensional problem restricted strip covering. If we replace the covering constraint by a packing constraint, the problem is identical to dynamic storage allocation, a scheduling problem that is a restricted case of the strip packing problem. We show that the restricted strip covering problem is NP-hard and present an O(log log n)-approximation algorithm. We present better approximations or exact algorithms for some special cases. For the uniform-duration case of restricted strip covering we give a polynomial-time, exact algorithm but prove that the uniform-duration case for higher-dimensional regions is NP-hard. Finally, we consider regions that are arbitrary sets, and we present an O(log n)-approximation algorithm. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('cs/0605102v1-abstract-full').style.display = 'none'; document.getElementById('cs/0605102v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 23 May, 2006; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2006. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">14 pages, 6 figures</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/cs/0206018">arXiv:cs/0206018</a> <span> [<a href="https://arxiv.org/pdf/cs/0206018">pdf</a>, <a href="https://arxiv.org/ps/cs/0206018">ps</a>, <a href="https://arxiv.org/format/cs/0206018">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Geometry">cs.CG</span> </div> </div> <p class="title is-5 mathjax"> On Simultaneous Graph Embedding </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Duncan%2C+C+A">C. A. Duncan</a>, <a href="/search/cs?searchtype=author&query=Efrat%2C+A">A. Efrat</a>, <a href="/search/cs?searchtype=author&query=Erten%2C+C">C. Erten</a>, <a href="/search/cs?searchtype=author&query=Kobourov%2C+S">S. Kobourov</a>, <a href="/search/cs?searchtype=author&query=Mitchell%2C+J+S+B">J. S. B. Mitchell</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="cs/0206018v3-abstract-short" style="display: inline;"> We consider the problem of simultaneous embedding of planar graphs. There are two variants of this problem, one in which the mapping between the vertices of the two graphs is given and another where the mapping is not given. In particular, we show that without mapping, any number of outerplanar graphs can be embedded simultaneously on an $O(n)\times O(n)$ grid, and an outerplanar and general pla… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('cs/0206018v3-abstract-full').style.display = 'inline'; document.getElementById('cs/0206018v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="cs/0206018v3-abstract-full" style="display: none;"> We consider the problem of simultaneous embedding of planar graphs. There are two variants of this problem, one in which the mapping between the vertices of the two graphs is given and another where the mapping is not given. In particular, we show that without mapping, any number of outerplanar graphs can be embedded simultaneously on an $O(n)\times O(n)$ grid, and an outerplanar and general planar graph can be embedded simultaneously on an $O(n^2)\times O(n^3)$ grid. If the mapping is given, we show how to embed two paths on an $n \times n$ grid, a caterpillar and a path on an $n \times 2n$ grid, or two caterpillar graphs on an $O(n^2)\times O(n^3)$ grid. We also show that 5 paths, or 3 caterpillars, or two general planar graphs cannot be simultaneously embedded given the mapping. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('cs/0206018v3-abstract-full').style.display = 'none'; document.getElementById('cs/0206018v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 9 September, 2002; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 11 June, 2002; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2002. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">12 pages, 4 figures</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">ACM Class:</span> F.2.2; G.2.2 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/cs/0204050">arXiv:cs/0204050</a> <span> [<a href="https://arxiv.org/pdf/cs/0204050">pdf</a>, <a href="https://arxiv.org/ps/cs/0204050">ps</a>, <a href="https://arxiv.org/format/cs/0204050">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Geometry">cs.CG</span> </div> </div> <p class="title is-5 mathjax"> Computing Homotopic Shortest Paths Efficiently </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Alon Efrat</a>, <a href="/search/cs?searchtype=author&query=Kobourov%2C+S+G">Stephen G. Kobourov</a>, <a href="/search/cs?searchtype=author&query=Lubiw%2C+A">Anna Lubiw</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="cs/0204050v1-abstract-short" style="display: inline;"> This paper addresses the problem of finding shortest paths homotopic to a given disjoint set of paths that wind amongst point obstacles in the plane. We present a faster algorithm than previously known. </span> <span class="abstract-full has-text-grey-dark mathjax" id="cs/0204050v1-abstract-full" style="display: none;"> This paper addresses the problem of finding shortest paths homotopic to a given disjoint set of paths that wind amongst point obstacles in the plane. We present a faster algorithm than previously known. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('cs/0204050v1-abstract-full').style.display = 'none'; document.getElementById('cs/0204050v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 25 April, 2002; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2002. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">12 pages, 11 figures</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">ACM Class:</span> I.3.5; F.2.2 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/cs/0009013">arXiv:cs/0009013</a> <span> [<a href="https://arxiv.org/pdf/cs/0009013">pdf</a>, <a href="https://arxiv.org/ps/cs/0009013">ps</a>, <a href="https://arxiv.org/format/cs/0009013">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Geometry">cs.CG</span> </div> </div> <p class="title is-5 mathjax"> Pattern Matching for sets of segments </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Efrat%2C+A">Alon Efrat</a>, <a href="/search/cs?searchtype=author&query=Indyk%2C+P">Piotr Indyk</a>, <a href="/search/cs?searchtype=author&query=Venkatasubramanian%2C+S">Suresh Venkatasubramanian</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="cs/0009013v2-abstract-short" style="display: inline;"> In this paper we present algorithms for a number of problems in geometric pattern matching where the input consist of a collections of segments in the plane. Our work consists of two main parts. In the first, we address problems and measures that relate to collections of orthogonal line segments in the plane. Such collections arise naturally from problems in mapping buildings and robot explorati… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('cs/0009013v2-abstract-full').style.display = 'inline'; document.getElementById('cs/0009013v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="cs/0009013v2-abstract-full" style="display: none;"> In this paper we present algorithms for a number of problems in geometric pattern matching where the input consist of a collections of segments in the plane. Our work consists of two main parts. In the first, we address problems and measures that relate to collections of orthogonal line segments in the plane. Such collections arise naturally from problems in mapping buildings and robot exploration. We propose a new measure of segment similarity called a \emph{coverage measure}, and present efficient algorithms for maximising this measure between sets of axis-parallel segments under translations. Our algorithms run in time $O(n^3\polylog n)$ in the general case, and run in time $O(n^2\polylog n)$ for the case when all segments are horizontal. In addition, we show that when restricted to translations that are only vertical, the Hausdorff distance between two sets of horizontal segments can be computed in time roughly $O(n^{3/2}{\sl polylog}n)$. These algorithms form significant improvements over the general algorithm of Chew et al. that takes time $O(n^4 \log^2 n)$. In the second part of this paper we address the problem of matching polygonal chains. We study the well known \Frd, and present the first algorithm for computing the \Frd under general translations. Our methods also yield algorithms for computing a generalization of the \Fr distance, and we also present a simple approximation algorithm for the \Frd that runs in time $O(n^2\polylog n)$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('cs/0009013v2-abstract-full').style.display = 'none'; document.getElementById('cs/0009013v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 22 September, 2000; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 19 September, 2000; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2000. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">To appear in the 12 ACM Symposium on Discrete Algorithms, Jan 2001</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">ACM Class:</span> F.2.2 </p> </li> </ol> <div class="is-hidden-tablet">  <span class="help" style="display: inline-block;"><a href="https://github.com/arXiv/arxiv-search/releases">Search v0.5.6 released 2020-02-24</a>  </span> </div> </div> </main> <footer> <div class="columns is-desktop" role="navigation" aria-label="Secondary">  <div class="column"> <div class="columns"> <div class="column"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/about">About</a></li> <li><a href="https://info.arxiv.org/help">Help</a></li> </ul> </div> <div class="column"> <ul class="nav-spaced"> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>contact arXiv</title><desc>Click here to contact arXiv</desc><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg> <a href="https://info.arxiv.org/help/contact.html"> Contact</a> </li> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>subscribe to arXiv mailings</title><desc>Click here to subscribe</desc><path d="M476 3.2L12.5 270.6c-18.1 10.4-15.8 35.6 2.2 43.2L121 358.4l287.3-253.2c5.5-4.9 13.3 2.6 8.6 8.3L176 407v80.5c0 23.6 28.5 32.9 42.5 15.8L282 426l124.6 52.2c14.2 6 30.4-2.9 33-18.2l72-432C515 7.8 493.3-6.8 476 3.2z"/></svg> <a href="https://info.arxiv.org/help/subscribe"> Subscribe</a> </li> </ul> </div> </div> </div>   <div class="column"> <div class="columns"> <div class="column"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/help/license/index.html">Copyright</a></li> <li><a href="https://info.arxiv.org/help/policies/privacy_policy.html">Privacy Policy</a></li> </ul> </div> <div class="column sorry-app-links"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/help/web_accessibility.html">Web Accessibility Assistance</a></li> <li> <p class="help"> <a class="a11y-main-link" href="https://status.arxiv.org" target="_blank">arXiv Operational Status <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 256 512" class="icon filter-dark_grey" role="presentation"><path d="M224.3 273l-136 136c-9.4 9.4-24.6 9.4-33.9 0l-22.6-22.6c-9.4-9.4-9.4-24.6 0-33.9l96.4-96.4-96.4-96.4c-9.4-9.4-9.4-24.6 0-33.9L54.3 103c9.4-9.4 24.6-9.4 33.9 0l136 136c9.5 9.4 9.5 24.6.1 34z"/></svg></a><br> Get status notifications via <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/email/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg>email</a> or <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/slack/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512" class="icon filter-black" role="presentation"><path d="M94.12 315.1c0 25.9-21.16 47.06-47.06 47.06S0 341 0 315.1c0-25.9 21.16-47.06 47.06-47.06h47.06v47.06zm23.72 0c0-25.9 21.16-47.06 47.06-47.06s47.06 21.16 47.06 47.06v117.84c0 25.9-21.16 47.06-47.06 47.06s-47.06-21.16-47.06-47.06V315.1zm47.06-188.98c-25.9 0-47.06-21.16-47.06-47.06S139 32 164.9 32s47.06 21.16 47.06 47.06v47.06H164.9zm0 23.72c25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06H47.06C21.16 243.96 0 222.8 0 196.9s21.16-47.06 47.06-47.06H164.9zm188.98 47.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06h-47.06V196.9zm-23.72 0c0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06V79.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06V196.9zM283.1 385.88c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06v-47.06h47.06zm0-23.72c-25.9 0-47.06-21.16-47.06-47.06 0-25.9 21.16-47.06 47.06-47.06h117.84c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06H283.1z"/></svg>slack</a> </p> </li> </ul> </div> </div> </div>  </div> </footer> <script src="https://static.arxiv.org/static/base/1.0.0a5/js/member_acknowledgement.js"></script> </body> </html>

CINXE.COM

Search | arXiv e-print repository