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–16 of 16 results for author: <span class="mathjax">Velusamy, S</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=Velusamy%2C+S">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="Velusamy, S"> </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=Velusamy%2C+S&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="Velusamy, S"> <ul id="abstracts"><li><input checked id="abstracts-0" name="abstracts" type="radio" value="show"> <label for="abstracts-0">Show abstracts</label></li><li><input id="abstracts-1" name="abstracts" type="radio" value="hide"> <label for="abstracts-1">Hide abstracts</label></li></ul> </div> <div class="box field is-grouped is-grouped-multiline level-item"> <div class="control"> <span class="select is-small"> <select id="size" name="size"><option value="25">25</option><option selected value="50">50</option><option value="100">100</option><option value="200">200</option></select> </span> <label for="size">results per page</label>. </div> <div class="control"> <label for="order">Sort results by</label> <span class="select is-small"> <select id="order" name="order"><option selected value="-announced_date_first">Announcement date (newest first)</option><option value="announced_date_first">Announcement date (oldest first)</option><option value="-submitted_date">Submission date (newest first)</option><option value="submitted_date">Submission date (oldest first)</option><option value="">Relevance</option></select> </span> </div> <div class="control"> <button class="button is-small is-link">Go</button> </div> </div> </form> </div> </div> <ol class="breathe-horizontal" start="1"> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2411.18829">arXiv:2411.18829</a> <span> [<a href="https://arxiv.org/pdf/2411.18829">pdf</a>, <a href="https://arxiv.org/ps/2411.18829">ps</a>, <a href="https://arxiv.org/format/2411.18829">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"> Streaming Algorithms via Local Algorithms for Maximum Directed Cut </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Saxena%2C+R+R">Raghuvansh R. Saxena</a>, <a href="/search/cs?searchtype=author&query=Singer%2C+N+G">Noah G. Singer</a>, <a href="/search/cs?searchtype=author&query=Sudan%2C+M">Madhu Sudan</a>, <a href="/search/cs?searchtype=author&query=Velusamy%2C+S">Santhoshini Velusamy</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2411.18829v1-abstract-short" style="display: inline;"> We explore the use of local algorithms in the design of streaming algorithms for the Maximum Directed Cut problem. Specifically, building on the local algorithm of Buchbinder et al. (FOCS'12) and Censor-Hillel et al. (ALGOSENSORS'17), we develop streaming algorithms for both adversarially and randomly ordered streams that approximate the value of maximum directed cut in bounded-degree graphs. In… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.18829v1-abstract-full').style.display = 'inline'; document.getElementById('2411.18829v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2411.18829v1-abstract-full" style="display: none;"> We explore the use of local algorithms in the design of streaming algorithms for the Maximum Directed Cut problem. Specifically, building on the local algorithm of Buchbinder et al. (FOCS'12) and Censor-Hillel et al. (ALGOSENSORS'17), we develop streaming algorithms for both adversarially and randomly ordered streams that approximate the value of maximum directed cut in bounded-degree graphs. In $n$-vertex graphs, for adversarially ordered streams, our algorithm uses $O(n^{1-惟(1)})$ (sub-linear) space and for randomly ordered streams, our algorithm uses logarithmic space. Moreover, both algorithms require only one pass over the input stream. With a constant number of passes, we give a logarithmic-space algorithm which works even on graphs with unbounded degree on adversarially ordered streams. Our algorithms achieve any fixed constant approximation factor less than $\frac12$. In the single-pass setting, this is tight: known lower bounds show that obtaining any constant approximation factor greater than $\frac12$ is impossible without using linear space in adversarially ordered streams (Kapralov and Krachun, STOC'19) and $惟(\sqrt{n})$ space in randomly ordered streams, even on bounded degree graphs (Kapralov, Khanna, and Sudan, SODA'15). In terms of techniques, our algorithms partition the vertices into a small number of different types based on the structure of their local neighborhood, ensuring that each type carries enough information about the structure to approximately simulate the local algorithm on a vertex with that type. We then develop tools to accurately estimate the frequency of each type. This allows us to simulate an execution of the local algorithm on all vertices, and thereby approximate the value of the maximum directed cut. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.18829v1-abstract-full').style.display = 'none'; document.getElementById('2411.18829v1-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> 27 November, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">45 pages, to appear in SODA 2025</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2411.12976">arXiv:2411.12976</a> <span> [<a href="https://arxiv.org/pdf/2411.12976">pdf</a>, <a href="https://arxiv.org/ps/2411.12976">ps</a>, <a href="https://arxiv.org/format/2411.12976">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"> Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Hwang%2C+S">Samuel Hwang</a>, <a href="/search/cs?searchtype=author&query=Singer%2C+N+G">Noah G. Singer</a>, <a href="/search/cs?searchtype=author&query=Velusamy%2C+S">Santhoshini Velusamy</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2411.12976v1-abstract-short" style="display: inline;"> In the maximum directed cut problem, the input is a directed graph $G=(V,E)$, and the goal is to pick a partition $V = S \cup (V \setminus S)$ of the vertices such that as many edges as possible go from $S$ to $V\setminus S$. Oblivious algorithms, introduced by Feige and Jozeph (Algorithmica'17), are a simple class of algorithms for this problem. These algorithms independently and randomly assign… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.12976v1-abstract-full').style.display = 'inline'; document.getElementById('2411.12976v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2411.12976v1-abstract-full" style="display: none;"> In the maximum directed cut problem, the input is a directed graph $G=(V,E)$, and the goal is to pick a partition $V = S \cup (V \setminus S)$ of the vertices such that as many edges as possible go from $S$ to $V\setminus S$. Oblivious algorithms, introduced by Feige and Jozeph (Algorithmica'17), are a simple class of algorithms for this problem. These algorithms independently and randomly assign each vertex $v$ to either $S$ or $V \setminus S$, and the distribution of $v$'s assignment is determined using only extremely local information about $v$: its bias, i.e., the relative difference between its out- and in-degrees. These algorithms have natural implementations in certain graph streaming models, where they have important implications (Saxena, Singer, Sudan, and Velusamy, SODA'23, FOCS'23, Kallaugher, Parekh, and Voronova, STOC'24). In this work, we narrow the gap between upper and lower bounds on the best approximation ratio achievable by oblivious algorithms for Max-Directed-Cut. We show that there exists an oblivious algorithm achieving an approximation ratio of at least $0.4853$, while every oblivious algorithm obeying a natural symmetry property achieves an approximation ratio of at most $0.4889$. The previous known bounds were $0.4844$ and $0.4899$, due to Singer (APPROX'23) and Feige and Jozeph, respectively. Our techniques involve designing principled parameterizations of the spaces of algorithms and lower bounds and then executing computer searches through these spaces. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2411.12976v1-abstract-full').style.display = 'none'; document.getElementById('2411.12976v1-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 November, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">17 pages, 7 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/2301.09170">arXiv:2301.09170</a> <span>  </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Combinatorics">math.CO</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> </div> </div> <p class="title is-5 mathjax"> On the size of maximum cut in planar graphs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Gorantla%2C+P">Pranay Gorantla</a>, <a href="/search/cs?searchtype=author&query=Velusamy%2C+S">Santhoshini Velusamy</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="2301.09170v2-abstract-short" style="display: inline;"> We show that the size of maximum cut in a planar graph with $m$ edges is at least $2m/3$. We also show that maximal planar graphs saturate this bound. </span> <span class="abstract-full has-text-grey-dark mathjax" id="2301.09170v2-abstract-full" style="display: none;"> We show that the size of maximum cut in a planar graph with $m$ edges is at least $2m/3$. We also show that maximal planar graphs saturate this bound. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2301.09170v2-abstract-full').style.display = 'none'; document.getElementById('2301.09170v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 24 January, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 22 January, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 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">The main result already appeared in an answer to a question posted on math stack exchange in 2016</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2211.03916">arXiv:2211.03916</a> <span> [<a href="https://arxiv.org/pdf/2211.03916">pdf</a>, <a href="https://arxiv.org/ps/2211.03916">ps</a>, <a href="https://arxiv.org/format/2211.03916">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 Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Saxena%2C+R+R">Raghuvansh R. Saxena</a>, <a href="/search/cs?searchtype=author&query=Singer%2C+N+G">Noah G. Singer</a>, <a href="/search/cs?searchtype=author&query=Sudan%2C+M">Madhu Sudan</a>, <a href="/search/cs?searchtype=author&query=Velusamy%2C+S">Santhoshini Velusamy</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.03916v2-abstract-short" style="display: inline;"> We give an $\widetilde{O}(\sqrt{n})$-space single-pass $0.483$-approximation streaming algorithm for estimating the maximum directed cut size (Max-DICUT) in a directed graph on $n$ vertices. This improves over an $O(\log n)$-space $4/9 < 0.45$ approximation algorithm due to Chou, Golovnev, and Velusamy (FOCS 2020), which was known to be optimal for $o(\sqrt{n})$-space algorithms. Max-DICUT is a sp… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2211.03916v2-abstract-full').style.display = 'inline'; document.getElementById('2211.03916v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2211.03916v2-abstract-full" style="display: none;"> We give an $\widetilde{O}(\sqrt{n})$-space single-pass $0.483$-approximation streaming algorithm for estimating the maximum directed cut size (Max-DICUT) in a directed graph on $n$ vertices. This improves over an $O(\log n)$-space $4/9 < 0.45$ approximation algorithm due to Chou, Golovnev, and Velusamy (FOCS 2020), which was known to be optimal for $o(\sqrt{n})$-space algorithms. Max-DICUT is a special case of a constraint satisfaction problem (CSP). In this broader context, we give the first CSP for which algorithms with $\widetilde{O}(\sqrt{n})$ space can provably outperform $o(\sqrt{n})$-space algorithms. The key technical contribution of our work is development of the notions of a first-order snapshot of a (directed) graph and of estimates of such snapshots. These snapshots can be used to simulate certain (non-streaming) Max-DICUT algorithms, including the "oblivious" algorithms introduced by Feige and Jozeph (Algorithmica, 2015), who showed that one such algorithm achieves a 0.483-approximation. Previous work of the authors (SODA 2023) studied the restricted case of bounded-degree graphs, and observed that in this setting, it is straightforward to estimate the snapshot with $\ell_1$ errors and this suffices to simulate oblivious algorithms. But for unbounded-degree graphs, even defining an achievable and sufficient notion of estimation is subtle. We describe a new notion of snapshot estimation and prove its sufficiency using careful smoothing techniques, and then develop an algorithm which sketches such an estimate via a delicate process of intertwined vertex- and edge-subsampling. Prior to our work, the only streaming algorithms for any CSP on general instances were based on generalizations of the $O(\log n)$-space algorithm for Max-DICUT, and thus our work opens the possibility of a new class of algorithms for approximating CSPs. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2211.03916v2-abstract-full').style.display = 'none'; document.getElementById('2211.03916v2-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 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 7 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">53 pages, 2 figures; substantial revisions; in submission; abstract shortened to fit requirements</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2209.05614">arXiv:2209.05614</a> <span> [<a href="https://arxiv.org/pdf/2209.05614">pdf</a>, <a href="https://arxiv.org/ps/2209.05614">ps</a>, <a href="https://arxiv.org/format/2209.05614">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> An Improved Lower Bound for Matroid Intersection Prophet Inequalities </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Saxena%2C+R+R">Raghuvansh R. Saxena</a>, <a href="/search/cs?searchtype=author&query=Velusamy%2C+S">Santhoshini Velusamy</a>, <a href="/search/cs?searchtype=author&query=Weinberg%2C+S+M">S. Matthew Weinberg</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="2209.05614v1-abstract-short" style="display: inline;"> We consider prophet inequalities subject to feasibility constraints that are the intersection of $q$ matroids. The best-known algorithms achieve a $螛(q)$-approximation, even when restricted to instances that are the intersection of $q$ partition matroids, and with i.i.d.~Bernoulli random variables. The previous best-known lower bound is $螛(\sqrt{q})$ due to a simple construction of [Kleinberg-Wein… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2209.05614v1-abstract-full').style.display = 'inline'; document.getElementById('2209.05614v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2209.05614v1-abstract-full" style="display: none;"> We consider prophet inequalities subject to feasibility constraints that are the intersection of $q$ matroids. The best-known algorithms achieve a $螛(q)$-approximation, even when restricted to instances that are the intersection of $q$ partition matroids, and with i.i.d.~Bernoulli random variables. The previous best-known lower bound is $螛(\sqrt{q})$ due to a simple construction of [Kleinberg-Weinberg STOC 2012] (which uses i.i.d.~Bernoulli random variables, and writes the construction as the intersection of partition matroids). We establish an improved lower bound of $q^{1/2+惟(1/\log \log q)}$ by writing the construction of [Kleinberg-Weinberg STOC 2012] as the intersection of asymptotically fewer partition matroids. We accomplish this via an improved upper bound on the product dimension of a graph with $p^p$ disjoint cliques of size $p$, using recent techniques developed in [Alon-Alweiss European Journal of Combinatorics 2020]. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2209.05614v1-abstract-full').style.display = 'none'; document.getElementById('2209.05614v1-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 September, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2022. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2207.07158">arXiv:2207.07158</a> <span> [<a href="https://arxiv.org/pdf/2207.07158">pdf</a>, <a href="https://arxiv.org/ps/2207.07158">ps</a>, <a href="https://arxiv.org/format/2207.07158">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </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.1137/1.9781611977554.ch156">10.1137/1.9781611977554.ch156 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Streaming complexity of CSPs with randomly ordered constraints </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Saxena%2C+R+R">Raghuvansh R. Saxena</a>, <a href="/search/cs?searchtype=author&query=Singer%2C+N">Noah Singer</a>, <a href="/search/cs?searchtype=author&query=Sudan%2C+M">Madhu Sudan</a>, <a href="/search/cs?searchtype=author&query=Velusamy%2C+S">Santhoshini Velusamy</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="2207.07158v1-abstract-short" style="display: inline;"> We initiate a study of the streaming complexity of constraint satisfaction problems (CSPs) when the constraints arrive in a random order. We show that there exists a CSP, namely $\textsf{Max-DICUT}$, for which random ordering makes a provable difference. Whereas a $4/9 \approx 0.445$ approximation of $\textsf{DICUT}$ requires $惟(\sqrt{n})$ space with adversarial ordering, we show that with random… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2207.07158v1-abstract-full').style.display = 'inline'; document.getElementById('2207.07158v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2207.07158v1-abstract-full" style="display: none;"> We initiate a study of the streaming complexity of constraint satisfaction problems (CSPs) when the constraints arrive in a random order. We show that there exists a CSP, namely $\textsf{Max-DICUT}$, for which random ordering makes a provable difference. Whereas a $4/9 \approx 0.445$ approximation of $\textsf{DICUT}$ requires $惟(\sqrt{n})$ space with adversarial ordering, we show that with random ordering of constraints there exists a $0.48$-approximation algorithm that only needs $O(\log n)$ space. We also give new algorithms for $\textsf{Max-DICUT}$ in variants of the adversarial ordering setting. Specifically, we give a two-pass $O(\log n)$ space $0.48$-approximation algorithm for general graphs and a single-pass $\tilde{O}(\sqrt{n})$ space $0.48$-approximation algorithm for bounded degree graphs. On the negative side, we prove that CSPs where the satisfying assignments of the constraints support a one-wise independent distribution require $惟(\sqrt{n})$-space for any non-trivial approximation, even when the constraints are randomly ordered. This was previously known only for adversarially ordered constraints. Extending the results to randomly ordered constraints requires switching the hard instances from a union of random matchings to simple Erd枚s-Renyi random (hyper)graphs and extending tools that can perform Fourier analysis on such instances. The only CSP to have been considered previously with random ordering is $\textsf{Max-CUT}$ where the ordering is not known to change the approximability. Specifically it is known to be as hard to approximate with random ordering as with adversarial ordering, for $o(\sqrt{n})$ space algorithms. Our results show a richer variety of possibilities and motivate further study of CSPs with randomly ordered constraints. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2207.07158v1-abstract-full').style.display = 'none'; document.getElementById('2207.07158v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 14 July, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2022. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2205.02345">arXiv:2205.02345</a> <span> [<a href="https://arxiv.org/pdf/2205.02345">pdf</a>, <a href="https://arxiv.org/ps/2205.02345">ps</a>, <a href="https://arxiv.org/format/2205.02345">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </div> </div> <p class="title is-5 mathjax"> Sketching Approximability of (Weak) Monarchy Predicates </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Chou%2C+C">Chi-Ning Chou</a>, <a href="/search/cs?searchtype=author&query=Golovnev%2C+A">Alexander Golovnev</a>, <a href="/search/cs?searchtype=author&query=Shahrasbi%2C+A">Amirbehshad Shahrasbi</a>, <a href="/search/cs?searchtype=author&query=Sudan%2C+M">Madhu Sudan</a>, <a href="/search/cs?searchtype=author&query=Velusamy%2C+S">Santhoshini Velusamy</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="2205.02345v2-abstract-short" style="display: inline;"> We analyze the sketching approximability of constraint satisfaction problems on Boolean domains, where the constraints are balanced linear threshold functions applied to literals. In~particular, we explore the approximability of monarchy-like functions where the value of the function is determined by a weighted combination of the vote of the first variable (the president) and the sum of the votes… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2205.02345v2-abstract-full').style.display = 'inline'; document.getElementById('2205.02345v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2205.02345v2-abstract-full" style="display: none;"> We analyze the sketching approximability of constraint satisfaction problems on Boolean domains, where the constraints are balanced linear threshold functions applied to literals. In~particular, we explore the approximability of monarchy-like functions where the value of the function is determined by a weighted combination of the vote of the first variable (the president) and the sum of the votes of all remaining variables. The pure version of this function is when the president can only be overruled by when all remaining variables agree. For every $k \geq 5$, we show that CSPs where the underlying predicate is a pure monarchy function on $k$ variables have no non-trivial sketching approximation algorithm in $o(\sqrt{n})$ space. We also show infinitely many weaker monarchy functions for which CSPs using such constraints are non-trivially approximable by $O(\log(n))$ space sketching algorithms. Moreover, we give the first example of sketching approximable asymmetric Boolean CSPs. Our results work within the framework of Chou, Golovnev, Sudan, and Velusamy (FOCS 2021) that characterizes the sketching approximability of all CSPs. Their framework can be applied naturally to get a computer-aided analysis of the approximability of any specific constraint satisfaction problem. The novelty of our work is in using their work to get an analysis that applies to infinitely many problems simultaneously. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2205.02345v2-abstract-full').style.display = 'none'; document.getElementById('2205.02345v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 15 July, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 4 May, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2022. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2202.05186">arXiv:2202.05186</a> <span> [<a href="https://arxiv.org/pdf/2202.05186">pdf</a>, <a href="https://arxiv.org/format/2202.05186">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Theoretical Economics">econ.TH</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.1137/1.9781611977554.ch13">10.1137/1.9781611977554.ch13 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Fair allocation of a multiset of indivisible items </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Gorantla%2C+P">Pranay Gorantla</a>, <a href="/search/cs?searchtype=author&query=Marwaha%2C+K">Kunal Marwaha</a>, <a href="/search/cs?searchtype=author&query=Velusamy%2C+S">Santhoshini Velusamy</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="2202.05186v5-abstract-short" style="display: inline;"> We study the problem of fairly allocating a multiset $M$ of $m$ indivisible items among $n$ agents with additive valuations. Specifically, we introduce a parameter $t$ for the number of distinct types of items and study fair allocations of multisets that contain only items of these $t$ types, under two standard notions of fairness: 1. Envy-freeness (EF): For arbitrary $n$, $t$, we show that a co… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2202.05186v5-abstract-full').style.display = 'inline'; document.getElementById('2202.05186v5-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2202.05186v5-abstract-full" style="display: none;"> We study the problem of fairly allocating a multiset $M$ of $m$ indivisible items among $n$ agents with additive valuations. Specifically, we introduce a parameter $t$ for the number of distinct types of items and study fair allocations of multisets that contain only items of these $t$ types, under two standard notions of fairness: 1. Envy-freeness (EF): For arbitrary $n$, $t$, we show that a complete EF allocation exists when at least one agent has a unique valuation and the number of items of each type exceeds a particular finite threshold. We give explicit upper and lower bounds on this threshold in some special cases. 2. Envy-freeness up to any good (EFX): For arbitrary $n$, $m$, and for $t\le 2$, we show that a complete EFX allocation always exists. We give two different proofs of this result. One proof is constructive and runs in polynomial time; the other is geometrically inspired. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2202.05186v5-abstract-full').style.display = 'none'; document.getElementById('2202.05186v5-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 November, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 10 February, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 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">34 pages, 6 figures, 1 table, 1 algorithm</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> In Proceedings of the Symposium on Discrete Algorithms (SODA 2023); pp. 304-331 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2112.06319">arXiv:2112.06319</a> <span> [<a href="https://arxiv.org/pdf/2112.06319">pdf</a>, <a href="https://arxiv.org/ps/2112.06319">ps</a>, <a href="https://arxiv.org/format/2112.06319">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </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.4230/LIPIcs.APPROX/RANDOM.2022.38">10.4230/LIPIcs.APPROX/RANDOM.2022.38 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> On sketching approximations for symmetric Boolean CSPs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Boyland%2C+J">Joanna Boyland</a>, <a href="/search/cs?searchtype=author&query=Hwang%2C+M">Michael Hwang</a>, <a href="/search/cs?searchtype=author&query=Prasad%2C+T">Tarun Prasad</a>, <a href="/search/cs?searchtype=author&query=Singer%2C+N">Noah Singer</a>, <a href="/search/cs?searchtype=author&query=Velusamy%2C+S">Santhoshini Velusamy</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="2112.06319v3-abstract-short" style="display: inline;"> A Boolean maximum constraint satisfaction problem, Max-CSP($f$), is specified by a predicate $f:\{-1,1\}^k\to\{0,1\}$. An $n$-variable instance of Max-CSP($f$) consists of a list of constraints, each of which applies $f$ to $k$ distinct literals drawn from the $n$ variables. For $k=2$, Chou, Golovnev, and Velusamy [CGV20, FOCS 2020] obtained explicit ratios characterizing the $\sqrt n$-space strea… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2112.06319v3-abstract-full').style.display = 'inline'; document.getElementById('2112.06319v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2112.06319v3-abstract-full" style="display: none;"> A Boolean maximum constraint satisfaction problem, Max-CSP($f$), is specified by a predicate $f:\{-1,1\}^k\to\{0,1\}$. An $n$-variable instance of Max-CSP($f$) consists of a list of constraints, each of which applies $f$ to $k$ distinct literals drawn from the $n$ variables. For $k=2$, Chou, Golovnev, and Velusamy [CGV20, FOCS 2020] obtained explicit ratios characterizing the $\sqrt n$-space streaming approximability of every predicate. For $k \geq 3$, Chou, Golovnev, Sudan, and Velusamy [CGSV21, arXiv:2102.12351] proved a general dichotomy theorem for $\sqrt n$-space sketching algorithms: For every $f$, there exists $伪(f)\in (0,1]$ such that for every $蔚>0$, Max-CSP($f$) is $(伪(f)-蔚)$-approximable by an $O(\log n)$-space linear sketching algorithm, but $(伪(f)+蔚)$-approximation sketching algorithms require $惟(\sqrt{n})$ space. In this work, we give closed-form expressions for the sketching approximation ratios of multiple families of symmetric Boolean functions. Letting $伪'_k = 2^{-(k-1)} (1-k^{-2})^{(k-1)/2}$, we show that for odd $k \geq 3$, $伪(k$AND$) = 伪'_k$, and for even $k \geq 2$, $伪(k$AND$) = 2伪'_{k+1}$. We also resolve the ratio for the "at-least-$(k-1)$-$1$'s" function for all even $k$; the "exactly-$\frac{k+1}2$-$1$'s" function for odd $k \in \{3,\ldots,51\}$; and fifteen other functions. We stress here that for general $f$, according to [CGSV21], closed-form expressions for $伪(f)$ need not have existed a priori. Separately, for all threshold functions, we give optimal "bias-based" approximation algorithms generalizing [CGV20] while simplifying [CGSV21]. Finally, we investigate the $\sqrt n$-space streaming lower bounds in [CGSV21], and show that they are incomplete for $3$AND. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2112.06319v3-abstract-full').style.display = 'none'; document.getElementById('2112.06319v3-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 July, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 12 December, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 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">27 pages; same results but significant changes in presentation</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2110.01015">arXiv:2110.01015</a> <span> [<a href="https://arxiv.org/pdf/2110.01015">pdf</a>, <a href="https://arxiv.org/format/2110.01015">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Vision and Pattern Recognition">cs.CV</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"> Spatio-Temporal Video Representation Learning for AI Based Video Playback Style Prediction </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Parihar%2C+R">Rishubh Parihar</a>, <a href="/search/cs?searchtype=author&query=Ramola%2C+G">Gaurav Ramola</a>, <a href="/search/cs?searchtype=author&query=Saha%2C+R">Ranajit Saha</a>, <a href="/search/cs?searchtype=author&query=Kini%2C+R">Ravi Kini</a>, <a href="/search/cs?searchtype=author&query=Rege%2C+A">Aniket Rege</a>, <a href="/search/cs?searchtype=author&query=Velusamy%2C+S">Sudha Velusamy</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="2110.01015v1-abstract-short" style="display: inline;"> Ever-increasing smartphone-generated video content demands intelligent techniques to edit and enhance videos on power-constrained devices. Most of the best performing algorithms for video understanding tasks like action recognition, localization, etc., rely heavily on rich spatio-temporal representations to make accurate predictions. For effective learning of the spatio-temporal representation, it… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2110.01015v1-abstract-full').style.display = 'inline'; document.getElementById('2110.01015v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2110.01015v1-abstract-full" style="display: none;"> Ever-increasing smartphone-generated video content demands intelligent techniques to edit and enhance videos on power-constrained devices. Most of the best performing algorithms for video understanding tasks like action recognition, localization, etc., rely heavily on rich spatio-temporal representations to make accurate predictions. For effective learning of the spatio-temporal representation, it is crucial to understand the underlying object motion patterns present in the video. In this paper, we propose a novel approach for understanding object motions via motion type classification. The proposed motion type classifier predicts a motion type for the video based on the trajectories of the objects present. Our classifier assigns a motion type for the given video from the following five primitive motion classes: linear, projectile, oscillatory, local and random. We demonstrate that the representations learned from the motion type classification generalizes well for the challenging downstream task of video retrieval. Further, we proposed a recommendation system for video playback style based on the motion type classifier predictions. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2110.01015v1-abstract-full').style.display = 'none'; document.getElementById('2110.01015v1-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 October, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 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">10 pages, 5 figures, 4 tables, ICCV Workshops 2021 - SRVU</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2106.13078">arXiv:2106.13078</a> <span> [<a href="https://arxiv.org/pdf/2106.13078">pdf</a>, <a href="https://arxiv.org/format/2106.13078">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Linear Space Streaming Lower Bounds for Approximating CSPs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Chou%2C+C">Chi-Ning Chou</a>, <a href="/search/cs?searchtype=author&query=Golovnev%2C+A">Alexander Golovnev</a>, <a href="/search/cs?searchtype=author&query=Sudan%2C+M">Madhu Sudan</a>, <a href="/search/cs?searchtype=author&query=Velingker%2C+A">Ameya Velingker</a>, <a href="/search/cs?searchtype=author&query=Velusamy%2C+S">Santhoshini Velusamy</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="2106.13078v2-abstract-short" style="display: inline;"> We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on $n$ variables taking values in $\{0,\ldots,q-1\}$, we prove that improving over the trivial approximability by a factor of $q$ requires $惟(n)$ space even on instances with $O(n)$ constraints. We also identify a broad subclass of problems for which any imp… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2106.13078v2-abstract-full').style.display = 'inline'; document.getElementById('2106.13078v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2106.13078v2-abstract-full" style="display: none;"> We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on $n$ variables taking values in $\{0,\ldots,q-1\}$, we prove that improving over the trivial approximability by a factor of $q$ requires $惟(n)$ space even on instances with $O(n)$ constraints. We also identify a broad subclass of problems for which any improvement over the trivial approximability requires $惟(n)$ space. The key technical core is an optimal, $q^{-(k-1)}$-inapproximability for the \textsf{Max $k$-LIN}-$\bmod\; q$ problem, which is the Max CSP problem where every constraint is given by a system of $k-1$ linear equations $\bmod\; q$ over $k$ variables. Our work builds on and extends the breakthrough work of Kapralov and Krachun (Proc. STOC 2019) who showed a linear lower bound on any non-trivial approximation of the MaxCut problem in graphs. MaxCut corresponds roughly to the case of \textsf{Max $k$-LIN}-$\bmod\; q$ with ${k=q=2}$. For general CSPs in the streaming setting, prior results only yielded $惟(\sqrt{n})$ space bounds. In particular no linear space lower bound was known for an approximation factor less than $1/2$ for {\em any} CSP. Extending the work of Kapralov and Krachun to \textsf{Max $k$-LIN}-$\bmod\; q$ to $k>2$ and $q>2$ (while getting optimal hardness results) is the main technical contribution of this work. Each one of these extensions provides non-trivial technical challenges that we overcome in this work. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2106.13078v2-abstract-full').style.display = 'none'; document.getElementById('2106.13078v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 24 April, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 24 June, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2021. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2105.01782">arXiv:2105.01782</a> <span> [<a href="https://arxiv.org/pdf/2105.01782">pdf</a>, <a href="https://arxiv.org/ps/2105.01782">ps</a>, <a href="https://arxiv.org/format/2105.01782">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </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.4230/LIPIcs.APPROX/RANDOM.2021.17">10.4230/LIPIcs.APPROX/RANDOM.2021.17 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </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.1007/s00037-024-00252-5">10.1007/s00037-024-00252-5 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Streaming approximation resistance of every ordering CSP </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Singer%2C+N+G">Noah G. Singer</a>, <a href="/search/cs?searchtype=author&query=Sudan%2C+M">Madhu Sudan</a>, <a href="/search/cs?searchtype=author&query=Velusamy%2C+S">Santhoshini Velusamy</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2105.01782v3-abstract-short" style="display: inline;"> An ordering constraint satisfaction problem (OCSP) is defined by a family $\mathcal{F}$ of predicates mapping permutations on $\{1,\ldots,k\}$ to $\{0,1\}$. An instance of Max-OCSP($\mathcal{F}$) on $n$ variables consists of a list of constraints, each consisting of a predicate from $\mathcal{F}$ applied on $k$ distinct variables. The goal is to find an ordering of the $n$ variables that maximizes… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2105.01782v3-abstract-full').style.display = 'inline'; document.getElementById('2105.01782v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2105.01782v3-abstract-full" style="display: none;"> An ordering constraint satisfaction problem (OCSP) is defined by a family $\mathcal{F}$ of predicates mapping permutations on $\{1,\ldots,k\}$ to $\{0,1\}$. An instance of Max-OCSP($\mathcal{F}$) on $n$ variables consists of a list of constraints, each consisting of a predicate from $\mathcal{F}$ applied on $k$ distinct variables. The goal is to find an ordering of the $n$ variables that maximizes the number of constraints for which the induced ordering on the $k$ variables satisfies the predicate. OCSPs capture well-studied problems including `maximum acyclic subgraph' (MAS) and "maximum betweenness". In this work, we consider the task of approximating the maximum number of satisfiable constraints in the (single-pass) streaming setting, when an instance is presented as a stream of constraints. We show that for every $\mathcal{F}$, Max-OCSP($\mathcal{F}$) is approximation-resistant to $o(n)$-space streaming algorithms, i.e., algorithms using $o(n)$ space cannot distinguish streams where almost every constraint is satisfiable from streams where no ordering beats the random ordering by a noticeable amount. This space bound is tight up to polylogarithmic factors. In the case of MAS our result shows that for every $蔚>0$, MAS is not $(1/2+蔚)$-approximable in $o(n)$ space. The previous best inapproximability result, due to Guruswami and Tao (APPROX'19), only ruled out $3/4$-approximations in $o(\sqrt n)$ space. Our results build on a recent work of Chou, Golovnev, Sudan, Velingker, and Velusamy (STOC'22), who provide a tight, linear-space inapproximability theorem for a broad class of "standard" (i.e., non-ordering) constraint satisfaction problems (CSPs) over arbitrary (finite) alphabets. We construct a family of appropriate standard CSPs from any given OCSP, apply their hardness result to this family of CSPs, and then convert back to our OCSP. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2105.01782v3-abstract-full').style.display = 'none'; document.getElementById('2105.01782v3-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 August, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 4 May, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2021. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">21 pages, 1 figure. Abstract abridged. Appeared in APPROX'21 and Computational Complexity</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2105.01161">arXiv:2105.01161</a> <span> [<a href="https://arxiv.org/pdf/2105.01161">pdf</a>, <a href="https://arxiv.org/format/2105.01161">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </div> </div> <p class="title is-5 mathjax"> Sketching approximability of all finite CSPs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Chou%2C+C">Chi-Ning Chou</a>, <a href="/search/cs?searchtype=author&query=Golovnev%2C+A">Alexander Golovnev</a>, <a href="/search/cs?searchtype=author&query=Sudan%2C+M">Madhu Sudan</a>, <a href="/search/cs?searchtype=author&query=Velusamy%2C+S">Santhoshini Velusamy</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2105.01161v5-abstract-short" style="display: inline;"> A constraint satisfaction problem (CSP), $\textsf{Max-CSP}(\mathcal{F})$, is specified by a finite set of constraints $\mathcal{F} \subseteq \{[q]^k \to \{0,1\}\}$ for positive integers $q$ and $k$. An instance of the problem on $n$ variables is given by $m$ applications of constraints from $\mathcal{F}$ to subsequences of the $n$ variables, and the goal is to find an assignment to the variables t… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2105.01161v5-abstract-full').style.display = 'inline'; document.getElementById('2105.01161v5-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2105.01161v5-abstract-full" style="display: none;"> A constraint satisfaction problem (CSP), $\textsf{Max-CSP}(\mathcal{F})$, is specified by a finite set of constraints $\mathcal{F} \subseteq \{[q]^k \to \{0,1\}\}$ for positive integers $q$ and $k$. An instance of the problem on $n$ variables is given by $m$ applications of constraints from $\mathcal{F}$ to subsequences of the $n$ variables, and the goal is to find an assignment to the variables that satisfies the maximum number of constraints. In the $(纬,尾)$-approximation version of the problem for parameters $0 \leq 尾< 纬\leq 1$, the goal is to distinguish instances where at least $纬$ fraction of the constraints can be satisfied from instances where at most $尾$ fraction of the constraints can be satisfied. In this work we consider the approximability of this problem in the context of sketching algorithms and give a dichotomy result. Specifically, for every family $\mathcal{F}$ and every $尾< 纬$, we show that either a linear sketching algorithm solves the problem in polylogarithmic space, or the problem is not solvable by any sketching algorithm in $o(\sqrt{n})$ space. In particular, we give non-trivial approximation algorithms using polylogarithmic space for infinitely many constraint satisfaction problems. We also extend previously known lower bounds for general streaming algorithms to a wide variety of problems, and in particular the case of $q=k=2$, where we get a dichotomy, and the case when the satisfying assignments of the constraints of $\mathcal{F}$ support a distribution on $[q]^k$ with uniform marginals. Prior to this work, other than sporadic examples, the only systematic classes of CSPs that were analyzed considered the setting of Boolean variables $q=2$, binary constraints $k=2$, singleton families $|\mathcal{F}|=1$ and only considered the setting where constraints are placed on literals rather than variables. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2105.01161v5-abstract-full').style.display = 'none'; document.getElementById('2105.01161v5-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 February, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 3 May, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2021. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Updated version to appear in JACM arXiv admin note: text overlap with arXiv:2102.12351</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2102.12351">arXiv:2102.12351</a> <span> [<a href="https://arxiv.org/pdf/2102.12351">pdf</a>, <a href="https://arxiv.org/format/2102.12351">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Approximability of all Boolean CSPs with linear sketches </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Chou%2C+C">Chi-Ning Chou</a>, <a href="/search/cs?searchtype=author&query=Golovnev%2C+A">Alexander Golovnev</a>, <a href="/search/cs?searchtype=author&query=Sudan%2C+M">Madhu Sudan</a>, <a href="/search/cs?searchtype=author&query=Velusamy%2C+S">Santhoshini Velusamy</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="2102.12351v8-abstract-short" style="display: inline;"> In this work we consider the approximability of $\textsf{Max-CSP}(f)$ in the context of sketching algorithms and completely characterize the approximability of all Boolean CSPs. Specifically, given $f$, $纬$ and $尾$ we show that either (1) the $(纬,尾)$-approximation version of $\textsf{Max-CSP}(f)$ has a linear sketching algorithm using $O(\log n)$ space, or (2) for every $蔚> 0$ the $(纬-蔚,尾+蔚)$-appr… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2102.12351v8-abstract-full').style.display = 'inline'; document.getElementById('2102.12351v8-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2102.12351v8-abstract-full" style="display: none;"> In this work we consider the approximability of $\textsf{Max-CSP}(f)$ in the context of sketching algorithms and completely characterize the approximability of all Boolean CSPs. Specifically, given $f$, $纬$ and $尾$ we show that either (1) the $(纬,尾)$-approximation version of $\textsf{Max-CSP}(f)$ has a linear sketching algorithm using $O(\log n)$ space, or (2) for every $蔚> 0$ the $(纬-蔚,尾+蔚)$-approximation version of $\textsf{Max-CSP}(f)$ requires $惟(\sqrt{n})$ space for any sketching algorithm. We also prove lower bounds against streaming algorithms for several CSPs. In particular, we recover the streaming dichotomy of [CGV20] for $k=2$ and show streaming approximation resistance of all CSPs for which $f^{-1}(1)$ supports a distribution with uniform marginals. Our positive results show wider applicability of bias-based algorithms used previously by [GVV17] and [CGV20] by giving a systematic way to discover biases. Our negative results combine the Fourier analytic methods of [KKS15], which we extend to a wider class of CSPs, with a rich collection of reductions among communication complexity problems that lie at the heart of the negative results. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2102.12351v8-abstract-full').style.display = 'none'; document.getElementById('2102.12351v8-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 February, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 24 February, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2021. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2004.11796">arXiv:2004.11796</a> <span> [<a href="https://arxiv.org/pdf/2004.11796">pdf</a>, <a href="https://arxiv.org/format/2004.11796">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computational Complexity">cs.CC</span> </div> </div> <p class="title is-5 mathjax"> Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-kSAT </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Chou%2C+C">Chi-Ning Chou</a>, <a href="/search/cs?searchtype=author&query=Golovnev%2C+A">Alexander Golovnev</a>, <a href="/search/cs?searchtype=author&query=Velusamy%2C+S">Santhoshini Velusamy</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2004.11796v4-abstract-short" style="display: inline;"> We prove tight upper and lower bounds on approximation ratios of all Boolean Max-2CSP problems in the streaming model. Specifically, for every type of Max-2CSP problem, we give an explicit constant $伪$, s.t. for any $蔚>0$ (i) there is an $(伪-蔚)$-streaming approximation using space $O(\log{n})$; and (ii) any $(伪+蔚)$-streaming approximation requires space $惟(\sqrt{n})$. This generalizes the celebrat… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2004.11796v4-abstract-full').style.display = 'inline'; document.getElementById('2004.11796v4-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2004.11796v4-abstract-full" style="display: none;"> We prove tight upper and lower bounds on approximation ratios of all Boolean Max-2CSP problems in the streaming model. Specifically, for every type of Max-2CSP problem, we give an explicit constant $伪$, s.t. for any $蔚>0$ (i) there is an $(伪-蔚)$-streaming approximation using space $O(\log{n})$; and (ii) any $(伪+蔚)$-streaming approximation requires space $惟(\sqrt{n})$. This generalizes the celebrated work of [Kapralov, Khanna, Sudan SODA 2015; Kapralov, Krachun STOC 2019], who showed that the optimal approximation ratio for Max-CUT was $1/2$. Prior to this work, the problem of determining this ratio was open for all other Max-2CSPs. Our results are quite surprising for some specific Max-2CSPs. For the Max-DCUT problem, there was a gap between an upper bound of $1/2$ and a lower bound of $2/5$ [Guruswami, Velingker, Velusamy APPROX 2017]. We show that neither of these bounds is tight, and the optimal ratio for Max-DCUT is $4/9$. We also establish that the tight approximation for Max-2SAT is $\sqrt{2}/2$, and for Exact Max-2SAT it is $3/4$. As a byproduct, our result gives a separation between space-efficient approximations for Max-2SAT and Exact Max-2SAT. This is in sharp contrast to the setting of polynomial-time algorithms with polynomial space, where the two problems are known to be equally hard to approximate. Finally, we prove that the tight streaming approximation for \mksat{} is $\sqrt{2}/2$ for every $k\geq2$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2004.11796v4-abstract-full').style.display = 'none'; document.getElementById('2004.11796v4-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 January, 2021; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 24 April, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2020. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Full version for the conference version appearing in FOCS 2020. Fix an error in the algorithm for Max-kSAT</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2002.06702">arXiv:2002.06702</a> <span> [<a href="https://arxiv.org/pdf/2002.06702">pdf</a>, <a href="https://arxiv.org/ps/2002.06702">ps</a>, <a href="https://arxiv.org/format/2002.06702">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Theoretical Economics">econ.TH</span> </div> </div> <p class="title is-5 mathjax"> Multi-item Non-truthful Auctions Achieve Good Revenue </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Daskalakis%2C+C">Constantinos Daskalakis</a>, <a href="/search/cs?searchtype=author&query=Fishelson%2C+M">Maxwell Fishelson</a>, <a href="/search/cs?searchtype=author&query=Lucier%2C+B">Brendan Lucier</a>, <a href="/search/cs?searchtype=author&query=Syrgkanis%2C+V">Vasilis Syrgkanis</a>, <a href="/search/cs?searchtype=author&query=Velusamy%2C+S">Santhoshini Velusamy</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="2002.06702v6-abstract-short" style="display: inline;"> We present a general framework for designing approximately revenue-optimal mechanisms for multi-item additive auctions, which applies to both truthful and non-truthful auctions. Given a (not necessarily truthful) single-item auction format $A$ satisfying certain technical conditions, we run simultaneous item auctions augmented with a personalized entry fee for each bidder that must be paid before… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2002.06702v6-abstract-full').style.display = 'inline'; document.getElementById('2002.06702v6-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2002.06702v6-abstract-full" style="display: none;"> We present a general framework for designing approximately revenue-optimal mechanisms for multi-item additive auctions, which applies to both truthful and non-truthful auctions. Given a (not necessarily truthful) single-item auction format $A$ satisfying certain technical conditions, we run simultaneous item auctions augmented with a personalized entry fee for each bidder that must be paid before the auction can be accessed. These entry fees depend only on the prior distribution of bidder types, and in particular are independent of realized bids. We bound the revenue of the resulting two-part tariff mechanism using a novel geometric technique that enables revenue guarantees for many common non-truthful auctions that previously had none. Our approach adapts and extends the duality framework of Cai et al [CDW16] beyond truthful auctions. Our framework can be used with many common auction formats, such as simultaneous first-price, simultaneous second-price, and simultaneous all-pay auctions. Our results for first price and all-pay are the first revenue guarantees of non-truthful mechanisms in multi-dimensional environments, addressing an open question in the literature [RST17]. If all-pay auctions are used, we prove that the resulting mechanism is also credible in the sense that the auctioneer cannot benefit by deviating from the stated mechanism after observing agent bids. This is the first static credible mechanism for multi-item additive auctions that achieves a constant factor of the optimal revenue. If second-price auctions are used, we obtain a truthful $O(1)$-approximate mechanism with fixed entry fees that are amenable to tuning via online learning techniques. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2002.06702v6-abstract-full').style.display = 'none'; document.getElementById('2002.06702v6-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> 21 September, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 16 February, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2020. </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