The Year Before Last

[1]

H. Akrami, B. Ray Chaudhury, M. Hoefer, K. Mehlhorn, M. Schmalhofer, G. Shahkarami, G. Varricchio, Q. Vermande, and E. van Wijland, “Maximizing Nash Social Welfare in 2-Value Instances,” 2021. [Online]. Available: https://arxiv.org/abs/2107.08965. (arXiv: 2107.08965)

[arXiv]

[PuRe]

[BibTeX]

[pre-print version]

Abstract

We consider the problem of maximizing the Nash social welfare when allocating a set $\mathcal{G}$ of indivisible goods to a set $\mathcal{N}$ of agents. We study instances, in which all agents have 2-value additive valuations: The value of every agent $i \in \mathcal{N}$ for every good $j \in \mathcal{G}$ is $v_{ij} \in \{p,q\}$, for $p,q \in \mathbb{N}$, $p \le q$. Maybe surprisingly, we design an algorithm to compute an optimal allocation in polynomial time if $p$ divides $q$, i.e., when $p=1$ and $q \in \mathbb{N}$ after appropriate scaling. The problem is \classNP-hard whenever $p$ and $q$ are coprime and $p \ge 3$. In terms of approximation, we present positive and negative results for general $p$ and $q$. We show that our algorithm obtains an approximation ratio of at most 1.0345. Moreover, we prove that the problem is \classAPX-hard, with a lower bound of $1.000015$ achieved at $p/q = 4/5$.

Links

Export

BibTeX

@online{Akrami2107.08965, TITLE = {Maximizing Nash Social Welfare in 2-Value Instances}, AUTHOR = {Akrami, Hannaneh and Ray Chaudhury, Bhaskar and Hoefer, Martin and Mehlhorn, Kurt and Schmalhofer, Marco and Shahkarami, Golnoosh and Varricchio, Giovanna and Vermande, Quentin and van Wijland, Ernest}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2107.08965}, EPRINT = {2107.08965}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We consider the problem of maximizing the Nash social welfare when allocating a set $\mathcal{G}$ of indivisible goods to a set $\mathcal{N}$ of agents. We study instances, in which all agents have 2-value additive valuations: The value of every agent $i \in \mathcal{N}$ for every good $j \in \mathcal{G}$ is $v_{ij} \in \{p,q\}$, for $p,q \in \mathbb{N}$, $p \le q$. Maybe surprisingly, we design an algorithm to compute an optimal allocation in polynomial time if $p$ divides $q$, i.e., when $p=1$ and $q \in \mathbb{N}$ after appropriate scaling. The problem is \classNP-hard whenever $p$ and $q$ are coprime and $p \ge 3$. In terms of approximation, we present positive and negative results for general $p$ and $q$. We show that our algorithm obtains an approximation ratio of at most 1.0345. Moreover, we prove that the problem is \classAPX-hard, with a lower bound of $1.000015$ achieved at $p/q = 4/5$. }, }

Endnote

%0 Report %A Akrami, Hannaneh %A Ray Chaudhury, Bhaskar %A Hoefer, Martin %A Mehlhorn, Kurt %A Schmalhofer, Marco %A Shahkarami, Golnoosh %A Varricchio, Giovanna %A Vermande, Quentin %A van Wijland, Ernest %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Maximizing Nash Social Welfare in 2-Value Instances : %G eng %U http://hdl.handle.net/21.11116/0000-000C-2000-F %U https://arxiv.org/abs/2107.08965 %D 2021 %X We consider the problem of maximizing the Nash social welfare when allocating a set $\mathcal{G}$ of indivisible goods to a set $\mathcal{N}$ of agents. We study instances, in which all agents have 2-value additive valuations: The value of every agent $i \in \mathcal{N}$ for every good $j \in \mathcal{G}$ is $v_{ij} \in \{p,q\}$, for $p,q \in \mathbb{N}$, $p \le q$. Maybe surprisingly, we design an algorithm to compute an optimal allocation in polynomial time if $p$ divides $q$, i.e., when $p=1$ and $q \in \mathbb{N}$ after appropriate scaling. The problem is \classNP-hard whenever $p$ and $q$ are coprime and $p \ge 3$. In terms of approximation, we present positive and negative results for general $p$ and $q$. We show that our algorithm obtains an approximation ratio of at most 1.0345. Moreover, we prove that the problem is \classAPX-hard, with a lower bound of $1.000015$ achieved at $p/q = 4/5$. %K Computer Science, Computer Science and Game Theory, cs.GT

[2]

H. Akrami, B. Ray Chaudhury, K. Mehlhorn, G. Shahkarami, and Q. Vermande, “Nash Social Welfare for 2-value Instances,” 2021. [Online]. Available: https://arxiv.org/abs/2106.14816. (arXiv: 2106.14816)

Abstract

We study the problem of allocating a set of indivisible goods among agents with 2-value additive valuations. Our goal is to find an allocation with maximum Nash social welfare, i.e., the geometric mean of the valuations of the agents. We give a polynomial-time algorithm to find a Nash social welfare maximizing allocation when the valuation functions are integrally 2-valued, i.e., each agent has a value either $1$ or $p$ for each good, for some positive integer $p$. We then extend our algorithm to find a better approximation factor for general 2-value instances.

Links

Export

BibTeX

@online{Akrami2106.14816, TITLE = {Nash Social Welfare for 2-value Instances}, AUTHOR = {Akrami, Hannaneh and Ray Chaudhury, Bhaskar and Mehlhorn, Kurt and Shahkarami, Golnoosh and Vermande, Quentin}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2106.14816}, EPRINT = {2106.14816}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We study the problem of allocating a set of indivisible goods among agents with 2-value additive valuations. Our goal is to find an allocation with maximum Nash social welfare, i.e., the geometric mean of the valuations of the agents. We give a polynomial-time algorithm to find a Nash social welfare maximizing allocation when the valuation functions are integrally 2-valued, i.e., each agent has a value either $1$ or $p$ for each good, for some positive integer $p$. We then extend our algorithm to find a better approximation factor for general 2-value instances. }, }

Endnote

%0 Report %A Akrami, Hannaneh %A Ray Chaudhury, Bhaskar %A Mehlhorn, Kurt %A Shahkarami, Golnoosh %A Vermande, Quentin %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Nash Social Welfare for 2-value Instances : %G eng %U http://hdl.handle.net/21.11116/0000-0008-DB45-4 %U https://arxiv.org/abs/2106.14816 %D 2021 %X We study the problem of allocating a set of indivisible goods among agents with 2-value additive valuations. Our goal is to find an allocation with maximum Nash social welfare, i.e., the geometric mean of the valuations of the agents. We give a polynomial-time algorithm to find a Nash social welfare maximizing allocation when the valuation functions are integrally 2-valued, i.e., each agent has a value either $1$ or $p$ for each good, for some positive integer $p$. We then extend our algorithm to find a better approximation factor for general 2-value instances. %K Computer Science, Computer Science and Game Theory, cs.GT

[3]

G. Amanatidis and P. Kleer, “Approximate Sampling and Counting of Graphs with Near-Regular Degree Intervals,” 2021. [Online]. Available: https://arxiv.org/abs/2110.09068. (arXiv: 2110.09068)

Abstract

The approximate uniform sampling of graphs with a given degree sequence is a well-known, extensively studied problem in theoretical computer science and has significant applications, e.g., in the analysis of social networks. In this work we study an extension of the problem, where degree intervals are specified rather than a single degree sequence. We are interested in sampling and counting graphs whose degree sequences satisfy the degree interval constraints. A natural scenario where this problem arises is in hypothesis testing on social networks that are only partially observed. In this work, we provide the first fully polynomial almost uniform sampler (FPAUS) as well as the first fully polynomial randomized approximation scheme (FPRAS) for sampling and counting, respectively, graphs with near-regular degree intervals, in which every node $i$ has a degree from an interval not too far away from a given $d \in \N$. In order to design our FPAUS, we rely on various state-of-the-art tools from Markov chain theory and combinatorics. In particular, we provide the first non-trivial algorithmic application of a breakthrough result of Liebenau and Wormald (2017) regarding an asymptotic formula for the number of graphs with a given near-regular degree sequence. Furthermore, we also make use of the recent breakthrough of Anari et al. (2019) on sampling a base of a matroid under a strongly log-concave probability distribution. As a more direct approach, we also study a natural Markov chain recently introduced by Rechner, Strowick and M\"uller-Hannemann (2018), based on three simple local operations: Switches, hinge flips, and additions/deletions of a single edge. We obtain the first theoretical results for this Markov chain by showing it is rapidly mixing for the case of near-regular degree intervals of size at most one.

Links

Export

BibTeX

@online{Amanatidis_2110.09068, TITLE = {Approximate Sampling and Counting of Graphs with Near-Regular Degree Intervals}, AUTHOR = {Amanatidis, Georgios and Kleer, Pieter}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2110.09068}, EPRINT = {2110.09068}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {The approximate uniform sampling of graphs with a given degree sequence is a well-known, extensively studied problem in theoretical computer science and has significant applications, e.g., in the analysis of social networks. In this work we study an extension of the problem, where degree intervals are specified rather than a single degree sequence. We are interested in sampling and counting graphs whose degree sequences satisfy the degree interval constraints. A natural scenario where this problem arises is in hypothesis testing on social networks that are only partially observed. In this work, we provide the first fully polynomial almost uniform sampler (FPAUS) as well as the first fully polynomial randomized approximation scheme (FPRAS) for sampling and counting, respectively, graphs with near-regular degree intervals, in which every node $i$ has a degree from an interval not too far away from a given $d \in \N$. In order to design our FPAUS, we rely on various state-of-the-art tools from Markov chain theory and combinatorics. In particular, we provide the first non-trivial algorithmic application of a breakthrough result of Liebenau and Wormald (2017) regarding an asymptotic formula for the number of graphs with a given near-regular degree sequence. Furthermore, we also make use of the recent breakthrough of Anari et al. (2019) on sampling a base of a matroid under a strongly log-concave probability distribution. As a more direct approach, we also study a natural Markov chain recently introduced by Rechner, Strowick and M\"uller-Hannemann (2018), based on three simple local operations: Switches, hinge flips, and additions/deletions of a single edge. We obtain the first theoretical results for this Markov chain by showing it is rapidly mixing for the case of near-regular degree intervals of size at most one. }, }

Endnote

%0 Report %A Amanatidis, Georgios %A Kleer, Pieter %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Approximate Sampling and Counting of Graphs with Near-Regular Degree Intervals : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B839-8 %U https://arxiv.org/abs/2110.09068 %D 2021 %X The approximate uniform sampling of graphs with a given degree sequence is a well-known, extensively studied problem in theoretical computer science and has significant applications, e.g., in the analysis of social networks. In this work we study an extension of the problem, where degree intervals are specified rather than a single degree sequence. We are interested in sampling and counting graphs whose degree sequences satisfy the degree interval constraints. A natural scenario where this problem arises is in hypothesis testing on social networks that are only partially observed. In this work, we provide the first fully polynomial almost uniform sampler (FPAUS) as well as the first fully polynomial randomized approximation scheme (FPRAS) for sampling and counting, respectively, graphs with near-regular degree intervals, in which every node $i$ has a degree from an interval not too far away from a given $d \in \N$. In order to design our FPAUS, we rely on various state-of-the-art tools from Markov chain theory and combinatorics. In particular, we provide the first non-trivial algorithmic application of a breakthrough result of Liebenau and Wormald (2017) regarding an asymptotic formula for the number of graphs with a given near-regular degree sequence. Furthermore, we also make use of the recent breakthrough of Anari et al. (2019) on sampling a base of a matroid under a strongly log-concave probability distribution. As a more direct approach, we also study a natural Markov chain recently introduced by Rechner, Strowick and M\"uller-Hannemann (2018), based on three simple local operations: Switches, hinge flips, and additions/deletions of a single edge. We obtain the first theoretical results for this Markov chain by showing it is rapidly mixing for the case of near-regular degree intervals of size at most one. %K Computer Science, Discrete Mathematics, cs.DM,Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Combinatorics, math.CO

[4]

I. Anagnostides, T. Gouleakis, and A. Marashian, “Robust Learning under Strong Noise via SQs,” in Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS 2021), Virtual Conference, 2021.

Links

Export

BibTeX

@inproceedings{Anagnostides_AISTATS2020, TITLE = {Robust Learning under Strong Noise via {SQs}}, AUTHOR = {Anagnostides, Ioannis and Gouleakis, Themis and Marashian, Ali}, LANGUAGE = {eng}, URL = {https://proceedings.mlr.press/v130/anagnostides21a.html}, PUBLISHER = {PMLR}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS 2021)}, EDITOR = {Banerjee, Arindam and Fukumizu, Kenli}, PAGES = {3808--3816}, SERIES = {Proceedings of the Machine Learning Research}, VOLUME = {130}, ADDRESS = {Virtual Conference}, }

Endnote

%0 Conference Proceedings %A Anagnostides, Ioannis %A Gouleakis, Themis %A Marashian, Ali %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Robust Learning under Strong Noise via SQs : %G eng %U http://hdl.handle.net/21.11116/0000-0007-DBCD-C %U https://proceedings.mlr.press/v130/anagnostides21a.html %D 2021 %B 24th International Conference on Artificial Intelligence and Statistics %Z date of event: 2021-04-13 - 2021-04-15 %C Virtual Conference %B Proceedings of the 24th International Conference on Artificial Intelligence and Statistics %E Banerjee, Arindam; Fukumizu, Kenli %P 3808 - 3816 %I PMLR %B Proceedings of the Machine Learning Research %N 130

[5]

I. Anagnostides and T. Gouleakis, “Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model,” in 35th International Symposium on Distributed Computing (DISC 2021), Freiburg, Germany (Virtual Conference), 2021.

Links

Export

BibTeX

@inproceedings{Anagnostides_DISC21, TITLE = {Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model}, AUTHOR = {Anagnostides, Ioannis and Gouleakis, Themis}, LANGUAGE = {eng}, ISSN = {1868-8969}, ISBN = {978-3-95977-210-5}, URL = {urn:nbn:de:0030-drops-148077}, DOI = {10.4230/LIPIcs.DISC.2021.5}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {35th International Symposium on Distributed Computing (DISC 2021)}, EDITOR = {Gilbert, Seth}, PAGES = {1--19}, EID = {5}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {209}, ADDRESS = {Freiburg, Germany (Virtual Conference)}, }

Endnote

%0 Conference Proceedings %A Anagnostides, Ioannis %A Gouleakis, Themis %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model : %G eng %U http://hdl.handle.net/21.11116/0000-000C-7306-C %R 10.4230/LIPIcs.DISC.2021.5 %U urn:nbn:de:0030-drops-148077 %D 2021 %B 35th International Symposium on Distributed Computing %Z date of event: 2021-10-04 - 2021-10-08 %C Freiburg, Germany (Virtual Conference) %B 35th International Symposium on Distributed Computing %E Gilbert, Seth %P 1 - 19 %Z sequence number: 5 %I Schloss Dagstuhl %@ 978-3-95977-210-5 %B Leibniz International Proceedings in Informatics %N 209 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2021/14807/https://creativecommons.org/licenses/by/4.0/legalcode

[6]

I. Anagnostides, C. Lenzen, B. Haeupler, G. Zuzic, and T. Gouleakis, “Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts,” 2021. [Online]. Available: https://arxiv.org/abs/2109.05151. (arXiv: 2109.05151)

Abstract

In this work we refine the analysis of the distributed Laplacian solver recently established by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS '21), via the Ghaffari-Haeupler framework (SODA '16) of low-congestion shortcuts. Specifically, if $\epsilon > 0$ represents the error of the solver, we derive two main results. First, for any $n$-node graph $G$ with hop-diameter $D$ and treewidth bounded by $k$, we show the existence of a Laplacian solver with round complexity $O(n^{o(1)}kD \log(1/\epsilon))$ in the CONGEST model. For graphs with bounded treewidth this circumvents the notorious $\Omega(\sqrt{n})$ lower bound for "global" problems in general graphs. Moreover, following a recent line of work in distributed algorithms, we consider a hybrid communication model which enhances CONGEST with very limited global power in the form of the recently introduced node-capacitated clique. In this model, we show the existence of a Laplacian solver with round complexity $O(n^{o(1)} \log(1/\epsilon))$. The unifying thread of these results is an application of accelerated distributed algorithms for a congested variant of the standard part-wise aggregation problem that we introduce. This primitive constitutes the primary building block for simulating "local" operations on low-congestion minors, and we believe that this framework could be more generally applicable.

Links

Export

BibTeX

@online{Anagnostides_2109.05151, TITLE = {Almost Universally Optimal Distributed {L}aplacian Solvers via Low-Congestion Shortcuts}, AUTHOR = {Anagnostides, Ioannis and Lenzen, Christoph and Haeupler, Bernhard and Zuzic, Goran and Gouleakis, Themis}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2109.05151}, EPRINT = {2109.05151}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {In this work we refine the analysis of the distributed Laplacian solver recently established by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS '21), via the Ghaffari-Haeupler framework (SODA '16) of low-congestion shortcuts. Specifically, if $\epsilon > 0$ represents the error of the solver, we derive two main results. First, for any $n$-node graph $G$ with hop-diameter $D$ and treewidth bounded by $k$, we show the existence of a Laplacian solver with round complexity $O(n^{o(1)}kD \log(1/\epsilon))$ in the CONGEST model. For graphs with bounded treewidth this circumvents the notorious $\Omega(\sqrt{n})$ lower bound for "global" problems in general graphs. Moreover, following a recent line of work in distributed algorithms, we consider a hybrid communication model which enhances CONGEST with very limited global power in the form of the recently introduced node-capacitated clique. In this model, we show the existence of a Laplacian solver with round complexity $O(n^{o(1)} \log(1/\epsilon))$. The unifying thread of these results is an application of accelerated distributed algorithms for a congested variant of the standard part-wise aggregation problem that we introduce. This primitive constitutes the primary building block for simulating "local" operations on low-congestion minors, and we believe that this framework could be more generally applicable. }, }

Endnote

%0 Report %A Anagnostides, Ioannis %A Lenzen, Christoph %A Haeupler, Bernhard %A Zuzic, Goran %A Gouleakis, Themis %+ External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B83F-2 %U https://arxiv.org/abs/2109.05151 %D 2021 %X In this work we refine the analysis of the distributed Laplacian solver recently established by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS '21), via the Ghaffari-Haeupler framework (SODA '16) of low-congestion shortcuts. Specifically, if $\epsilon > 0$ represents the error of the solver, we derive two main results. First, for any $n$-node graph $G$ with hop-diameter $D$ and treewidth bounded by $k$, we show the existence of a Laplacian solver with round complexity $O(n^{o(1)}kD \log(1/\epsilon))$ in the CONGEST model. For graphs with bounded treewidth this circumvents the notorious $\Omega(\sqrt{n})$ lower bound for "global" problems in general graphs. Moreover, following a recent line of work in distributed algorithms, we consider a hybrid communication model which enhances CONGEST with very limited global power in the form of the recently introduced node-capacitated clique. In this model, we show the existence of a Laplacian solver with round complexity $O(n^{o(1)} \log(1/\epsilon))$. The unifying thread of these results is an application of accelerated distributed algorithms for a congested variant of the standard part-wise aggregation problem that we introduce. This primitive constitutes the primary building block for simulating "local" operations on low-congestion minors, and we believe that this framework could be more generally applicable. %K Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC

[7]

A. Antoniadis, R. Hoeksma, S. Kisfaludi-Bak, and K. Schewior, “Online Search for a Hyperplane in High-Dimensional Euclidean Space,” 2021. [Online]. Available: https://arxiv.org/abs/2109.04340. (arXiv: 2109.04340)

Abstract

We consider the online search problem in which a server starting at the origin of a $d$-dimensional Euclidean space has to find an arbitrary hyperplane. The best-possible competitive ratio and the length of the shortest curve from which each point on the $d$-dimensional unit sphere can be seen are within a constant factor of each other. We show that this length is in $\Omega(d)\cap O(d^{3/2})$.

Links

Export

BibTeX

@online{Antoniadis_2109.04340, TITLE = {Online Search for a Hyperplane in High-Dimensional Euclidean Space}, AUTHOR = {Antoniadis, Antonios and Hoeksma, Ruben and Kisfaludi-Bak, S{\'a}ndor and Schewior, Kevin}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2109.04340}, EPRINT = {2109.04340}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We consider the online search problem in which a server starting at the origin of a $d$-dimensional Euclidean space has to find an arbitrary hyperplane. The best-possible competitive ratio and the length of the shortest curve from which each point on the $d$-dimensional unit sphere can be seen are within a constant factor of each other. We show that this length is in $\Omega(d)\cap O(d^{3/2})$. }, }

Endnote

%0 Report %A Antoniadis, Antonios %A Hoeksma, Ruben %A Kisfaludi-Bak, Sándor %A Schewior, Kevin %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Online Search for a Hyperplane in High-Dimensional Euclidean Space : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B814-1 %U https://arxiv.org/abs/2109.04340 %D 2021 %X We consider the online search problem in which a server starting at the origin of a $d$-dimensional Euclidean space has to find an arbitrary hyperplane. The best-possible competitive ratio and the length of the shortest curve from which each point on the $d$-dimensional unit sphere can be seen are within a constant factor of each other. We show that this length is in $\Omega(d)\cap O(d^{3/2})$. %K Computer Science, Computational Geometry, cs.CG,Computer Science, Data Structures and Algorithms, cs.DS

[8]

K. Axiotis, A. Backurs, K. Bringmann, C. Jin, V. Nakos, C. Tzamos, and H. Wu, “Fast and Simple Modular Subset Sum,” in Symposium on Simplicity in Algorithms (SOSA 2021), Alexandria, VA, USA (Virtual Conference), 2021.

Links

Export

BibTeX

@inproceedings{Axiotis_SOSA2021, TITLE = {Fast and Simple Modular Subset Sum}, AUTHOR = {Axiotis, Kyriakos and Backurs, Arturs and Bringmann, Karl and Jin, Ce and Nakos, Vasileios and Tzamos, Christos and Wu, Hongxun}, LANGUAGE = {eng}, ISBN = {978-1-61197-649-6}, DOI = {10.1137/1.9781611976496.6}, PUBLISHER = {SIAM}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {Symposium on Simplicity in Algorithms (SOSA 2021)}, EDITOR = {King, Valerie and Viet Le, Hung}, PAGES = {57--67}, ADDRESS = {Alexandria, VA, USA (Virtual Conference)}, }

Endnote

%0 Conference Proceedings %A Axiotis, Kyriakos %A Backurs, Arturs %A Bringmann, Karl %A Jin, Ce %A Nakos, Vasileios %A Tzamos, Christos %A Wu, Hongxun %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Fast and Simple Modular Subset Sum : %G eng %U http://hdl.handle.net/21.11116/0000-0007-56CF-0 %R 10.1137/1.9781611976496.6 %D 2021 %B SIAM Symposium on Simplicity in Algorithms %Z date of event: 2021-01-11 - 2021-01-12 %C Alexandria, VA, USA (Virtual Conference) %B Symposium on Simplicity in Algorithms %E King, Valerie; Viet Le, Hung %P 57 - 67 %I SIAM %@ 978-1-61197-649-6

[9]

R. Becker, S. Forster, A. Karrenbauer, and C. Lenzen, “Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models,” SIAM Journal on Computing, vol. 50, no. 3, 2021.

Links

Export

BibTeX

@article{Becker2021, TITLE = {Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models}, AUTHOR = {Becker, Ruben and Forster, Sebastian and Karrenbauer, Andreas and Lenzen, Christoph}, LANGUAGE = {eng}, ISSN = {0097-5397}, DOI = {10.1137/19M1286955}, PUBLISHER = {SIAM}, ADDRESS = {Philadelphia}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, DATE = {2021}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {50}, NUMBER = {3}, PAGES = {815--856}, }

Endnote

%0 Journal Article %A Becker, Ruben %A Forster, Sebastian %A Karrenbauer, Andreas %A Lenzen, Christoph %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E543-A %R 10.1137/19M1286955 %7 2021 %D 2021 %J SIAM Journal on Computing %V 50 %N 3 %& 815 %P 815 - 856 %I SIAM %C Philadelphia %@ false

[10]

B. A. Berendsohn, L. Kozma, and D. Marx, “Finding and Counting Permutations via CSPs,” Algorithmica, vol. 83, 2021.

Links

Export

BibTeX

@article{berendsohn2021, TITLE = {Finding and Counting Permutations via {CSPs}}, AUTHOR = {Berendsohn, Benjamin Aram and Kozma, L{\'a}szl{\'o} and Marx, D{\'a}niel}, LANGUAGE = {eng}, ISSN = {0178-4617}, DOI = {10.1007/s00453-021-00812-z}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, JOURNAL = {Algorithmica}, VOLUME = {83}, PAGES = {2552--2577}, }

Endnote

%0 Journal Article %A Berendsohn, Benjamin Aram %A Kozma, László %A Marx, Dániel %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Finding and Counting Permutations via CSPs : %G eng %U http://hdl.handle.net/21.11116/0000-0008-3403-A %R 10.1007/s00453-021-00812-z %7 2021 %D 2021 %J Algorithmica %V 83 %& 2552 %P 2552 - 2577 %I Springer %C New York, NY %@ false

[11]

K. Bringmann and J. Slusallek, “Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal,” 2021. [Online]. Available: https://arxiv.org/abs/2105.05062. (arXiv: 2105.05062)

Abstract

The Subgraph Isomorphism problem is of considerable importance in computer science. We examine the problem when the pattern graph H is of bounded treewidth, as occurs in a variety of applications. This problem has a well-known algorithm via color-coding that runs in time $O(n^{tw(H)+1})$ [Alon, Yuster, Zwick'95], where $n$ is the number of vertices of the host graph $G$. While there are pattern graphs known for which Subgraph Isomorphism can be solved in an improved running time of $O(n^{tw(H)+1-\varepsilon})$ or even faster (e.g. for $k$-cliques), it is not known whether such improvements are possible for all patterns. The only known lower bound rules out time $n^{o(tw(H) / \log(tw(H)))}$ for any class of patterns of unbounded treewidth assuming the Exponential Time Hypothesis [Marx'07]. In this paper, we demonstrate the existence of maximally hard pattern graphs $H$ that require time $n^{tw(H)+1-o(1)}$. Specifically, under the Strong Exponential Time Hypothesis (SETH), a standard assumption from fine-grained complexity theory, we prove the following asymptotic statement for large treewidth $t$: For any $\varepsilon > 0$ there exists $t \ge 3$ and a pattern graph $H$ of treewidth $t$ such that Subgraph Isomorphism on pattern $H$ has no algorithm running in time $O(n^{t+1-\varepsilon})$. Under the more recent 3-uniform Hyperclique hypothesis, we even obtain tight lower bounds for each specific treewidth $t \ge 3$: For any $t \ge 3$ there exists a pattern graph $H$ of treewidth $t$ such that for any $\varepsilon>0$ Subgraph Isomorphism on pattern $H$ has no algorithm running in time $O(n^{t+1-\varepsilon})$. In addition to these main results, we explore (1) colored and uncolored problem variants (and why they are equivalent for most cases), (2) Subgraph Isomorphism for $tw < 3$, (3) Subgraph Isomorphism parameterized by pathwidth, and (4) a weighted problem variant.

Links

Export

BibTeX

@online{Bringmann_2105.05062, TITLE = {Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal}, AUTHOR = {Bringmann, Karl and Slusallek, Jasper}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2105.05062}, EPRINT = {2105.05062}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {The Subgraph Isomorphism problem is of considerable importance in computer science. We examine the problem when the pattern graph H is of bounded treewidth, as occurs in a variety of applications. This problem has a well-known algorithm via color-coding that runs in time $O(n^{tw(H)+1})$ [Alon, Yuster, Zwick'95], where $n$ is the number of vertices of the host graph $G$. While there are pattern graphs known for which Subgraph Isomorphism can be solved in an improved running time of $O(n^{tw(H)+1-\varepsilon})$ or even faster (e.g. for $k$-cliques), it is not known whether such improvements are possible for all patterns. The only known lower bound rules out time $n^{o(tw(H) / \log(tw(H)))}$ for any class of patterns of unbounded treewidth assuming the Exponential Time Hypothesis [Marx'07]. In this paper, we demonstrate the existence of maximally hard pattern graphs $H$ that require time $n^{tw(H)+1-o(1)}$. Specifically, under the Strong Exponential Time Hypothesis (SETH), a standard assumption from fine-grained complexity theory, we prove the following asymptotic statement for large treewidth $t$: For any $\varepsilon > 0$ there exists $t \ge 3$ and a pattern graph $H$ of treewidth $t$ such that Subgraph Isomorphism on pattern $H$ has no algorithm running in time $O(n^{t+1-\varepsilon})$. Under the more recent 3-uniform Hyperclique hypothesis, we even obtain tight lower bounds for each specific treewidth $t \ge 3$: For any $t \ge 3$ there exists a pattern graph $H$ of treewidth $t$ such that for any $\varepsilon>0$ Subgraph Isomorphism on pattern $H$ has no algorithm running in time $O(n^{t+1-\varepsilon})$. In addition to these main results, we explore (1) colored and uncolored problem variants (and why they are equivalent for most cases), (2) Subgraph Isomorphism for $tw < 3$, (3) Subgraph Isomorphism parameterized by pathwidth, and (4) a weighted problem variant. }, }

Endnote

%0 Report %A Bringmann, Karl %A Slusallek, Jasper %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E25F-F %U https://arxiv.org/abs/2105.05062 %D 2021 %X The Subgraph Isomorphism problem is of considerable importance in computer science. We examine the problem when the pattern graph H is of bounded treewidth, as occurs in a variety of applications. This problem has a well-known algorithm via color-coding that runs in time $O(n^{tw(H)+1})$ [Alon, Yuster, Zwick'95], where $n$ is the number of vertices of the host graph $G$. While there are pattern graphs known for which Subgraph Isomorphism can be solved in an improved running time of $O(n^{tw(H)+1-\varepsilon})$ or even faster (e.g. for $k$-cliques), it is not known whether such improvements are possible for all patterns. The only known lower bound rules out time $n^{o(tw(H) / \log(tw(H)))}$ for any class of patterns of unbounded treewidth assuming the Exponential Time Hypothesis [Marx'07]. In this paper, we demonstrate the existence of maximally hard pattern graphs $H$ that require time $n^{tw(H)+1-o(1)}$. Specifically, under the Strong Exponential Time Hypothesis (SETH), a standard assumption from fine-grained complexity theory, we prove the following asymptotic statement for large treewidth $t$: For any $\varepsilon > 0$ there exists $t \ge 3$ and a pattern graph $H$ of treewidth $t$ such that Subgraph Isomorphism on pattern $H$ has no algorithm running in time $O(n^{t+1-\varepsilon})$. Under the more recent 3-uniform Hyperclique hypothesis, we even obtain tight lower bounds for each specific treewidth $t \ge 3$: For any $t \ge 3$ there exists a pattern graph $H$ of treewidth $t$ such that for any $\varepsilon>0$ Subgraph Isomorphism on pattern $H$ has no algorithm running in time $O(n^{t+1-\varepsilon})$. In addition to these main results, we explore (1) colored and uncolored problem variants (and why they are equivalent for most cases), (2) Subgraph Isomorphism for $tw < 3$, (3) Subgraph Isomorphism parameterized by pathwidth, and (4) a weighted problem variant. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computational Complexity, cs.CC,

[12]

K. Bringmann, N. Fischer, and V. Nakos, “Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution,” in STOC ’21, 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual, Italy, 2021.

Links

Export

BibTeX

@inproceedings{Bringmann_STOC2021, TITLE = {Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution}, AUTHOR = {Bringmann, Karl and Fischer, Nick and Nakos, Vasileios}, LANGUAGE = {eng}, ISBN = {9781450380539}, DOI = {10.1145/3406325.3451090}, PUBLISHER = {ACM}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {STOC '21, 53rd Annual ACM SIGACT Symposium on Theory of Computing}, EDITOR = {Khuller, Samir and Vassilevska Williams, Virginia}, PAGES = {1711--1724}, ADDRESS = {Virtual, Italy}, }

Endnote

%0 Conference Proceedings %A Bringmann, Karl %A Fischer, Nick %A Nakos, Vasileios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E23F-3 %R 10.1145/3406325.3451090 %D 2021 %B 53rd Annual ACM SIGACT Symposium on Theory of Computing %Z date of event: 2021-06-21 - 2021-06-25 %C Virtual, Italy %B STOC '21 %E Khuller, Samir; Vassilevska Williams, Virginia %P 1711 - 1724 %I ACM %@ 9781450380539

[13]

K. Bringmann, M. Künnemann, and A. Nusser, “Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance,” Journal of Computational Geometry, vol. 12, no. 1, 2021.

Links

Export

BibTeX

@article{Bringmann21, TITLE = {Walking the Dog Fast in Practice: {A}lgorithm Engineering of the {F}r\'{e}chet Distance}, AUTHOR = {Bringmann, Karl and K{\"u}nnemann, Marvin and Nusser, Andr{\'e}}, LANGUAGE = {eng}, DOI = {10.20382/jocg.v12i1a4}, PUBLISHER = {JoCG.org}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, JOURNAL = {Journal of Computational Geometry}, VOLUME = {12}, NUMBER = {1}, PAGES = {70--108}, }

Endnote

%0 Journal Article %A Bringmann, Karl %A Künnemann, Marvin %A Nusser, André %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1F8A-7 %R 10.20382/jocg.v12i1a4 %7 2021 %D 2021 %J Journal of Computational Geometry %V 12 %N 1 %& 70 %P 70 - 108 %I JoCG.org

[14]

K. Bringmann, “Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry,” 2021. [Online]. Available: https://arxiv.org/abs/2110.10283. (arXiv: 2110.10283)

Abstract

Fine-grained complexity theory is the area of theoretical computer science that proves conditional lower bounds based on the Strong Exponential Time Hypothesis and similar conjectures. This area has been thriving in the last decade, leading to conditionally best-possible algorithms for a wide variety of problems on graphs, strings, numbers etc. This article is an introduction to fine-grained lower bounds in computational geometry, with a focus on lower bounds for polynomial-time problems based on the Orthogonal Vectors Hypothesis. Specifically, we discuss conditional lower bounds for nearest neighbor search under the Euclidean distance and Fr\'echet distance.

Links

Export

BibTeX

@online{Bringmann2110.10283, TITLE = {Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry}, AUTHOR = {Bringmann, Karl}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2110.10283}, EPRINT = {2110.10283}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {Fine-grained complexity theory is the area of theoretical computer science that proves conditional lower bounds based on the Strong Exponential Time Hypothesis and similar conjectures. This area has been thriving in the last decade, leading to conditionally best-possible algorithms for a wide variety of problems on graphs, strings, numbers etc. This article is an introduction to fine-grained lower bounds in computational geometry, with a focus on lower bounds for polynomial-time problems based on the Orthogonal Vectors Hypothesis. Specifically, we discuss conditional lower bounds for nearest neighbor search under the Euclidean distance and Fr\'echet distance. }, }

Endnote

%0 Report %A Bringmann, Karl %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B42E-9 %U https://arxiv.org/abs/2110.10283 %D 2021 %X Fine-grained complexity theory is the area of theoretical computer science that proves conditional lower bounds based on the Strong Exponential Time Hypothesis and similar conjectures. This area has been thriving in the last decade, leading to conditionally best-possible algorithms for a wide variety of problems on graphs, strings, numbers etc. This article is an introduction to fine-grained lower bounds in computational geometry, with a focus on lower bounds for polynomial-time problems based on the Orthogonal Vectors Hypothesis. Specifically, we discuss conditional lower bounds for nearest neighbor search under the Euclidean distance and Fr\'echet distance. %K Computer Science, Computational Geometry, cs.CG,Computer Science, Data Structures and Algorithms, cs.DS

[15]

K. Bringmann, “Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry,” in Connecting with Computability (CiE 2021), Ghent, Belgium (Virtual Event), 2021.

Links

Export

BibTeX

@inproceedings{Bringmann_CiE21, TITLE = {Fine-Grained Complexity Theory: {C}onditional Lower Bounds for Computational Geometry}, AUTHOR = {Bringmann, Karl}, LANGUAGE = {eng}, ISBN = {978-3-030-80048-2}, DOI = {10.1007/978-3-030-80049-9_6}, PUBLISHER = {Springer}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {Connecting with Computability (CiE 2021)}, EDITOR = {De Mol, Liesbeth and Weiermann, Andreas and Manea, Florin and Fern{\'a}ndez-Duque, David}, PAGES = {60--70}, SERIES = {Lecture Notes in Computer Science}, VOLUME = {12813}, ADDRESS = {Ghent, Belgium (Virtual Event)}, }

Endnote

%0 Conference Proceedings %A Bringmann, Karl %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B428-F %R 10.1007/978-3-030-80049-9_6 %D 2021 %B 17th Conference on Computability in Europe %Z date of event: 2021-07-05 - 2021-07-09 %C Ghent, Belgium (Virtual Event) %B Connecting with Computability %E De Mol, Liesbeth; Weiermann, Andreas; Manea, Florin; Fernández-Duque, David %P 60 - 70 %I Springer %@ 978-3-030-80048-2 %B Lecture Notes in Computer Science %N 12813

[16]

K. Bringmann and A. Nusser, “Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation,” 2021. [Online]. Available: https://arxiv.org/abs/2101.07696. (arXiv: 2101.07696)

Abstract

Computing the similarity of two point sets is a ubiquitous task in medical imaging, geometric shape comparison, trajectory analysis, and many more settings. Arguably the most basic distance measure for this task is the Hausdorff distance, which assigns to each point from one set the closest point in the other set and then evaluates the maximum distance of any assigned pair. A drawback is that this distance measure is not translational invariant, that is, comparing two objects just according to their shape while disregarding their position in space is impossible. Fortunately, there is a canonical translational invariant version, the Hausdorff distance under translation, which minimizes the Hausdorff distance over all translations of one of the point sets. For point sets of size $n$ and $m$, the Hausdorff distance under translation can be computed in time $\tilde O(nm)$ for the $L_1$ and $L_\infty$ norm [Chew, Kedem SWAT'92] and $\tilde O(nm (n+m))$ for the $L_2$ norm [Huttenlocher, Kedem, Sharir DCG'93]. As these bounds have not been improved for over 25 years, in this paper we approach the Hausdorff distance under translation from the perspective of fine-grained complexity theory. We show (i) a matching lower bound of $(nm)^{1-o(1)}$ for $L_1$ and $L_\infty$ assuming the Orthogonal Vectors Hypothesis and (ii) a matching lower bound of $n^{2-o(1)}$ for $L_2$ in the imbalanced case of $m = O(1)$ assuming the 3SUM Hypothesis.

Links

Export

BibTeX

@online{Bringmann_2101.07696, TITLE = {Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation}, AUTHOR = {Bringmann, Karl and Nusser, Andr{\'e}}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2101.07696}, EPRINT = {2101.07696}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {Computing the similarity of two point sets is a ubiquitous task in medical imaging, geometric shape comparison, trajectory analysis, and many more settings. Arguably the most basic distance measure for this task is the Hausdorff distance, which assigns to each point from one set the closest point in the other set and then evaluates the maximum distance of any assigned pair. A drawback is that this distance measure is not translational invariant, that is, comparing two objects just according to their shape while disregarding their position in space is impossible. Fortunately, there is a canonical translational invariant version, the Hausdorff distance under translation, which minimizes the Hausdorff distance over all translations of one of the point sets. For point sets of size $n$ and $m$, the Hausdorff distance under translation can be computed in time $\tilde O(nm)$ for the $L_1$ and $L_\infty$ norm [Chew, Kedem SWAT'92] and $\tilde O(nm (n+m))$ for the $L_2$ norm [Huttenlocher, Kedem, Sharir DCG'93]. As these bounds have not been improved for over 25 years, in this paper we approach the Hausdorff distance under translation from the perspective of fine-grained complexity theory. We show (i) a matching lower bound of $(nm)^{1-o(1)}$ for $L_1$ and $L_\infty$ assuming the Orthogonal Vectors Hypothesis and (ii) a matching lower bound of $n^{2-o(1)}$ for $L_2$ in the imbalanced case of $m = O(1)$ assuming the 3SUM Hypothesis. }, }

Endnote

%0 Report %A Bringmann, Karl %A Nusser, André %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E242-E %U https://arxiv.org/abs/2101.07696 %D 2021 %X Computing the similarity of two point sets is a ubiquitous task in medical imaging, geometric shape comparison, trajectory analysis, and many more settings. Arguably the most basic distance measure for this task is the Hausdorff distance, which assigns to each point from one set the closest point in the other set and then evaluates the maximum distance of any assigned pair. A drawback is that this distance measure is not translational invariant, that is, comparing two objects just according to their shape while disregarding their position in space is impossible. Fortunately, there is a canonical translational invariant version, the Hausdorff distance under translation, which minimizes the Hausdorff distance over all translations of one of the point sets. For point sets of size $n$ and $m$, the Hausdorff distance under translation can be computed in time $\tilde O(nm)$ for the $L_1$ and $L_\infty$ norm [Chew, Kedem SWAT'92] and $\tilde O(nm (n+m))$ for the $L_2$ norm [Huttenlocher, Kedem, Sharir DCG'93]. As these bounds have not been improved for over 25 years, in this paper we approach the Hausdorff distance under translation from the perspective of fine-grained complexity theory. We show (i) a matching lower bound of $(nm)^{1-o(1)}$ for $L_1$ and $L_\infty$ assuming the Orthogonal Vectors Hypothesis and (ii) a matching lower bound of $n^{2-o(1)}$ for $L_2$ in the imbalanced case of $m = O(1)$ assuming the 3SUM Hypothesis. %K Computer Science, Computational Geometry, cs.CG,Computer Science, Computational Complexity, cs.CC

[17]

K. Bringmann and A. Nusser, “Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance under Translation,” Journal of Computational Geometry, vol. 13, no. 2, 2021.

Links

Export

BibTeX

@article{Bringmann22b, TITLE = {Translating {Hausdorff} is hard: {F}ine-grained lower bounds for {H}ausdorff distance under translation}, AUTHOR = {Bringmann, Karl and Nusser, Andr{\'e}}, LANGUAGE = {eng}, DOI = {10.20382/jocg.v13i2a3}, PUBLISHER = {JoCG.org}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, JOURNAL = {Journal of Computational Geometry}, VOLUME = {13}, NUMBER = {2}, PAGES = {30--50}, }

Endnote

%0 Journal Article %A Bringmann, Karl %A Nusser, André %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance under Translation : %G eng %U http://hdl.handle.net/21.11116/0000-000C-2690-6 %R 10.20382/jocg.v13i2a3 %7 2021 %D 2021 %J Journal of Computational Geometry %V 13 %N 2 %& 30 %P 30 - 50 %I JoCG.org

[18]

K. Bringmann and V. Nakos, “Fast n-fold Boolean Convolution via Additive Combinatorics,” 2021. [Online]. Available: https://arxiv.org/abs/2105.03968. (arXiv: 2105.03968)

Abstract

We consider the problem of computing the Boolean convolution (with wraparound) of $n$~vectors of dimension $m$, or, equivalently, the problem of computing the sumset $A_1+A_2+\ldots+A_n$ for $A_1,\ldots,A_n \subseteq \mathbb{Z}_m$. Boolean convolution formalizes the frequent task of combining two subproblems, where the whole problem has a solution of size $k$ if for some $i$ the first subproblem has a solution of size~$i$ and the second subproblem has a solution of size $k-i$. Our problem formalizes a natural generalization, namely combining solutions of $n$ subproblems subject to a modular constraint. This simultaneously generalises Modular Subset Sum and Boolean Convolution (Sumset Computation). Although nearly optimal algorithms are known for special cases of this problem, not even tiny improvements are known for the general case. We almost resolve the computational complexity of this problem, shaving essentially a factor of $n$ from the running time of previous algorithms. Specifically, we present a \emph{deterministic} algorithm running in \emph{almost} linear time with respect to the input plus output size $k$. We also present a \emph{Las Vegas} algorithm running in \emph{nearly} linear expected time with respect to the input plus output size $k$. Previously, no deterministic or randomized $o(nk)$ algorithm was known. At the heart of our approach lies a careful usage of Kneser's theorem from Additive Combinatorics, and a new deterministic almost linear output-sensitive algorithm for non-negative sparse convolution. In total, our work builds a solid toolbox that could be of independent interest.

Links

Export

BibTeX

@online{Bringmann_2105.03968, TITLE = {Fast $n$-fold {B}oolean Convolution via Additive Combinatorics}, AUTHOR = {Bringmann, Karl and Nakos, Vasileios}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2105.03968}, EPRINT = {2105.03968}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We consider the problem of computing the Boolean convolution (with wraparound) of $n$~vectors of dimension $m$, or, equivalently, the problem of computing the sumset $A_1+A_2+\ldots+A_n$ for $A_1,\ldots,A_n \subseteq \mathbb{Z}_m$. Boolean convolution formalizes the frequent task of combining two subproblems, where the whole problem has a solution of size $k$ if for some $i$ the first subproblem has a solution of size~$i$ and the second subproblem has a solution of size $k-i$. Our problem formalizes a natural generalization, namely combining solutions of $n$ subproblems subject to a modular constraint. This simultaneously generalises Modular Subset Sum and Boolean Convolution (Sumset Computation). Although nearly optimal algorithms are known for special cases of this problem, not even tiny improvements are known for the general case. We almost resolve the computational complexity of this problem, shaving essentially a factor of $n$ from the running time of previous algorithms. Specifically, we present a \emph{deterministic} algorithm running in \emph{almost} linear time with respect to the input plus output size $k$. We also present a \emph{Las Vegas} algorithm running in \emph{nearly} linear expected time with respect to the input plus output size $k$. Previously, no deterministic or randomized $o(nk)$ algorithm was known. At the heart of our approach lies a careful usage of Kneser's theorem from Additive Combinatorics, and a new deterministic almost linear output-sensitive algorithm for non-negative sparse convolution. In total, our work builds a solid toolbox that could be of independent interest. }, }

Endnote

%0 Report %A Bringmann, Karl %A Nakos, Vasileios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fast n-fold Boolean Convolution via Additive Combinatorics : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E25B-3 %U https://arxiv.org/abs/2105.03968 %D 2021 %X We consider the problem of computing the Boolean convolution (with wraparound) of $n$~vectors of dimension $m$, or, equivalently, the problem of computing the sumset $A_1+A_2+\ldots+A_n$ for $A_1,\ldots,A_n \subseteq \mathbb{Z}_m$. Boolean convolution formalizes the frequent task of combining two subproblems, where the whole problem has a solution of size $k$ if for some $i$ the first subproblem has a solution of size~$i$ and the second subproblem has a solution of size $k-i$. Our problem formalizes a natural generalization, namely combining solutions of $n$ subproblems subject to a modular constraint. This simultaneously generalises Modular Subset Sum and Boolean Convolution (Sumset Computation). Although nearly optimal algorithms are known for special cases of this problem, not even tiny improvements are known for the general case. We almost resolve the computational complexity of this problem, shaving essentially a factor of $n$ from the running time of previous algorithms. Specifically, we present a \emph{deterministic} algorithm running in \emph{almost} linear time with respect to the input plus output size $k$. We also present a \emph{Las Vegas} algorithm running in \emph{nearly} linear expected time with respect to the input plus output size $k$. Previously, no deterministic or randomized $o(nk)$ algorithm was known. At the heart of our approach lies a careful usage of Kneser's theorem from Additive Combinatorics, and a new deterministic almost linear output-sensitive algorithm for non-negative sparse convolution. In total, our work builds a solid toolbox that could be of independent interest. %K Computer Science, Data Structures and Algorithms, cs.DS

[19]

K. Bringmann, A. Driemel, A. Nusser, and I. Psarros, “Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance,” 2021. [Online]. Available: https://arxiv.org/abs/2107.07792. (arXiv: 2107.07792)

Abstract

We study the $c$-approximate near neighbor problem under the continuous Fr\'echet distance: Given a set of $n$ polygonal curves with $m$ vertices, a radius $\delta > 0$, and a parameter $k \leq m$, we want to preprocess the curves into a data structure that, given a query curve $q$ with $k$ vertices, either returns an input curve with Fr\'echet distance at most $c\cdot \delta$ to $q$, or returns that there exists no input curve with Fr\'echet distance at most $\delta$ to $q$. We focus on the case where the input and the queries are one-dimensional polygonal curves -- also called time series -- and we give a comprehensive analysis for this case. We obtain new upper bounds that provide different tradeoffs between approximation factor, preprocessing time, and query time. Our data structures improve upon the state of the art in several ways. We show that for any $0 < \varepsilon \leq 1$ an approximation factor of $(1+\varepsilon)$ can be achieved within the same asymptotic time bounds as the previously best result for $(2+\varepsilon)$. Moreover, we show that an approximation factor of $(2+\varepsilon)$ can be obtained by using preprocessing time and space $O(nm)$, which is linear in the input size, and query time in $O(\frac{1}{\varepsilon})^{k+2}$, where the previously best result used preprocessing time in $n \cdot O(\frac{m}{\varepsilon k})^k$ and query time in $O(1)^k$. We complement our upper bounds with matching conditional lower bounds based on the Orthogonal Vectors Hypothesis. Interestingly, some of our lower bounds already hold for any super-constant value of $k$. This is achieved by proving hardness of a one-sided sparse version of the Orthogonal Vectors problem as an intermediate problem, which we believe to be of independent interest.

Links

Export

BibTeX

@online{Bringmann_2107.07792, TITLE = {Tight Bounds for Approximate Near Neighbor Searching for Time Series under the {F}r\'{e}chet Distance}, AUTHOR = {Bringmann, Karl and Driemel, Anne and Nusser, Andr{\'e} and Psarros, Ioannis}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2107.07792}, EPRINT = {2107.07792}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We study the $c$-approximate near neighbor problem under the continuous Fr\'echet distance: Given a set of $n$ polygonal curves with $m$ vertices, a radius $\delta > 0$, and a parameter $k \leq m$, we want to preprocess the curves into a data structure that, given a query curve $q$ with $k$ vertices, either returns an input curve with Fr\'echet distance at most $c\cdot \delta$ to $q$, or returns that there exists no input curve with Fr\'echet distance at most $\delta$ to $q$. We focus on the case where the input and the queries are one-dimensional polygonal curves -- also called time series -- and we give a comprehensive analysis for this case. We obtain new upper bounds that provide different tradeoffs between approximation factor, preprocessing time, and query time. Our data structures improve upon the state of the art in several ways. We show that for any $0 < \varepsilon \leq 1$ an approximation factor of $(1+\varepsilon)$ can be achieved within the same asymptotic time bounds as the previously best result for $(2+\varepsilon)$. Moreover, we show that an approximation factor of $(2+\varepsilon)$ can be obtained by using preprocessing time and space $O(nm)$, which is linear in the input size, and query time in $O(\frac{1}{\varepsilon})^{k+2}$, where the previously best result used preprocessing time in $n \cdot O(\frac{m}{\varepsilon k})^k$ and query time in $O(1)^k$. We complement our upper bounds with matching conditional lower bounds based on the Orthogonal Vectors Hypothesis. Interestingly, some of our lower bounds already hold for any super-constant value of $k$. This is achieved by proving hardness of a one-sided sparse version of the Orthogonal Vectors problem as an intermediate problem, which we believe to be of independent interest. }, }

Endnote

%0 Report %A Bringmann, Karl %A Driemel, Anne %A Nusser, André %A Psarros, Ioannis %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B43F-6 %U https://arxiv.org/abs/2107.07792 %D 2021 %X We study the $c$-approximate near neighbor problem under the continuous Fr\'echet distance: Given a set of $n$ polygonal curves with $m$ vertices, a radius $\delta > 0$, and a parameter $k \leq m$, we want to preprocess the curves into a data structure that, given a query curve $q$ with $k$ vertices, either returns an input curve with Fr\'echet distance at most $c\cdot \delta$ to $q$, or returns that there exists no input curve with Fr\'echet distance at most $\delta$ to $q$. We focus on the case where the input and the queries are one-dimensional polygonal curves -- also called time series -- and we give a comprehensive analysis for this case. We obtain new upper bounds that provide different tradeoffs between approximation factor, preprocessing time, and query time. Our data structures improve upon the state of the art in several ways. We show that for any $0 < \varepsilon \leq 1$ an approximation factor of $(1+\varepsilon)$ can be achieved within the same asymptotic time bounds as the previously best result for $(2+\varepsilon)$. Moreover, we show that an approximation factor of $(2+\varepsilon)$ can be obtained by using preprocessing time and space $O(nm)$, which is linear in the input size, and query time in $O(\frac{1}{\varepsilon})^{k+2}$, where the previously best result used preprocessing time in $n \cdot O(\frac{m}{\varepsilon k})^k$ and query time in $O(1)^k$. We complement our upper bounds with matching conditional lower bounds based on the Orthogonal Vectors Hypothesis. Interestingly, some of our lower bounds already hold for any super-constant value of $k$. This is achieved by proving hardness of a one-sided sparse version of the Orthogonal Vectors problem as an intermediate problem, which we believe to be of independent interest. %K Computer Science, Computational Geometry, cs.CG,Computer Science, Computational Complexity, cs.CC,Computer Science, Data Structures and Algorithms, cs.DS

[20]

K. Bringmann and J. Slusallek, “Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal,” in 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Glasgow, UK (Virtual Conference), 2021.

Links

Export

BibTeX

@inproceedings{Bringmann_ICALP2021b, TITLE = {Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal}, AUTHOR = {Bringmann, Karl and Slusallek, Jasper}, LANGUAGE = {eng}, ISSN = {1868-8969}, ISBN = {978-3-95977-195-5}, URL = {urn:nbn:de:0030-drops-141095}, DOI = {10.4230/LIPIcs.ICALP.2021.40}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, EDITOR = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, PAGES = {1--16}, EID = {40}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {198}, ADDRESS = {Glasgow, UK (Virtual Conference)}, }

Endnote

%0 Conference Proceedings %A Bringmann, Karl %A Slusallek, Jasper %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal : %G eng %U http://hdl.handle.net/21.11116/0000-0008-DB85-B %R 10.4230/LIPIcs.ICALP.2021.40 %U urn:nbn:de:0030-drops-141095 %D 2021 %B 48th International Colloquium on Automata, Languages, and Programming %Z date of event: 2021-07-12 - 2020-07-16 %C Glasgow, UK (Virtual Conference) %B 48th International Colloquium on Automata, Languages, and Programming %E Bansal, Nikhil; Merelli, Emanuela; Worrell, James %P 1 - 16 %Z sequence number: 40 %I Schloss Dagstuhl %@ 978-3-95977-195-5 %B Leibniz International Proceedings in Informatics %N 198 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2021/14109/https://creativecommons.org/licenses/by/4.0/legalcode

[21]

K. Bringmann and D. Das, “A Linear-Time n0.4-Approximation for Longest Common Subsequence,” in 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Glasgow, UK (Virtual Conference), 2021.

Links

Export

BibTeX

@inproceedings{Bringmann_ICALP2021, TITLE = {A Linear-Time $n^{0.4}$-Approximation for Longest Common Subsequence}, AUTHOR = {Bringmann, Karl and Das, Debarati}, LANGUAGE = {eng}, ISSN = {1868-8969}, ISBN = {978-3-95977-195-5}, URL = {urn:nbn:de:0030-drops-141082}, DOI = {10.4230/LIPIcs.ICALP.2021.39}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, EDITOR = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, PAGES = {1--20}, EID = {39}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {198}, ADDRESS = {Glasgow, UK (Virtual Conference)}, }

Endnote

%0 Conference Proceedings %A Bringmann, Karl %A Das, Debarati %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T A Linear-Time n0.4-Approximation for Longest Common Subsequence : %G eng %U http://hdl.handle.net/21.11116/0000-0008-DB7B-8 %R 10.4230/LIPIcs.ICALP.2021.39 %U urn:nbn:de:0030-drops-141082 %D 2021 %B 48th International Colloquium on Automata, Languages, and Programming %Z date of event: 2021-07-12 - 2020-07-16 %C Glasgow, UK (Virtual Conference) %B 48th International Colloquium on Automata, Languages, and Programming %E Bansal, Nikhil; Merelli, Emanuela; Worrell, James %P 1 - 20 %Z sequence number: 39 %I Schloss Dagstuhl %@ 978-3-95977-195-5 %B Leibniz International Proceedings in Informatics %N 198 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2021/14108/https://creativecommons.org/licenses/by/4.0/legalcode

[22]

K. Bringmann, M. Kapralov, M. Makarov, V. Nakos, A. Yagudin, and A. Zandieh, “Sparse Fourier Transform by Traversing Cooley-Tukey FFT Computation Graphs,” 2021. [Online]. Available: https://arxiv.org/abs/2107.07347. (arXiv: 2107.07347)

Abstract

Computing the dominant Fourier coefficients of a vector is a common task in many fields, such as signal processing, learning theory, and computational complexity. In the Sparse Fast Fourier Transform (Sparse FFT) problem, one is given oracle access to a $d$-dimensional vector $x$ of size $N$, and is asked to compute the best $k$-term approximation of its Discrete Fourier Transform, quickly and using few samples of the input vector $x$. While the sample complexity of this problem is quite well understood, all previous approaches either suffer from an exponential dependence of runtime on the dimension $d$ or can only tolerate a trivial amount of noise. This is in sharp contrast with the classical FFT algorithm of Cooley and Tukey, which is stable and completely insensitive to the dimension of the input vector: its runtime is $O(N\log N)$ in any dimension $d$. In this work, we introduce a new high-dimensional Sparse FFT toolkit and use it to obtain new algorithms, both on the exact, as well as in the case of bounded $\ell_2$ noise. This toolkit includes i) a new strategy for exploring a pruned FFT computation tree that reduces the cost of filtering, ii) new structural properties of adaptive aliasing filters recently introduced by Kapralov, Velingker and Zandieh'SODA'19, and iii) a novel lazy estimation argument, suited to reducing the cost of estimation in FFT tree-traversal approaches. Our robust algorithm can be viewed as a highly optimized sparse, stable extension of the Cooley-Tukey FFT algorithm. Finally, we explain the barriers we have faced by proving a conditional quadratic lower bound on the running time of the well-studied non-equispaced Fourier transform problem. This resolves a natural and frequently asked question in computational Fourier transforms. Lastly, we provide a preliminary experimental evaluation comparing the runtime of our algorithm to FFTW and SFFT 2.0.

Links

Export

BibTeX

@online{Bringmann_2107.07347, TITLE = {Sparse {Fourier Transform} by Traversing {Cooley-Tukey FFT} Computation Graphs}, AUTHOR = {Bringmann, Karl and Kapralov, Michael and Makarov, Mikhail and Nakos, Vasileios and Yagudin, Amir and Zandieh, Amir}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2107.07347}, EPRINT = {2107.07347}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {Computing the dominant Fourier coefficients of a vector is a common task in many fields, such as signal processing, learning theory, and computational complexity. In the Sparse Fast Fourier Transform (Sparse FFT) problem, one is given oracle access to a $d$-dimensional vector $x$ of size $N$, and is asked to compute the best $k$-term approximation of its Discrete Fourier Transform, quickly and using few samples of the input vector $x$. While the sample complexity of this problem is quite well understood, all previous approaches either suffer from an exponential dependence of runtime on the dimension $d$ or can only tolerate a trivial amount of noise. This is in sharp contrast with the classical FFT algorithm of Cooley and Tukey, which is stable and completely insensitive to the dimension of the input vector: its runtime is $O(N\log N)$ in any dimension $d$. In this work, we introduce a new high-dimensional Sparse FFT toolkit and use it to obtain new algorithms, both on the exact, as well as in the case of bounded $\ell_2$ noise. This toolkit includes i) a new strategy for exploring a pruned FFT computation tree that reduces the cost of filtering, ii) new structural properties of adaptive aliasing filters recently introduced by Kapralov, Velingker and Zandieh'SODA'19, and iii) a novel lazy estimation argument, suited to reducing the cost of estimation in FFT tree-traversal approaches. Our robust algorithm can be viewed as a highly optimized sparse, stable extension of the Cooley-Tukey FFT algorithm. Finally, we explain the barriers we have faced by proving a conditional quadratic lower bound on the running time of the well-studied non-equispaced Fourier transform problem. This resolves a natural and frequently asked question in computational Fourier transforms. Lastly, we provide a preliminary experimental evaluation comparing the runtime of our algorithm to FFTW and SFFT 2.0. }, }

Endnote

%0 Report %A Bringmann, Karl %A Kapralov, Michael %A Makarov, Mikhail %A Nakos, Vasileios %A Yagudin, Amir %A Zandieh, Amir %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Sparse Fourier Transform by Traversing Cooley-Tukey FFT Computation Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B459-8 %U https://arxiv.org/abs/2107.07347 %D 2021 %X Computing the dominant Fourier coefficients of a vector is a common task in many fields, such as signal processing, learning theory, and computational complexity. In the Sparse Fast Fourier Transform (Sparse FFT) problem, one is given oracle access to a $d$-dimensional vector $x$ of size $N$, and is asked to compute the best $k$-term approximation of its Discrete Fourier Transform, quickly and using few samples of the input vector $x$. While the sample complexity of this problem is quite well understood, all previous approaches either suffer from an exponential dependence of runtime on the dimension $d$ or can only tolerate a trivial amount of noise. This is in sharp contrast with the classical FFT algorithm of Cooley and Tukey, which is stable and completely insensitive to the dimension of the input vector: its runtime is $O(N\log N)$ in any dimension $d$. In this work, we introduce a new high-dimensional Sparse FFT toolkit and use it to obtain new algorithms, both on the exact, as well as in the case of bounded $\ell_2$ noise. This toolkit includes i) a new strategy for exploring a pruned FFT computation tree that reduces the cost of filtering, ii) new structural properties of adaptive aliasing filters recently introduced by Kapralov, Velingker and Zandieh'SODA'19, and iii) a novel lazy estimation argument, suited to reducing the cost of estimation in FFT tree-traversal approaches. Our robust algorithm can be viewed as a highly optimized sparse, stable extension of the Cooley-Tukey FFT algorithm. Finally, we explain the barriers we have faced by proving a conditional quadratic lower bound on the running time of the well-studied non-equispaced Fourier transform problem. This resolves a natural and frequently asked question in computational Fourier transforms. Lastly, we provide a preliminary experimental evaluation comparing the runtime of our algorithm to FFTW and SFFT 2.0. %K Computer Science, Data Structures and Algorithms, cs.DS

[23]

K. Bringmann and A. Nusser, “Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation,” in 37th International Symposium on Computational Geometry (SoCG 2021), Buffalo, NY, USA (Virtual Conference), 2021.

Links

Export

BibTeX

@inproceedings{Bringmann_SoCG2021, TITLE = {Translating {Hausdorff} Is Hard: {F}ine-Grained Lower Bounds for {Hausdorff} Distance Under Translation}, AUTHOR = {Bringmann, Karl and Nusser, Andr{\'e}}, LANGUAGE = {eng}, ISSN = {1868-8969}, ISBN = {978-3-95977-184-9}, URL = {urn:nbn:de:0030-drops-138177}, DOI = {10.4230/LIPIcs.SoCG.2021.18}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {37th International Symposium on Computational Geometry (SoCG 2021)}, EDITOR = {Buchin, Kevin and Colin de Verdi{\`e}re, {\'E}rich}, PAGES = {1--17}, EID = {18}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {189}, ADDRESS = {Buffalo, NY, USA (Virtual Conference)}, }

Endnote

%0 Conference Proceedings %A Bringmann, Karl %A Nusser, André %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation : %G eng %U http://hdl.handle.net/21.11116/0000-0008-DB6F-6 %R 10.4230/LIPIcs.SoCG.2021.18 %U urn:nbn:de:0030-drops-138177 %D 2021 %B 37th International Symposium on Computational Geometry %Z date of event: 2021-06-07 - 2021-06-11 %C Buffalo, NY, USA (Virtual Conference) %B 37th International Symposium on Computational Geometry %E Buchin, Kevin; Colin de Verdière, Érich %P 1 - 17 %Z sequence number: 18 %I Schloss Dagstuhl %@ 978-3-95977-184-9 %B Leibniz International Proceedings in Informatics %N 189 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2021/13817/https://creativecommons.org/licenses/by/4.0/legalcode

[24]

K. Bringmann and V. Nakos, “Fast n-Fold Boolean Convolution via Additive Combinatorics,” in 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Glasgow, UK (Virtual Conference), 2021.

Links

Export

BibTeX

@inproceedings{Bringmann_ICALP2021c, TITLE = {Fast $n$-Fold {B}oolean Convolution via Additive Combinatorics}, AUTHOR = {Bringmann, Karl and Nakos, Vasileios}, LANGUAGE = {eng}, ISSN = {1868-8969}, ISBN = {978-3-95977-195-5}, URL = {urn:nbn:de:0030-drops-141108}, DOI = {10.4230/LIPIcs.ICALP.2021.41}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, EDITOR = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, PAGES = {1--17}, EID = {41}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {198}, ADDRESS = {Glasgow, UK (Virtual Conference)}, }

Endnote

%0 Conference Proceedings %A Bringmann, Karl %A Nakos, Vasileios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Fast n-Fold Boolean Convolution via Additive Combinatorics : %G eng %U http://hdl.handle.net/21.11116/0000-0008-DB8E-2 %R 10.4230/LIPIcs.ICALP.2021.41 %U urn:nbn:de:0030-drops-141108 %D 2021 %B 48th International Colloquium on Automata, Languages, and Programming %Z date of event: 2021-07-12 - 2020-07-16 %C Glasgow, UK (Virtual Conference) %B 48th International Colloquium on Automata, Languages, and Programming %E Bansal, Nikhil; Merelli, Emanuela; Worrell, James %P 1 - 17 %Z sequence number: 41 %I Schloss Dagstuhl %@ 978-3-95977-195-5 %B Leibniz International Proceedings in Informatics %N 198 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2021/14110/pdf/LIPIcs-ICALP-2021-41.pdfhttps://creativecommons.org/licenses/by/4.0/legalcode

[25]

K. Bringmann, N. Fischer, and V. Nakos, “Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution,” 2021. [Online]. Available: https://arxiv.org/abs/2107.07625. (arXiv: 2107.07625)

Abstract

Computing the convolution $A\star B$ of two length-$n$ integer vectors $A,B$ is a core problem in several disciplines. It frequently comes up in algorithms for Knapsack, $k$-SUM, All-Pairs Shortest Paths, and string pattern matching problems. For these applications it typically suffices to compute convolutions of nonnegative vectors. This problem can be classically solved in time $O(n\log n)$ using the Fast Fourier Transform. However, often the involved vectors are sparse and hence one could hope for output-sensitive algorithms to compute nonnegative convolutions. This question was raised by Muthukrishnan and solved by Cole and Hariharan (STOC '02) by a randomized algorithm running in near-linear time in the (unknown) output-size $t$. Chan and Lewenstein (STOC '15) presented a deterministic algorithm with a $2^{O(\sqrt{\log t\cdot\log\log n})}$ overhead in running time and the additional assumption that a small superset of the output is given; this assumption was later removed by Bringmann and Nakos (ICALP '21). In this paper we present the first deterministic near-linear-time algorithm for computing sparse nonnegative convolutions. This immediately gives improved deterministic algorithms for the state-of-the-art of output-sensitive Subset Sum, block-mass pattern matching, $N$-fold Boolean convolution, and others, matching up to log-factors the fastest known randomized algorithms for these problems. Our algorithm is a blend of algebraic and combinatorial ideas and techniques. Additionally, we provide two fast Las Vegas algorithms for computing sparse nonnegative convolutions. In particular, we present a simple $O(t\log^2t)$ time algorithm, which is an accessible alternative to Cole and Hariharan's algorithm. We further refine this new algorithm to run in Las Vegas time $O(t\log t\cdot\log\log t)$, matching the running time of the dense case apart from the $\log\log t$ factor.

Links

Export

BibTeX

@online{Bringmann_2107.07625, TITLE = {Deterministic and {Las Vegas} Algorithms for Sparse Nonnegative Convolution}, AUTHOR = {Bringmann, Karl and Fischer, Nick and Nakos, Vasileios}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2107.07625}, EPRINT = {2107.07625}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {Computing the convolution $A\star B$ of two length-$n$ integer vectors $A,B$ is a core problem in several disciplines. It frequently comes up in algorithms for Knapsack, $k$-SUM, All-Pairs Shortest Paths, and string pattern matching problems. For these applications it typically suffices to compute convolutions of nonnegative vectors. This problem can be classically solved in time $O(n\log n)$ using the Fast Fourier Transform. However, often the involved vectors are sparse and hence one could hope for output-sensitive algorithms to compute nonnegative convolutions. This question was raised by Muthukrishnan and solved by Cole and Hariharan (STOC '02) by a randomized algorithm running in near-linear time in the (unknown) output-size $t$. Chan and Lewenstein (STOC '15) presented a deterministic algorithm with a $2^{O(\sqrt{\log t\cdot\log\log n})}$ overhead in running time and the additional assumption that a small superset of the output is given; this assumption was later removed by Bringmann and Nakos (ICALP '21). In this paper we present the first deterministic near-linear-time algorithm for computing sparse nonnegative convolutions. This immediately gives improved deterministic algorithms for the state-of-the-art of output-sensitive Subset Sum, block-mass pattern matching, $N$-fold Boolean convolution, and others, matching up to log-factors the fastest known randomized algorithms for these problems. Our algorithm is a blend of algebraic and combinatorial ideas and techniques. Additionally, we provide two fast Las Vegas algorithms for computing sparse nonnegative convolutions. In particular, we present a simple $O(t\log^2t)$ time algorithm, which is an accessible alternative to Cole and Hariharan's algorithm. We further refine this new algorithm to run in Las Vegas time $O(t\log t\cdot\log\log t)$, matching the running time of the dense case apart from the $\log\log t$ factor. }, }

Endnote

%0 Report %A Bringmann, Karl %A Fischer, Nick %A Nakos, Vasileios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B454-D %U https://arxiv.org/abs/2107.07625 %D 2021 %X Computing the convolution $A\star B$ of two length-$n$ integer vectors $A,B$ is a core problem in several disciplines. It frequently comes up in algorithms for Knapsack, $k$-SUM, All-Pairs Shortest Paths, and string pattern matching problems. For these applications it typically suffices to compute convolutions of nonnegative vectors. This problem can be classically solved in time $O(n\log n)$ using the Fast Fourier Transform. However, often the involved vectors are sparse and hence one could hope for output-sensitive algorithms to compute nonnegative convolutions. This question was raised by Muthukrishnan and solved by Cole and Hariharan (STOC '02) by a randomized algorithm running in near-linear time in the (unknown) output-size $t$. Chan and Lewenstein (STOC '15) presented a deterministic algorithm with a $2^{O(\sqrt{\log t\cdot\log\log n})}$ overhead in running time and the additional assumption that a small superset of the output is given; this assumption was later removed by Bringmann and Nakos (ICALP '21). In this paper we present the first deterministic near-linear-time algorithm for computing sparse nonnegative convolutions. This immediately gives improved deterministic algorithms for the state-of-the-art of output-sensitive Subset Sum, block-mass pattern matching, $N$-fold Boolean convolution, and others, matching up to log-factors the fastest known randomized algorithms for these problems. Our algorithm is a blend of algebraic and combinatorial ideas and techniques. Additionally, we provide two fast Las Vegas algorithms for computing sparse nonnegative convolutions. In particular, we present a simple $O(t\log^2t)$ time algorithm, which is an accessible alternative to Cole and Hariharan's algorithm. We further refine this new algorithm to run in Las Vegas time $O(t\log t\cdot\log\log t)$, matching the running time of the dense case apart from the $\log\log t$ factor. %K Computer Science, Data Structures and Algorithms, cs.DS

[26]

K. Bringmann and V. Nakos, “Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum,” 2021. [Online]. Available: https://arxiv.org/abs/2107.13206. (arXiv: 2107.13206)

Abstract

In the classical Subset Sum problem we are given a set $X$ and a target $t$, and the task is to decide whether there exists a subset of $X$ which sums to $t$. A recent line of research has resulted in $\tilde{O}(t)$-time algorithms, which are (near-)optimal under popular complexity-theoretic assumptions. On the other hand, the standard dynamic programming algorithm runs in time $O(n \cdot |\mathcal{S}(X,t)|)$, where $\mathcal{S}(X,t)$ is the set of all subset sums of $X$ that are smaller than $t$. Furthermore, all known pseudopolynomial algorithms actually solve a stronger task, since they actually compute the whole set $\mathcal{S}(X,t)$. As the aforementioned two running times are incomparable, in this paper we ask whether one can achieve the best of both worlds: running time $\tilde{O}(|\mathcal{S}(X,t)|)$. In particular, we ask whether $\mathcal{S}(X,t)$ can be computed in near-linear time in the output-size. Using a diverse toolkit containing techniques such as color coding, sparse recovery, and sumset estimates, we make considerable progress towards this question and design an algorithm running in time $\tilde{O}(|\mathcal{S}(X,t)|^{4/3})$. Central to our approach is the study of top-$k$-convolution, a natural problem of independent interest: given sparse polynomials with non-negative coefficients, compute the lowest $k$ non-zero monomials of their product. We design an algorithm running in time $\tilde{O}(k^{4/3})$, by a combination of sparse convolution and sumset estimates considered in Additive Combinatorics. Moreover, we provide evidence that going beyond some of the barriers we have faced requires either an algorithmic breakthrough or possibly new techniques from Additive Combinatorics on how to pass from information on restricted sumsets to information on unrestricted sumsets.

Links

Export

BibTeX

@online{Bringmann_2107.13206, TITLE = {Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum}, AUTHOR = {Bringmann, Karl and Nakos, Vasileios}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2107.13206}, EPRINT = {2107.13206}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {In the classical Subset Sum problem we are given a set $X$ and a target $t$, and the task is to decide whether there exists a subset of $X$ which sums to $t$. A recent line of research has resulted in $\tilde{O}(t)$-time algorithms, which are (near-)optimal under popular complexity-theoretic assumptions. On the other hand, the standard dynamic programming algorithm runs in time $O(n \cdot |\mathcal{S}(X,t)|)$, where $\mathcal{S}(X,t)$ is the set of all subset sums of $X$ that are smaller than $t$. Furthermore, all known pseudopolynomial algorithms actually solve a stronger task, since they actually compute the whole set $\mathcal{S}(X,t)$. As the aforementioned two running times are incomparable, in this paper we ask whether one can achieve the best of both worlds: running time $\tilde{O}(|\mathcal{S}(X,t)|)$. In particular, we ask whether $\mathcal{S}(X,t)$ can be computed in near-linear time in the output-size. Using a diverse toolkit containing techniques such as color coding, sparse recovery, and sumset estimates, we make considerable progress towards this question and design an algorithm running in time $\tilde{O}(|\mathcal{S}(X,t)|^{4/3})$. Central to our approach is the study of top-$k$-convolution, a natural problem of independent interest: given sparse polynomials with non-negative coefficients, compute the lowest $k$ non-zero monomials of their product. We design an algorithm running in time $\tilde{O}(k^{4/3})$, by a combination of sparse convolution and sumset estimates considered in Additive Combinatorics. Moreover, we provide evidence that going beyond some of the barriers we have faced requires either an algorithmic breakthrough or possibly new techniques from Additive Combinatorics on how to pass from information on restricted sumsets to information on unrestricted sumsets. }, }

Endnote

%0 Report %A Bringmann, Karl %A Nakos, Vasileios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B434-1 %U https://arxiv.org/abs/2107.13206 %D 2021 %X In the classical Subset Sum problem we are given a set $X$ and a target $t$, and the task is to decide whether there exists a subset of $X$ which sums to $t$. A recent line of research has resulted in $\tilde{O}(t)$-time algorithms, which are (near-)optimal under popular complexity-theoretic assumptions. On the other hand, the standard dynamic programming algorithm runs in time $O(n \cdot |\mathcal{S}(X,t)|)$, where $\mathcal{S}(X,t)$ is the set of all subset sums of $X$ that are smaller than $t$. Furthermore, all known pseudopolynomial algorithms actually solve a stronger task, since they actually compute the whole set $\mathcal{S}(X,t)$. As the aforementioned two running times are incomparable, in this paper we ask whether one can achieve the best of both worlds: running time $\tilde{O}(|\mathcal{S}(X,t)|)$. In particular, we ask whether $\mathcal{S}(X,t)$ can be computed in near-linear time in the output-size. Using a diverse toolkit containing techniques such as color coding, sparse recovery, and sumset estimates, we make considerable progress towards this question and design an algorithm running in time $\tilde{O}(|\mathcal{S}(X,t)|^{4/3})$. Central to our approach is the study of top-$k$-convolution, a natural problem of independent interest: given sparse polynomials with non-negative coefficients, compute the lowest $k$ non-zero monomials of their product. We design an algorithm running in time $\tilde{O}(k^{4/3})$, by a combination of sparse convolution and sumset estimates considered in Additive Combinatorics. Moreover, we provide evidence that going beyond some of the barriers we have faced requires either an algorithmic breakthrough or possibly new techniques from Additive Combinatorics on how to pass from information on restricted sumsets to information on unrestricted sumsets. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Discrete Mathematics, cs.DM

[27]

K. Bringmann and V. Nakos, “A Fine-Grained Perspective on Approximating Subset Sum and Partition,” in Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, VA, USA (Virtual Conference), 2021.

Links

Export

BibTeX

@inproceedings{Bringmann_SODA21b, TITLE = {A Fine-Grained Perspective on Approximating {Subset Sum} and Partition}, AUTHOR = {Bringmann, Karl and Nakos, Vasileios}, LANGUAGE = {eng}, ISBN = {978-1-61197-646-5}, DOI = {10.1137/1.9781611976465.108}, PUBLISHER = {SIAM}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, DATE = {2021}, BOOKTITLE = {Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)}, EDITOR = {Marx, D{\'a}niel}, PAGES = {1797--1815}, ADDRESS = {Alexandria, VA, USA (Virtual Conference)}, }

Endnote

[28]

K. Bringmann and P. Wellnitz, “On Near-Linear-Time Algorithms for Dense Subset Sum,” in Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, VA, USA (Virtual Conference), 2021.

Links

Export

BibTeX

@inproceedings{Bringmann_SODA21, TITLE = {On Near-Linear-Time Algorithms for Dense {Subset Sum}}, AUTHOR = {Bringmann, Karl and Wellnitz, Philip}, LANGUAGE = {eng}, ISBN = {978-1-61197-646-5}, DOI = {10.1137/1.9781611976465.107}, PUBLISHER = {SIAM}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, DATE = {2021}, BOOKTITLE = {Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)}, EDITOR = {Marx, D{\'a}niel}, PAGES = {1777--1796}, ADDRESS = {Alexandria, VA, USA (Virtual Conference)}, }

Endnote

%0 Conference Proceedings %A Bringmann, Karl %A Wellnitz, Philip %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T On Near-Linear-Time Algorithms for Dense Subset Sum : %G eng %U http://hdl.handle.net/21.11116/0000-0007-8C7E-F %R 10.1137/1.9781611976465.107 %D 2021 %B 32nd Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2021-01-10 - 2021-01-13 %C Alexandria, VA, USA (Virtual Conference) %B Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms %E Marx, Dániel %P 1777 - 1796 %I SIAM %@ 978-1-61197-646-5

[29]

K. Bringmann, N. Fischer, and V. Nakos, “Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution,” 2021. [Online]. Available: https://arxiv.org/abs/2105.05984. (arXiv: 2105.05984)

Abstract

Computing the convolution $A\star B$ of two length-$n$ vectors $A,B$ is an ubiquitous computational primitive. Applications range from string problems to Knapsack-type problems, and from 3SUM to All-Pairs Shortest Paths. These applications often come in the form of nonnegative convolution, where the entries of $A,B$ are nonnegative integers. The classical algorithm to compute $A\star B$ uses the Fast Fourier Transform and runs in time $O(n\log n)$. However, often $A$ and $B$ satisfy sparsity conditions, and hence one could hope for significant improvements. The ideal goal is an $O(k\log k)$-time algorithm, where $k$ is the number of non-zero elements in the output, i.e., the size of the support of $A\star B$. This problem is referred to as sparse nonnegative convolution, and has received considerable attention in the literature; the fastest algorithms to date run in time $O(k\log^2 n)$. The main result of this paper is the first $O(k\log k)$-time algorithm for sparse nonnegative convolution. Our algorithm is randomized and assumes that the length $n$ and the largest entry of $A$ and $B$ are subexponential in $k$. Surprisingly, we can phrase our algorithm as a reduction from the sparse case to the dense case of nonnegative convolution, showing that, under some mild assumptions, sparse nonnegative convolution is equivalent to dense nonnegative convolution for constant-error randomized algorithms. Specifically, if $D(n)$ is the time to convolve two nonnegative length-$n$ vectors with success probability $2/3$, and $S(k)$ is the time to convolve two nonnegative vectors with output size $k$ with success probability $2/3$, then $S(k)=O(D(k)+k(\log\log k)^2)$. Our approach uses a variety of new techniques in combination with some old machinery from linear sketching and structured linear algebra, as well as new insights on linear hashing, the most classical hash function.

Links

Export

BibTeX

@online{Bringmann_2105.05984, TITLE = {Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution}, AUTHOR = {Bringmann, Karl and Fischer, Nick and Nakos, Vasileios}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2105.05984}, EPRINT = {2105.05984}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {Computing the convolution $A\star B$ of two length-$n$ vectors $A,B$ is an ubiquitous computational primitive. Applications range from string problems to Knapsack-type problems, and from 3SUM to All-Pairs Shortest Paths. These applications often come in the form of nonnegative convolution, where the entries of $A,B$ are nonnegative integers. The classical algorithm to compute $A\star B$ uses the Fast Fourier Transform and runs in time $O(n\log n)$. However, often $A$ and $B$ satisfy sparsity conditions, and hence one could hope for significant improvements. The ideal goal is an $O(k\log k)$-time algorithm, where $k$ is the number of non-zero elements in the output, i.e., the size of the support of $A\star B$. This problem is referred to as sparse nonnegative convolution, and has received considerable attention in the literature; the fastest algorithms to date run in time $O(k\log^2 n)$. The main result of this paper is the first $O(k\log k)$-time algorithm for sparse nonnegative convolution. Our algorithm is randomized and assumes that the length $n$ and the largest entry of $A$ and $B$ are subexponential in $k$. Surprisingly, we can phrase our algorithm as a reduction from the sparse case to the dense case of nonnegative convolution, showing that, under some mild assumptions, sparse nonnegative convolution is equivalent to dense nonnegative convolution for constant-error randomized algorithms. Specifically, if $D(n)$ is the time to convolve two nonnegative length-$n$ vectors with success probability $2/3$, and $S(k)$ is the time to convolve two nonnegative vectors with output size $k$ with success probability $2/3$, then $S(k)=O(D(k)+k(\log\log k)^2)$. Our approach uses a variety of new techniques in combination with some old machinery from linear sketching and structured linear algebra, as well as new insights on linear hashing, the most classical hash function. }, }

Endnote

%0 Report %A Bringmann, Karl %A Fischer, Nick %A Nakos, Vasileios %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E263-9 %U https://arxiv.org/abs/2105.05984 %D 2021 %X Computing the convolution $A\star B$ of two length-$n$ vectors $A,B$ is an ubiquitous computational primitive. Applications range from string problems to Knapsack-type problems, and from 3SUM to All-Pairs Shortest Paths. These applications often come in the form of nonnegative convolution, where the entries of $A,B$ are nonnegative integers. The classical algorithm to compute $A\star B$ uses the Fast Fourier Transform and runs in time $O(n\log n)$. However, often $A$ and $B$ satisfy sparsity conditions, and hence one could hope for significant improvements. The ideal goal is an $O(k\log k)$-time algorithm, where $k$ is the number of non-zero elements in the output, i.e., the size of the support of $A\star B$. This problem is referred to as sparse nonnegative convolution, and has received considerable attention in the literature; the fastest algorithms to date run in time $O(k\log^2 n)$. The main result of this paper is the first $O(k\log k)$-time algorithm for sparse nonnegative convolution. Our algorithm is randomized and assumes that the length $n$ and the largest entry of $A$ and $B$ are subexponential in $k$. Surprisingly, we can phrase our algorithm as a reduction from the sparse case to the dense case of nonnegative convolution, showing that, under some mild assumptions, sparse nonnegative convolution is equivalent to dense nonnegative convolution for constant-error randomized algorithms. Specifically, if $D(n)$ is the time to convolve two nonnegative length-$n$ vectors with success probability $2/3$, and $S(k)$ is the time to convolve two nonnegative vectors with output size $k$ with success probability $2/3$, then $S(k)=O(D(k)+k(\log\log k)^2)$. Our approach uses a variety of new techniques in combination with some old machinery from linear sketching and structured linear algebra, as well as new insights on linear hashing, the most classical hash function. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computational Complexity, cs.CC

[30]

K. Bringmann, V. Cohen-Addad, and D. Das, “A Linear-Time n0.4-Approximation for Longest Common Subsequence,” 2021. [Online]. Available: https://arxiv.org/abs/2106.08195. (arXiv: 2106.08195)

Abstract

We consider the classic problem of computing the Longest Common Subsequence (LCS) of two strings of length $n$. While a simple quadratic algorithm has been known for the problem for more than 40 years, no faster algorithm has been found despite an extensive effort. The lack of progress on the problem has recently been explained by Abboud, Backurs, and Vassilevska Williams [FOCS'15] and Bringmann and K\"unnemann [FOCS'15] who proved that there is no subquadratic algorithm unless the Strong Exponential Time Hypothesis fails. This has led the community to look for subquadratic approximation algorithms for the problem. Yet, unlike the edit distance problem for which a constant-factor approximation in almost-linear time is known, very little progress has been made on LCS, making it a notoriously difficult problem also in the realm of approximation. For the general setting, only a naive $O(n^{\varepsilon/2})$-approximation algorithm with running time $\tilde{O}(n^{2-\varepsilon})$ has been known, for any constant $0 < \varepsilon \le 1$. Recently, a breakthrough result by Hajiaghayi, Seddighin, Seddighin, and Sun [SODA'19] provided a linear-time algorithm that yields a $O(n^{0.497956})$-approximation in expectation; improving upon the naive $O(\sqrt{n})$-approximation for the first time. In this paper, we provide an algorithm that in time $O(n^{2-\varepsilon})$ computes an $\tilde{O}(n^{2\varepsilon/5})$-approximation with high probability, for any $0 < \varepsilon \le 1$. Our result (1) gives an $\tilde{O}(n^{0.4})$-approximation in linear time, improving upon the bound of Hajiaghayi, Seddighin, Seddighin, and Sun, (2) provides an algorithm whose approximation scales with any subquadratic running time $O(n^{2-\varepsilon})$, improving upon the naive bound of $O(n^{\varepsilon/2})$ for any $\varepsilon$, and (3) instead of only in expectation, succeeds with high probability.

Links

Export

BibTeX

@online{Bringmann_2106.08195, TITLE = {A Linear-Time $n^{0.4}$-Approximation for Longest Common Subsequence}, AUTHOR = {Bringmann, Karl and Cohen-Addad, Vincent and Das, Debarati}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2106.08195}, EPRINT = {2106.08195}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We consider the classic problem of computing the Longest Common Subsequence (LCS) of two strings of length $n$. While a simple quadratic algorithm has been known for the problem for more than 40 years, no faster algorithm has been found despite an extensive effort. The lack of progress on the problem has recently been explained by Abboud, Backurs, and Vassilevska Williams [FOCS'15] and Bringmann and K\"unnemann [FOCS'15] who proved that there is no subquadratic algorithm unless the Strong Exponential Time Hypothesis fails. This has led the community to look for subquadratic approximation algorithms for the problem. Yet, unlike the edit distance problem for which a constant-factor approximation in almost-linear time is known, very little progress has been made on LCS, making it a notoriously difficult problem also in the realm of approximation. For the general setting, only a naive $O(n^{\varepsilon/2})$-approximation algorithm with running time $\tilde{O}(n^{2-\varepsilon})$ has been known, for any constant $0 < \varepsilon \le 1$. Recently, a breakthrough result by Hajiaghayi, Seddighin, Seddighin, and Sun [SODA'19] provided a linear-time algorithm that yields a $O(n^{0.497956})$-approximation in expectation; improving upon the naive $O(\sqrt{n})$-approximation for the first time. In this paper, we provide an algorithm that in time $O(n^{2-\varepsilon})$ computes an $\tilde{O}(n^{2\varepsilon/5})$-approximation with high probability, for any $0 < \varepsilon \le 1$. Our result (1) gives an $\tilde{O}(n^{0.4})$-approximation in linear time, improving upon the bound of Hajiaghayi, Seddighin, Seddighin, and Sun, (2) provides an algorithm whose approximation scales with any subquadratic running time $O(n^{2-\varepsilon})$, improving upon the naive bound of $O(n^{\varepsilon/2})$ for any $\varepsilon$, and (3) instead of only in expectation, succeeds with high probability. }, }

Endnote

%0 Report %A Bringmann, Karl %A Cohen-Addad, Vincent %A Das, Debarati %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T A Linear-Time n0.4-Approximation for Longest Common Subsequence : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E267-5 %U https://arxiv.org/abs/2106.08195 %D 2021 %X We consider the classic problem of computing the Longest Common Subsequence (LCS) of two strings of length $n$. While a simple quadratic algorithm has been known for the problem for more than 40 years, no faster algorithm has been found despite an extensive effort. The lack of progress on the problem has recently been explained by Abboud, Backurs, and Vassilevska Williams [FOCS'15] and Bringmann and K\"unnemann [FOCS'15] who proved that there is no subquadratic algorithm unless the Strong Exponential Time Hypothesis fails. This has led the community to look for subquadratic approximation algorithms for the problem. Yet, unlike the edit distance problem for which a constant-factor approximation in almost-linear time is known, very little progress has been made on LCS, making it a notoriously difficult problem also in the realm of approximation. For the general setting, only a naive $O(n^{\varepsilon/2})$-approximation algorithm with running time $\tilde{O}(n^{2-\varepsilon})$ has been known, for any constant $0 < \varepsilon \le 1$. Recently, a breakthrough result by Hajiaghayi, Seddighin, Seddighin, and Sun [SODA'19] provided a linear-time algorithm that yields a $O(n^{0.497956})$-approximation in expectation; improving upon the naive $O(\sqrt{n})$-approximation for the first time. In this paper, we provide an algorithm that in time $O(n^{2-\varepsilon})$ computes an $\tilde{O}(n^{2\varepsilon/5})$-approximation with high probability, for any $0 < \varepsilon \le 1$. Our result (1) gives an $\tilde{O}(n^{0.4})$-approximation in linear time, improving upon the bound of Hajiaghayi, Seddighin, Seddighin, and Sun, (2) provides an algorithm whose approximation scales with any subquadratic running time $O(n^{2-\varepsilon})$, improving upon the naive bound of $O(n^{\varepsilon/2})$ for any $\varepsilon$, and (3) instead of only in expectation, succeeds with high probability. %K Computer Science, Data Structures and Algorithms, cs.DS,

[31]

P. Charalampopoulos, T. Kociumaka, and P. Wellnitz, “Faster Approximate Pattern Matching: A Unified Approach,” in FOCS 2020, 61st Annual IEEE Symposium on Foundations of Computer Science, Durham, NC, USA (Virtual Conference), 2021.

Links

Export

BibTeX

@inproceedings{Charalampopoulos_FOCS2020, TITLE = {Faster Approximate Pattern Matching: {A} Unified Approach}, AUTHOR = {Charalampopoulos, Panagiotis and Kociumaka, Tomasz and Wellnitz, Philip}, LANGUAGE = {eng}, ISBN = {978-1-7281-9621-3}, DOI = {10.1109/FOCS46700.2020}, PUBLISHER = {IEEE}, YEAR = {2020}, MARGINALMARK = {$\bullet$}, DATE = {2021}, BOOKTITLE = {FOCS 2020, 61st Annual IEEE Symposium on Foundations of Computer Science}, PAGES = {978--989}, ADDRESS = {Durham, NC, USA (Virtual Conference)}, }

Endnote

%0 Conference Proceedings %A Charalampopoulos, Panagiotis %A Kociumaka, Tomasz %A Wellnitz, Philip %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Faster Approximate Pattern Matching: A Unified Approach : %G eng %U http://hdl.handle.net/21.11116/0000-0007-8C66-9 %R 10.1109/FOCS46700.2020 %D 2021 %B 61st Annual IEEE Symposium on Foundations of Computer Science %Z date of event: 2020-11-16 - 2020-11-19 %C Durham, NC, USA (Virtual Conference) %B FOCS 2020 %P 978 - 989 %I IEEE %@ 978-1-7281-9621-3

[32]

B. R. Chaudhury, “Finding Fair and Efficient Allocations,” Universität des Saarlandes, Saarbrücken, 2021.

Links

Export

BibTeX

@phdthesis{Chaudphd2021, TITLE = {Finding Fair and Efficient Allocations}, AUTHOR = {Chaudhury, Bhaskar Ray}, LANGUAGE = {eng}, URL = {nbn:de:bsz:291--ds-345370}, DOI = {10.22028/D291-34537}, SCHOOL = {Universit{\"a}t des Saarlandes}, ADDRESS = {Saarbr{\"u}cken}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, DATE = {2021}, }

Endnote

%0 Thesis %A Chaudhury, Bhaskar Ray %Y Mehlhorn, Kurt %A referee: Bringmann, Karl %A referee: Roughgarden, Tim %A referee: Moulin, Herve %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society International Max Planck Research School, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Finding Fair and Efficient Allocations : %G eng %U http://hdl.handle.net/21.11116/0000-0009-9CC9-5 %R 10.22028/D291-34537 %U nbn:de:bsz:291--ds-345370 %F OTHER: hdl:20.500.11880/31737 %I Universität des Saarlandes %C Saarbrücken %D 2021 %P 173 p. %V phd %9 phd %U https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/31737

[33]

B. R. Chaudhury, J. Garg, K. Mehlhorn, R. Mehta, and P. Misra, “Improving EFX Guarantees through Rainbow Cycle Number,” in EC ’21, 22nd ACM Conference on Economics and Computation, Budapest, Hungary (Virtual), 2021.

Links

Export

BibTeX

@inproceedings{Chaudhury_EC2021, TITLE = {Improving {EFX} Guarantees through Rainbow Cycle Number}, AUTHOR = {Chaudhury, Bhaskar Ray and Garg, Jugal and Mehlhorn, Kurt and Mehta, Ruta and Misra, Pranabendu}, LANGUAGE = {eng}, ISBN = {978-1-4503-8554-1}, DOI = {10.1145/3465456.3467605}, PUBLISHER = {ACM}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {EC '21, 22nd ACM Conference on Economics and Computation}, EDITOR = {Bir{\'o}, P{\'e}ter and Chawla, Shuchi and Echenique, Federico and Sodomka, Eric}, PAGES = {310--311}, ADDRESS = {Budapest, Hungary (Virtual)}, }

Endnote

%0 Conference Proceedings %A Chaudhury, Bhaskar Ray %A Garg, Jugal %A Mehlhorn, Kurt %A Mehta, Ruta %A Misra, Pranabendu %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Improving EFX Guarantees through Rainbow Cycle Number : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B3F6-7 %R 10.1145/3465456.3467605 %D 2021 %B 22nd ACM Conference on Economics and Computation %Z date of event: 2021-07-18 - 2021-07-23 %C Budapest, Hungary (Virtual) %B EC '21 %E Biró, Péter; Chawla, Shuchi; Echenique, Federico; Sodomka, Eric %P 310 - 311 %I ACM %@ 978-1-4503-8554-1

[34]

M. Cheraghchi and V. Nakos, “Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time,” in FOCS 2020, 61st Annual IEEE Symposium on Foundations of Computer Science, Durham, NC, USA (Virtual Conference), 2021.

Links

Export

BibTeX

@inproceedings{Cheraghchi_FOCS2020, TITLE = {Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time}, AUTHOR = {Cheraghchi, Mahdi and Nakos, Vasileios}, LANGUAGE = {eng}, ISBN = {978-1-7281-9621-3}, DOI = {10.1109/FOCS46700.2020}, PUBLISHER = {IEEE}, YEAR = {2020}, MARGINALMARK = {$\bullet$}, DATE = {2021}, BOOKTITLE = {FOCS 2020, 61st Annual IEEE Symposium on Foundations of Computer Science}, PAGES = {1203--1213}, ADDRESS = {Durham, NC, USA (Virtual Conference)}, }

Endnote

%0 Conference Proceedings %A Cheraghchi, Mahdi %A Nakos, Vasileios %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time : %G eng %U http://hdl.handle.net/21.11116/0000-0007-56C6-9 %R 10.1109/FOCS46700.2020 %D 2021 %B 61st Annual IEEE Symposium on Foundations of Computer Science %Z date of event: 2020-11-16 - 2020-11-19 %C Durham, NC, USA (Virtual Conference) %B FOCS 2020 %P 1203 - 1213 %I IEEE %@ 978-1-7281-9621-3

[35]

C. Coupette, J. Singh, and H. Spamann, “Simplify Your Law: Using Information Theory to Deduplicate Legal Documents,” in 21st IEEE International Conference on Data Mining Workshops (ICDMW 2021), Virtual Conference, 2021.

Links

Export

BibTeX

@inproceedings{CoupetteICDMW21, TITLE = {Simplify Your Law: Using Information Theory to Deduplicate Legal Documents}, AUTHOR = {Coupette, Corinna and Singh, Jyotsna and Spamann, Holger}, LANGUAGE = {eng}, ISBN = {978-1-6654-2428-8}, DOI = {10.1109/ICDMW53433.2021.00083}, PUBLISHER = {IEEE}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, DATE = {2021}, BOOKTITLE = {21st IEEE International Conference on Data Mining Workshops (ICDMW 2021)}, EDITOR = {Xue, Bing and Pechenizkiy, Mykola and Koh, Yun Sing}, PAGES = {631--638}, ADDRESS = {Virtual Conference}, }

Endnote

%0 Conference Proceedings %A Coupette, Corinna %A Singh, Jyotsna %A Spamann, Holger %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Simplify Your Law: Using Information Theory to Deduplicate Legal Documents : %G eng %U http://hdl.handle.net/21.11116/0000-000A-5E10-B %R 10.1109/ICDMW53433.2021.00083 %D 2021 %B 21st IEEE International Conference on Data Mining Workshops %Z date of event: 2021-12-07 - 2021-12-10 %C Virtual Conference %B 21st IEEE International Conference on Data Mining Workshops %E Xue, Bing; Pechenizkiy, Mykola; Koh, Yun Sing %P 631 - 638 %I IEEE %@ 978-1-6654-2428-8

[36]

C. Coupette, J. Beckedorf, D. Hartung, M. Bommarito, and D. M. Katz, “Measuring Law Over Time: A Network Analytical Framework with an Application to Statutes and Regulations in the United States and Germany,” Frontiers in Physics, vol. 9, 2021.

Links

Export

BibTeX

@article{Coupette2021, TITLE = {Measuring Law Over Time: {A} Network Analytical Framework with an Application to Statutes and Regulations in the {United States} and {Germany}}, AUTHOR = {Coupette, Corinna and Beckedorf, Janis and Hartung, Dirk and Bommarito, Michael and Katz, Daniel Martin}, LANGUAGE = {eng}, ISSN = {2296-424X}, DOI = {10.3389/fphy.2021.658463}, PUBLISHER = {Frontiers Media}, ADDRESS = {Lausanne}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, JOURNAL = {Frontiers in Physics}, VOLUME = {9}, EID = {658463}, }

Endnote

%0 Journal Article %A Coupette, Corinna %A Beckedorf, Janis %A Hartung, Dirk %A Bommarito, Michael %A Katz, Daniel Martin %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations %T Measuring Law Over Time: A Network Analytical Framework with an Application to Statutes and Regulations in the United States and Germany : %G eng %U http://hdl.handle.net/21.11116/0000-0008-D8FA-B %R 10.3389/fphy.2021.658463 %7 2021 %D 2021 %J Frontiers in Physics %V 9 %Z sequence number: 658463 %I Frontiers Media %C Lausanne %@ false

[37]

C. Coupette and J. Vreeken, “Graph Similarity Description: How Are These Graphs Similar?,” in KDD ’21, 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, 2021.

Links

Export

BibTeX

@inproceedings{Coupette_KDD2021, TITLE = {Graph Similarity Description: {H}ow Are These Graphs Similar?}, AUTHOR = {Coupette, Corinna and Vreeken, Jilles}, LANGUAGE = {eng}, ISBN = {978-1-4503-8332-5}, DOI = {10.1145/3447548.3467257}, PUBLISHER = {ACM}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {KDD '21, 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining}, EDITOR = {Zhu, Fieda and Ooi, Beng, Chin and Miao, Chunyan and Cong, Gao and Tang, Jiliang and Derr, Tyler}, PAGES = {185--195}, ADDRESS = {Virtual Event, Singapore}, }

Endnote

%0 Conference Proceedings %A Coupette, Corinna %A Vreeken, Jilles %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Graph Similarity Description: How Are These Graphs Similar? : %G eng %U http://hdl.handle.net/21.11116/0000-0009-652C-5 %R 10.1145/3447548.3467257 %D 2021 %B 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining %Z date of event: 2021-08-14 - 2021-08-18 %C Virtual Event, Singapore %B KDD '21 %E Zhu, Fieda; Ooi, Beng, Chin; Miao, Chunyan; Cong, Gao; Tang, Jiliang; Derr, Tyler %P 185 - 195 %I ACM %@ 978-1-4503-8332-5

[38]

C. Coupette and C. Lenzen, “A Breezing Proof of the KMW Bound,” in Symposium on Simplicity in Algorithms (SOSA 2021), Alexandria, VA, USA (Virtual Conference), 2021.

Links

Export

BibTeX

@inproceedings{Coupette_SOSA2020, TITLE = {A Breezing Proof of the {KMW} Bound}, AUTHOR = {Coupette, Corinna and Lenzen, Christoph}, LANGUAGE = {eng}, ISBN = {978-1-61197-649-6}, DOI = {10.1137/1.9781611976496.21}, PUBLISHER = {SIAM}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {Symposium on Simplicity in Algorithms (SOSA 2021)}, EDITOR = {King, Valerie and Viet Le, Hung}, PAGES = {184--195}, ADDRESS = {Alexandria, VA, USA (Virtual Conference)}, }

Endnote

%0 Conference Proceedings %A Coupette, Corinna %A Lenzen, Christoph %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T A Breezing Proof of the KMW Bound : %G eng %U http://hdl.handle.net/21.11116/0000-0007-7A44-4 %R 10.1137/1.9781611976496.21 %D 2021 %B SIAM Symposium on Simplicity in Algorithms %Z date of event: 2021-01-11 - 2021-01-12 %C Alexandria, VA, USA (Virtual Conference) %B Symposium on Simplicity in Algorithms %E King, Valerie; Viet Le, Hung %P 184 - 195 %I SIAM %@ 978-1-61197-649-6

[39]

E. Cruciani, E. Natale, A. Nusser, and G. Scornavacca, “Phase Transition of the 2-Choices Dynamics on Core-Periphery Networks,” Distributed Computing, vol. 34, 2021.

Links

Export

BibTeX

@article{Cruciani_DC2021, TITLE = {Phase Transition of the 2-Choices Dynamics on Core-Periphery Networks}, AUTHOR = {Cruciani, Emilio and Natale, Emanuele and Nusser, Andr{\'e} and Scornavacca, Giacomo}, LANGUAGE = {eng}, ISSN = {0178-2770}, DOI = {10.1007/s00446-021-00396-5}, PUBLISHER = {Springer International}, ADDRESS = {Berlin}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, JOURNAL = {Distributed Computing}, VOLUME = {34}, PAGES = {207--225}, }

Endnote

%0 Journal Article %A Cruciani, Emilio %A Natale, Emanuele %A Nusser, André %A Scornavacca, Giacomo %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Phase Transition of the 2-Choices Dynamics on Core-Periphery Networks : %G eng %U http://hdl.handle.net/21.11116/0000-0008-BA11-3 %R 10.1007/s00446-021-00396-5 %7 2021 %D 2021 %J Distributed Computing %V 34 %& 207 %P 207 - 225 %I Springer International %C Berlin %@ false

[40]

O. Darwish, A. Elmasry, and J. Katajainen, “Memory-Adjustable Navigation Piles with Applications to Sorting and Convex Hulls,” ACM Transactions on Algorithms, vol. 17, no. 2, 2021.

Links

Export

BibTeX

@article{Darwish2021, TITLE = {Memory-Adjustable Navigation Piles with Applications to Sorting and Convex Hulls}, AUTHOR = {Darwish, Omar and Elmasry, Amr and Katajainen, Jyrki}, LANGUAGE = {eng}, ISSN = {1549-6325}, DOI = {10.1145/3452938}, PUBLISHER = {ACM}, ADDRESS = {New York, NY}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, JOURNAL = {ACM Transactions on Algorithms}, VOLUME = {17}, NUMBER = {2}, EID = {18}, }

Endnote

%0 Journal Article %A Darwish, Omar %A Elmasry, Amr %A Katajainen, Jyrki %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Memory-Adjustable Navigation Piles with Applications to Sorting and Convex Hulls : %G eng %U http://hdl.handle.net/21.11116/0000-0008-D8F2-3 %R 10.1145/3452938 %7 2021 %D 2021 %J ACM Transactions on Algorithms %V 17 %N 2 %Z sequence number: 18 %I ACM %C New York, NY %@ false

[41]

N. R. Dayama, M. Shiripour, A. Oulasvirta, E. Ivanko, and A. Karrenbauer, “Foraging-based Optimization of Menu Systems,” International Journal of Human-Computer Studies, vol. 151, 2021.

Links

Export

BibTeX

@article{Dayama2021, TITLE = {Foraging-based Optimization of Menu Systems}, AUTHOR = {Dayama, Niraj Ramesh and Shiripour, Morteza and Oulasvirta, Antti and Ivanko, Evgeny and Karrenbauer, Andreas}, LANGUAGE = {eng}, ISSN = {1071-5819}, DOI = {10.1016/j.ijhcs.2021.102624}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, DATE = {2021}, JOURNAL = {International Journal of Human-Computer Studies}, VOLUME = {151}, EID = {102624}, }

Endnote

%0 Journal Article %A Dayama, Niraj Ramesh %A Shiripour, Morteza %A Oulasvirta, Antti %A Ivanko, Evgeny %A Karrenbauer, Andreas %+ External Organizations External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Foraging-based Optimization of Menu Systems : %G eng %U http://hdl.handle.net/21.11116/0000-0008-9D57-6 %R 10.1016/j.ijhcs.2021.102624 %7 2021 %D 2021 %J International Journal of Human-Computer Studies %V 151 %Z sequence number: 102624 %I Elsevier %C Amsterdam %@ false

[42]

M. de Berg, S. Kisfaludi-Bak, M. Monemizadeh, and L. Theocharous, “Clique-Based Separators for Geometric Intersection Graphs,” in 32nd International Symposium on Algorithms and Computation (ISAAC 2021), Fukuoka, Japan, 2021.

Links

Export

BibTeX

@inproceedings{deBerg_ISAAC21, TITLE = {Clique-Based Separators for Geometric Intersection Graphs}, AUTHOR = {de Berg, Mark and Kisfaludi-Bak, S{\'a}ndor and Monemizadeh, Morteza and Theocharous, Leonidas}, LANGUAGE = {eng}, ISSN = {1868-8969}, ISBN = {978-3-95977-214-3}, URL = {urn:nbn:de:0030-drops-154556}, DOI = {10.4230/LIPIcs.ISAAC.2021.22}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, EDITOR = {Ahn, Hee-Kap and Sadakane, Kunihiko}, PAGES = {1--15}, EID = {22}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {212}, ADDRESS = {Fukuoka, Japan}, }

Endnote

%0 Conference Proceedings %A de Berg, Mark %A Kisfaludi-Bak, Sándor %A Monemizadeh, Morteza %A Theocharous, Leonidas %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Clique-Based Separators for Geometric Intersection Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B811-4 %R 10.4230/LIPIcs.ISAAC.2021.22 %U urn:nbn:de:0030-drops-154556 %D 2021 %B 32nd International Symposium on Algorithms and Computation %Z date of event: 2021-12-06 - 2021-12-08 %C Fukuoka, Japan %B 32nd International Symposium on Algorithms and Computation %E Ahn, Hee-Kap; Sadakane, Kunihiko %P 1 - 15 %Z sequence number: 22 %I Schloss Dagstuhl %@ 978-3-95977-214-3 %B Leibniz International Proceedings in Informatics %N 212 %@ false

[43]

I. Diakonikolas, T. Gouleakis, D. M. Kane, J. Peebles, and E. Price, “Optimal Testing of Discrete Distributions with High Probability,” in STOC ’21, 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual, Italy, 2021.

Links

Export

BibTeX

@inproceedings{Diakonikolas_STOC2021, TITLE = {Optimal Testing of Discrete Distributions with High Probability}, AUTHOR = {Diakonikolas, Ilias and Gouleakis, Themis and Kane, Daniel M. and Peebles, John and Price, Eric}, LANGUAGE = {eng}, ISBN = {9781450380539}, DOI = {10.1145/3406325.3450997}, PUBLISHER = {ACM}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {STOC '21, 53rd Annual ACM SIGACT Symposium on Theory of Computing}, EDITOR = {Khuller, Samir and Vassilevska Williams, Virginia}, PAGES = {542--555}, ADDRESS = {Virtual, Italy}, }

Endnote

%0 Conference Proceedings %A Diakonikolas, Ilias %A Gouleakis, Themis %A Kane, Daniel M. %A Peebles, John %A Price, Eric %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Optimal Testing of Discrete Distributions with High Probability : %G eng %U http://hdl.handle.net/21.11116/0000-000A-CD4F-8 %R 10.1145/3406325.3450997 %D 2021 %B 53rd Annual ACM SIGACT Symposium on Theory of Computing %Z date of event: 2021-06-21 - 2021-06-25 %C Virtual, Italy %B STOC '21 %E Khuller, Samir; Vassilevska Williams, Virginia %P 542 - 555 %I ACM %@ 9781450380539

[44]

J. Dörfler, M. Roth, J. Schmitt, and P. Wellnitz, “Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness,” Algorithmica, 2021.

Links

Export

BibTeX

@article{Doerfler2021, TITLE = {Counting Induced Subgraphs: {A}n Algebraic Approach to \#{W}[1]-hardness}, AUTHOR = {D{\"o}rfler, Julian and Roth, Marc and Schmitt, Johannes and Wellnitz, Philip}, LANGUAGE = {eng}, ISSN = {0178-4617}, DOI = {10.1007/s00453-021-00894-9}, PUBLISHER = {Springer-Verlag}, ADDRESS = {New York}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, JOURNAL = {Algorithmica}, }

Endnote

%0 Journal Article %A Dörfler, Julian %A Roth, Marc %A Schmitt, Johannes %A Wellnitz, Philip %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness : %G eng %U http://hdl.handle.net/21.11116/0000-0009-A583-8 %R 10.1007/s00453-021-00894-9 %7 2021 %D 2021 %J Algorithmica %I Springer-Verlag %C New York %@ false

[45]

A. Driemel, A. Nusser, J. M. Phillips, and I. Psarros, “The VC Dimension of Metric Balls under Fréchet and Hausdorff Distances,” Discrete & Computational Geometry, 2021.

Links

Export

BibTeX

@article{Driemel21, TITLE = {The {VC} Dimension of Metric Balls under {F}r\'{e}chet and {H}ausdorff Distances}, AUTHOR = {Driemel, Anne and Nusser, Andr{\'e} and Phillips, Jeff M. and Psarros, Ioannis}, LANGUAGE = {eng}, ISSN = {0179-5376}, DOI = {10.1007/s00454-021-00318-z}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, JOURNAL = {Discrete \& Computational Geometry}, }

Endnote

%0 Journal Article %A Driemel, Anne %A Nusser, André %A Phillips, Jeff M. %A Psarros, Ioannis %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T The VC Dimension of Metric Balls under Fréchet and Hausdorff Distances : %G eng %U http://hdl.handle.net/21.11116/0000-0009-414C-9 %R 10.1007/s00454-021-00318-z %7 2021 %D 2021 %J Discrete & Computational Geometry %I Springer %C New York, NY %@ false

[46]

M. Dyer, C. Greenhill, P. Kleer, J. Ross, and L. Stougie, “Sampling Hypergraphs with Given Degrees,” Discrete Mathematics, vol. 344, no. 11, 2021.

Links

Export

BibTeX

@article{Dyer2021, TITLE = {Sampling Hypergraphs with Given Degrees}, AUTHOR = {Dyer, Martin and Greenhill, Catherine and Kleer, Pieter and Ross, James and Stougie, Leen}, LANGUAGE = {eng}, ISSN = {0012-365X}, DOI = {10.1016/j.disc.2021.112566}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, DATE = {2021}, JOURNAL = {Discrete Mathematics}, VOLUME = {344}, NUMBER = {11}, EID = {112566}, }

Endnote

%0 Journal Article %A Dyer, Martin %A Greenhill, Catherine %A Kleer, Pieter %A Ross, James %A Stougie, Leen %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Sampling Hypergraphs with Given Degrees : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B820-3 %R 10.1016/j.disc.2021.112566 %7 2021 %D 2021 %J Discrete Mathematics %V 344 %N 11 %Z sequence number: 112566 %I Elsevier %C Amsterdam %@ false

[47]

A. M. Feit, M. Nancel, M. John, A. Karrenbauer, D. Weir, and A. Oulasvirta, “AZERTY Amélioré: Computational Design on a National Scale,” Communications of the ACM, vol. 64, no. 2, 2021.

Links

Export

BibTeX

@article{FNJKWO2021, TITLE = {{AZERTY} Am\'{e}lior\'{e}: {C}omputational Design on a National Scale}, AUTHOR = {Feit, Anna Maria and Nancel, Mathieu and John, Maximilian and Karrenbauer, Andreas and Weir, Daryl and Oulasvirta, Antti}, LANGUAGE = {eng}, ISSN = {0001-0782}, DOI = {10.1145/3382035}, PUBLISHER = {Association for Computing Machinery, Inc.}, ADDRESS = {New York}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, JOURNAL = {Communications of the ACM}, VOLUME = {64}, NUMBER = {2}, PAGES = {48--58}, }

Endnote

%0 Journal Article %A Feit, Anna Maria %A Nancel, Mathieu %A John, Maximilian %A Karrenbauer, Andreas %A Weir, Daryl %A Oulasvirta, Antti %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T AZERTY Amélioré: Computational Design on a National Scale : %G eng %U http://hdl.handle.net/21.11116/0000-0007-E78E-5 %R 10.1145/3382035 %7 2021 %D 2021 %K {F}r\'{e}chet %J Communications of the ACM %V 64 %N 2 %& 48 %P 48 - 58 %I Association for Computing Machinery, Inc. %C New York %@ false

[48]

F. Folz, K. Mehlhorn, and G. Morigi, “Interplay of Periodic Dynamics and Noise: Insights from a Simple Adaptive System,” Physical Review E, vol. 104, no. 5, 2021.

Links

Export

BibTeX

@article{Folz2021, TITLE = {Interplay of Periodic Dynamics and Noise: {I}nsights from a Simple Adaptive System}, AUTHOR = {Folz, Frederic and Mehlhorn, Kurt and Morigi, Giovanna}, LANGUAGE = {eng}, ISSN = {1539-3755}, DOI = {10.1103/PhysRevE.104.054215}, PUBLISHER = {American Physical Society}, ADDRESS = {Melville, NY}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, DATE = {2021}, JOURNAL = {Physical Review E}, VOLUME = {104}, NUMBER = {5}, EID = {054215}, }

Endnote

%0 Journal Article %A Folz, Frederic %A Mehlhorn, Kurt %A Morigi, Giovanna %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Interplay of Periodic Dynamics and Noise: Insights from a Simple Adaptive System : %G eng %U http://hdl.handle.net/21.11116/0000-0009-9D3F-1 %R 10.1103/PhysRevE.104.054215 %7 2021 %D 2021 %J Physical Review E %O Phys. Rev. E %V 104 %N 5 %Z sequence number: 054215 %I American Physical Society %C Melville, NY %@ false

[49]

J. Giliberti and A. Karrenbauer, “Improved Online Algorithm for Fractional Knapsack in the Random Order Model,” 2021. [Online]. Available: https://arxiv.org/abs/2109.04428. (arXiv: 2109.04428)

Abstract

The fractional knapsack problem is one of the classical problems in combinatorial optimization, which is well understood in the offline setting. However, the corresponding online setting has been handled only briefly in the theoretical computer science literature so far, although it appears in several applications. Even the previously best known guarantee for the competitive ratio was worse than the best known for the integral problem in the popular random order model. We show that there is an algorithm for the online fractional knapsack problem that admits a competitive ratio of 4.39. Our result significantly improves over the previously best known competitive ratio of 9.37 and surpasses the current best 6.65-competitive algorithm for the integral case. Moreover, our algorithm is deterministic in contrast to the randomized algorithms achieving the results mentioned above.

Links

Export

BibTeX

@online{Gilberti2109.04428, TITLE = {Improved Online Algorithm for Fractional Knapsack in the Random Order Model}, AUTHOR = {Giliberti, Jeff and Karrenbauer, Andreas}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2109.04428}, EPRINT = {2109.04428}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {The fractional knapsack problem is one of the classical problems in combinatorial optimization, which is well understood in the offline setting. However, the corresponding online setting has been handled only briefly in the theoretical computer science literature so far, although it appears in several applications. Even the previously best known guarantee for the competitive ratio was worse than the best known for the integral problem in the popular random order model. We show that there is an algorithm for the online fractional knapsack problem that admits a competitive ratio of 4.39. Our result significantly improves over the previously best known competitive ratio of 9.37 and surpasses the current best 6.65-competitive algorithm for the integral case. Moreover, our algorithm is deterministic in contrast to the randomized algorithms achieving the results mentioned above. }, }

Endnote

%0 Report %A Giliberti, Jeff %A Karrenbauer, Andreas %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Improved Online Algorithm for Fractional Knapsack in the Random Order Model : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B637-C %U https://arxiv.org/abs/2109.04428 %D 2021 %X The fractional knapsack problem is one of the classical problems in combinatorial optimization, which is well understood in the offline setting. However, the corresponding online setting has been handled only briefly in the theoretical computer science literature so far, although it appears in several applications. Even the previously best known guarantee for the competitive ratio was worse than the best known for the integral problem in the popular random order model. We show that there is an algorithm for the online fractional knapsack problem that admits a competitive ratio of 4.39. Our result significantly improves over the previously best known competitive ratio of 9.37 and surpasses the current best 6.65-competitive algorithm for the integral case. Moreover, our algorithm is deterministic in contrast to the randomized algorithms achieving the results mentioned above. %K Computer Science, Data Structures and Algorithms, cs.DS

[50]

M. Grohe, D. Neuen, and D. Wiebking, “Isomorphism Testing for Graphs Excluding Small Minors,” in FOCS 2020, 61st Annual IEEE Symposium on Foundations of Computer Science, Durham, NC, USA (Virtual Conference), 2021.

Links

Export

BibTeX

@inproceedings{Grohe_FOCS2020, TITLE = {Isomorphism Testing for Graphs Excluding Small Minors}, AUTHOR = {Grohe, Martin and Neuen, Daniel and Wiebking, Daniel}, LANGUAGE = {eng}, ISBN = {978-1-7281-9621-3}, DOI = {10.1109/FOCS46700.2020.00064}, PUBLISHER = {IEEE}, YEAR = {2020}, MARGINALMARK = {$\bullet$}, DATE = {2021}, BOOKTITLE = {FOCS 2020, 61st Annual IEEE Symposium on Foundations of Computer Science}, PAGES = {625--636}, ADDRESS = {Durham, NC, USA (Virtual Conference)}, }

Endnote

%0 Conference Proceedings %A Grohe, Martin %A Neuen, Daniel %A Wiebking, Daniel %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Isomorphism Testing for Graphs Excluding Small Minors : %G eng %U http://hdl.handle.net/21.11116/0000-0007-9947-D %R 10.1109/FOCS46700.2020.00064 %D 2021 %B 61st Annual IEEE Symposium on Foundations of Computer Science %Z date of event: 2020-11-16 - 2020-11-19 %C Durham, NC, USA (Virtual Conference) %B FOCS 2020 %P 625 - 636 %I IEEE %@ 978-1-7281-9621-3

[51]

P. Kleer and H. U. Simon, “Primal and Dual Combinatorial Dimensions,” 2021. [Online]. Available: https://arxiv.org/abs/2108.10037. (arXiv: 2108.10037)

Abstract

We give tight bounds on the relation between the primal and dual of various combinatorial dimensions, such as the pseudo-dimension and fat-shattering dimension, for multi-valued function classes. These dimensional notions play an important role in the area of learning theory. We first review some (folklore) results that bound the dual dimension of a function class in terms of its primal, and after that give (almost) matching lower bounds. In particular, we give an appropriate generalization to multi-valued function classes of a well-known bound due to Assouad (1983), that relates the primal and dual VC-dimension of a binary function class.

Links

Export

BibTeX

@online{Kleer_2108.10037, TITLE = {Primal and Dual Combinatorial Dimensions}, AUTHOR = {Kleer, Pieter and Simon, Hans Ulrich}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2108.10037}, EPRINT = {2108.10037}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We give tight bounds on the relation between the primal and dual of various combinatorial dimensions, such as the pseudo-dimension and fat-shattering dimension, for multi-valued function classes. These dimensional notions play an important role in the area of learning theory. We first review some (folklore) results that bound the dual dimension of a function class in terms of its primal, and after that give (almost) matching lower bounds. In particular, we give an appropriate generalization to multi-valued function classes of a well-known bound due to Assouad (1983), that relates the primal and dual VC-dimension of a binary function class. }, }

Endnote

%0 Report %A Kleer, Pieter %A Simon, Hans Ulrich %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Primal and Dual Combinatorial Dimensions : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B834-D %U https://arxiv.org/abs/2108.10037 %D 2021 %X We give tight bounds on the relation between the primal and dual of various combinatorial dimensions, such as the pseudo-dimension and fat-shattering dimension, for multi-valued function classes. These dimensional notions play an important role in the area of learning theory. We first review some (folklore) results that bound the dual dimension of a function class in terms of its primal, and after that give (almost) matching lower bounds. In particular, we give an appropriate generalization to multi-valued function classes of a well-known bound due to Assouad (1983), that relates the primal and dual VC-dimension of a binary function class. %K Mathematics, Combinatorics, math.CO,Computer Science, Discrete Mathematics, cs.DM,Computer Science, Learning, cs.LG

[52]

P. Kleer, “Sampling from the Gibbs Distribution in Congestion Games,” in EC ’21, 22nd ACM Conference on Economics and Computation, Budapest, Hungary (Virtual), 2021.

Links

Export

BibTeX

@inproceedings{Kleer_EC2021, TITLE = {Sampling from the {G}ibbs Distribution in Congestion Games}, AUTHOR = {Kleer, Pieter}, LANGUAGE = {eng}, ISBN = {978-1-4503-8554-1}, DOI = {10.1145/3465456.3467597}, PUBLISHER = {ACM}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {EC '21, 22nd ACM Conference on Economics and Computation}, EDITOR = {Bir{\'o}, P{\'e}ter and Chawla, Shuchi and Echenique, Federico and Sodomka, Eric}, PAGES = {679--680}, ADDRESS = {Budapest, Hungary (Virtual)}, }

Endnote

%0 Conference Proceedings %A Kleer, Pieter %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Sampling from the Gibbs Distribution in Congestion Games : %G eng %U http://hdl.handle.net/21.11116/0000-0009-B3F8-5 %R 10.1145/3465456.3467597 %D 2021 %B 22nd ACM Conference on Economics and Computation %Z date of event: 2021-07-18 - 2021-07-23 %C Budapest, Hungary (Virtual) %B EC '21 %E Biró, Péter; Chawla, Shuchi; Echenique, Federico; Sodomka, Eric %P 679 - 680 %I ACM %@ 978-1-4503-8554-1

[53]

P. Kleer, “Sampling from the Gibbs Distribution in Congestion Games,” 2021. [Online]. Available: https://arxiv.org/abs/2105.12982. (arXiv: 2105.12982)

Abstract

Logit dynamics is a form of randomized game dynamics where players have a bias towards strategic deviations that give a higher improvement in cost. It is used extensively in practice. In congestion (or potential) games, the dynamics converges to the so-called Gibbs distribution over the set of all strategy profiles, when interpreted as a Markov chain. In general, logit dynamics might converge slowly to the Gibbs distribution, but beyond that, not much is known about their algorithmic aspects, nor that of the Gibbs distribution. In this work, we are interested in the following two questions for congestion games: i) Is there an efficient algorithm for sampling from the Gibbs distribution? ii) If yes, do there also exist natural randomized dynamics that converges quickly to the Gibbs distribution? We first study these questions in extension parallel congestion games, a well-studied special case of symmetric network congestion games. As our main result, we show that there is a simple variation on the logit dynamics (in which we in addition are allowed to randomly interchange the strategies of two players) that converges quickly to the Gibbs distribution in such games. This answers both questions above affirmatively. We also address the first question for the class of so-called capacitated $k$-uniform congestion games. To prove our results, we rely on the recent breakthrough work of Anari, Liu, Oveis-Gharan and Vinzant (2019) concerning the approximate sampling of the base of a matroid according to strongly log-concave probability distribution.

Links

Export

BibTeX

@online{Kleer_2105.12982, TITLE = {Sampling from the {G}ibbs Distribution in Congestion Games}, AUTHOR = {Kleer, Pieter}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2105.12982}, EPRINT = {2105.12982}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {Logit dynamics is a form of randomized game dynamics where players have a bias towards strategic deviations that give a higher improvement in cost. It is used extensively in practice. In congestion (or potential) games, the dynamics converges to the so-called Gibbs distribution over the set of all strategy profiles, when interpreted as a Markov chain. In general, logit dynamics might converge slowly to the Gibbs distribution, but beyond that, not much is known about their algorithmic aspects, nor that of the Gibbs distribution. In this work, we are interested in the following two questions for congestion games: i) Is there an efficient algorithm for sampling from the Gibbs distribution? ii) If yes, do there also exist natural randomized dynamics that converges quickly to the Gibbs distribution? We first study these questions in extension parallel congestion games, a well-studied special case of symmetric network congestion games. As our main result, we show that there is a simple variation on the logit dynamics (in which we in addition are allowed to randomly interchange the strategies of two players) that converges quickly to the Gibbs distribution in such games. This answers both questions above affirmatively. We also address the first question for the class of so-called capacitated $k$-uniform congestion games. To prove our results, we rely on the recent breakthrough work of Anari, Liu, Oveis-Gharan and Vinzant (2019) concerning the approximate sampling of the base of a matroid according to strongly log-concave probability distribution. }, }

Endnote

%0 Report %A Kleer, Pieter %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Sampling from the Gibbs Distribution in Congestion Games : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E54C-1 %U https://arxiv.org/abs/2105.12982 %D 2021 %X Logit dynamics is a form of randomized game dynamics where players have a bias towards strategic deviations that give a higher improvement in cost. It is used extensively in practice. In congestion (or potential) games, the dynamics converges to the so-called Gibbs distribution over the set of all strategy profiles, when interpreted as a Markov chain. In general, logit dynamics might converge slowly to the Gibbs distribution, but beyond that, not much is known about their algorithmic aspects, nor that of the Gibbs distribution. In this work, we are interested in the following two questions for congestion games: i) Is there an efficient algorithm for sampling from the Gibbs distribution? ii) If yes, do there also exist natural randomized dynamics that converges quickly to the Gibbs distribution? We first study these questions in extension parallel congestion games, a well-studied special case of symmetric network congestion games. As our main result, we show that there is a simple variation on the logit dynamics (in which we in addition are allowed to randomly interchange the strategies of two players) that converges quickly to the Gibbs distribution in such games. This answers both questions above affirmatively. We also address the first question for the class of so-called capacitated $k$-uniform congestion games. To prove our results, we rely on the recent breakthrough work of Anari, Liu, Oveis-Gharan and Vinzant (2019) concerning the approximate sampling of the base of a matroid according to strongly log-concave probability distribution. %K Computer Science, Computer Science and Game Theory, cs.GT,Computer Science, Discrete Mathematics, cs.DM,Computer Science, Data Structures and Algorithms, cs.DS

[54]

P. Kleer and G. Schäfer, “Computation and Efficiency of Potential Function Minimizers of Combinatorial Congestion Games,” Mathematical Programming, vol. 190, no. 1, 2021.

Links

Export

BibTeX

@article{Kleer2020, TITLE = {Computation and Efficiency of Potential Function Minimizers of Combinatorial Congestion Games}, AUTHOR = {Kleer, Pieter and Sch{\"a}fer, Guido}, LANGUAGE = {eng}, DOI = {10.1007/s10107-020-01546-6}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, DATE = {2021}, JOURNAL = {Mathematical Programming}, VOLUME = {190}, NUMBER = {1}, PAGES = {523--560}, }

Endnote

%0 Journal Article %A Kleer, Pieter %A Schäfer, Guido %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Computation and Efficiency of Potential Function Minimizers of Combinatorial Congestion Games : %G eng %U http://hdl.handle.net/21.11116/0000-0006-F285-2 %R 10.1007/s10107-020-01546-6 %7 2020 %D 2021 %J Mathematical Programming %V 190 %N 1 %& 523 %P 523 - 560 %I Springer %C New York, NY

[55]

C. Lenzen and H. Vahidi, “Approximate Minimum Directed Spanning Trees Under Congestion,” in Structural Information and Communication Complexity (SIROCCO 2021), Wrocław, Poland (Online), 2021.

Links

Export

BibTeX

@inproceedings{Lenzen_SIROCCO21, TITLE = {Approximate Minimum Directed Spanning Trees Under Congestion}, AUTHOR = {Lenzen, Christoph and Vahidi, Hossein}, LANGUAGE = {eng}, ISBN = {978-3-030-79526-9}, DOI = {10.1007/978-3-030-79527-6_20}, PUBLISHER = {Springer}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, DATE = {2021}, BOOKTITLE = {Structural Information and Communication Complexity (SIROCCO 2021)}, EDITOR = {Jurdzi{\'n}ski, Tomasz and Schmid, Stefan}, PAGES = {352--369}, SERIES = {Lecture Notes in Computer Science}, VOLUME = {12810}, ADDRESS = {Wroc{\l}aw, Poland (Online)}, }

Endnote

%0 Conference Proceedings %A Lenzen, Christoph %A Vahidi, Hossein %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Approximate Minimum Directed Spanning Trees Under Congestion : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E553-8 %R 10.1007/978-3-030-79527-6_20 %D 2021 %B 28th International Colloquium on Structural Information and Communication Complexity %Z date of event: 2021-06-28 - 2021-07-01 %C Wrocław, Poland (Online) %B Structural Information and Communication Complexity %E Jurdziński, Tomasz; Schmid, Stefan %P 352 - 369 %I Springer %@ 978-3-030-79526-9 %B Lecture Notes in Computer Science %N 12810

[56]

D. Lokshtanov, P. Misra, J. Mukherjee, F. Panolan, G. Philip, and S. Saurabh, “2-Approximating Feedback Vertex Set in Tournaments,” ACM Transactions on Algorithms, vol. 17, no. 2, 2021.

Links

Export

BibTeX

@article{Lokshtanov2021, TITLE = {2-Approximating Feedback Vertex Set in Tournaments}, AUTHOR = {Lokshtanov, Daniel and Misra, Pranabendu and Mukherjee, Joydeep and Panolan, Fahad and Philip, Geevarghese and Saurabh, Saket}, LANGUAGE = {eng}, ISSN = {1549-6325}, DOI = {10.1145/3446969}, PUBLISHER = {ACM}, ADDRESS = {New York, NY}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, JOURNAL = {ACM Transactions on Algorithms}, VOLUME = {17}, NUMBER = {2}, EID = {11}, }

Endnote

%0 Journal Article %A Lokshtanov, Daniel %A Misra, Pranabendu %A Mukherjee, Joydeep %A Panolan, Fahad %A Philip, Geevarghese %A Saurabh, Saket %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations %T 2-Approximating Feedback Vertex Set in Tournaments : %G eng %U http://hdl.handle.net/21.11116/0000-0008-D8F8-D %R 10.1145/3446969 %7 2021 %D 2021 %J ACM Transactions on Algorithms %V 17 %N 2 %Z sequence number: 11 %I ACM %C New York, NY %@ false

[57]

D. Lokshtanov, P. Misra, M. S. Ramanujan, S. Saurabh, and M. Zehavi, “FPT-approximation for FPT Problems,” in Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, VA, USA (Virtual Conference), 2021.

Links

Export

BibTeX

@inproceedings{FPTApprox21, TITLE = {{FPT}-approximation for {FPT} Problems}, AUTHOR = {Lokshtanov, Daniel and Misra, Pranabendu and Ramanujan, M. S. and Saurabh, Saket and Zehavi, Meirav}, LANGUAGE = {eng}, ISBN = {978-1-61197-646-5}, DOI = {10.1137/1.9781611976465.14}, PUBLISHER = {SIAM}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, DATE = {2021}, BOOKTITLE = {Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)}, EDITOR = {Marx, D{\'a}niel}, PAGES = {199--218}, ADDRESS = {Alexandria, VA, USA (Virtual Conference)}, }

Endnote

%0 Conference Proceedings %A Lokshtanov, Daniel %A Misra, Pranabendu %A Ramanujan, M. S. %A Saurabh, Saket %A Zehavi, Meirav %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T FPT-approximation for FPT Problems : %G eng %U http://hdl.handle.net/21.11116/0000-0007-D2AE-8 %R 10.1137/1.9781611976465.14 %D 2021 %B 32nd Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2021-01-10 - 2021-01-13 %C Alexandria, VA, USA (Virtual Conference) %B Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms %E Marx, Dániel %P 199 - 218 %I SIAM %@ 978-1-61197-646-5

[58]

J. Madathil, R. Sharma, and M. Zehavi, “A Sub-exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs,” Algorithmica, vol. 83, 2021.

Links

Export

BibTeX

@article{Madathil2021, TITLE = {A Sub-exponential {FPT} Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs}, AUTHOR = {Madathil, Jayakrishnan and Sharma, Roohani and Zehavi, Meirav}, LANGUAGE = {eng}, ISSN = {0178-4617}, DOI = {10.1007/s00453-021-00806-x}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, JOURNAL = {Algorithmica}, VOLUME = {83}, PAGES = {1861--1884}, }

Endnote

%0 Journal Article %A Madathil, Jayakrishnan %A Sharma, Roohani %A Zehavi, Meirav %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T A Sub-exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs : %G eng %U http://hdl.handle.net/21.11116/0000-0008-2C54-9 %R 10.1007/s00453-021-00806-x %7 2021 %D 2021 %J Algorithmica %V 83 %& 1861 %P 1861 - 1884 %I Springer %C New York, NY %@ false

[59]

J. Nederlof and K. Węgrzycki, “Improving Schroeppel and Shamir’s Algorithm for Subset Sum via Orthogonal Vectors,” in STOC ’21, 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual, Italy, 2021.

Links

Export

BibTeX

@inproceedings{Nederlof_STOC2021, TITLE = {Improving {S}chroeppel and {S}hamir's Algorithm for Subset Sum via Orthogonal Vectors}, AUTHOR = {Nederlof, Jesper and W{\c e}grzycki, Karol}, LANGUAGE = {eng}, ISBN = {9781450380539}, DOI = {10.1145/3406325.3451024}, PUBLISHER = {ACM}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {STOC '21, 53rd Annual ACM SIGACT Symposium on Theory of Computing}, EDITOR = {Khuller, Samir and Vassilevska Williams, Virginia}, PAGES = {1670--1683}, ADDRESS = {Virtual, Italy}, }

Endnote

%0 Conference Proceedings %A Nederlof, Jesper %A Węgrzycki, Karol %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors : %G eng %U http://hdl.handle.net/21.11116/0000-000A-CD68-B %R 10.1145/3406325.3451024 %D 2021 %B 53rd Annual ACM SIGACT Symposium on Theory of Computing %Z date of event: 2021-06-21 - 2021-06-25 %C Virtual, Italy %B STOC '21 %E Khuller, Samir; Vassilevska Williams, Virginia %P 1670 - 1683 %I ACM %@ 9781450380539

[60]

A. S. Nittala, A. Karrenbauer, A. Khan, T. Kraus, and J. Steimle, “Computational Design and Optimization of Electro-physiological Sensors,” Nature Communications, vol. 12, no. 1, 2021.

Links

Export

BibTeX

@article{Nittala2021, TITLE = {Computational Design and Optimization of Electro-physiological Sensors}, AUTHOR = {Nittala, Aditya Shekhar and Karrenbauer, Andreas and Khan, Arshad and Kraus, Tobias and Steimle, J{\"u}rgen}, LANGUAGE = {eng}, ISSN = {2041-1723}, DOI = {10.1038/s41467-021-26442-1}, PUBLISHER = {Nature Publishing Group}, ADDRESS = {London}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, DATE = {2021}, JOURNAL = {Nature Communications}, VOLUME = {12}, NUMBER = {1}, EID = {6351}, }

Endnote

%0 Journal Article %A Nittala, Aditya Shekhar %A Karrenbauer, Andreas %A Khan, Arshad %A Kraus, Tobias %A Steimle, Jürgen %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Computational Design and Optimization of Electro-physiological Sensors : %G eng %U http://hdl.handle.net/21.11116/0000-0009-7E62-C %R 10.1038/s41467-021-26442-1 %7 2021 %D 2021 %J Nature Communications %O Nat. Commun. %V 12 %N 1 %Z sequence number: 6351 %I Nature Publishing Group %C London %@ false

[61]

A. Pandey, “Variety Membership Testing in Algebraic Complexity Theory,” Universität des Saarlandes, Saarbrücken, 2021.

Links

Export

BibTeX

@phdthesis{Pandeyphd2021, TITLE = {Variety Membership Testing in Algebraic Complexity Theory}, AUTHOR = {Pandey, Anurag}, LANGUAGE = {eng}, URL = {urn:nbn:de:bsz:291--ds-342440}, DOI = {10.22028/D291-34244}, SCHOOL = {Universit{\"a}t des Saarlandes}, ADDRESS = {Saarbr{\"u}cken}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, DATE = {2021}, }

Endnote

%0 Thesis %A Pandey, Anurag %Y Bläser, Markus %A referee: Ikenmeyer, Christian %A referee: Mahajan, Meena %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society International Max Planck Research School, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Variety Membership Testing in Algebraic Complexity Theory : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E9F5-D %R 10.22028/D291-34244 %F OTHER: hdl:20.500.11880/31479 %U urn:nbn:de:bsz:291--ds-342440 %I Universität des Saarlandes %C Saarbrücken %D 2021 %P 128 p. %V phd %9 phd %U https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/31479

[62]

A. Polak, L. Rohwedder, and K. Węgrzycki, “Knapsack and Subset Sum with Small Items,” in 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Glasgow, UK (Virtual Conference), 2021.

Links

Export

BibTeX

@inproceedings{Polak_ICALP2021, TITLE = {Knapsack and Subset Sum with Small Items}, AUTHOR = {Polak, Adam and Rohwedder, Lars and W{\c e}grzycki, Karol}, LANGUAGE = {eng}, ISSN = {1868-8969}, ISBN = {978-3-95977-195-5}, URL = {urn:nbn:de:0030-drops-141752; https://drops.dagstuhl.de/opus/volltexte/2021/14175/}, DOI = {10.4230/LIPIcs.ICALP.2021.106}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, EDITOR = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, PAGES = {1--19}, EID = {106}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {198}, ADDRESS = {Glasgow, UK (Virtual Conference)}, }

Endnote

%0 Conference Proceedings %A Polak, Adam %A Rohwedder, Lars %A Węgrzycki, Karol %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Knapsack and Subset Sum with Small Items : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1EEF-7 %R 10.4230/LIPIcs.ICALP.2021.106 %U urn:nbn:de:0030-drops-141752 %U https://drops.dagstuhl.de/opus/volltexte/2021/14175/ %D 2021 %B 48th International Colloquium on Automata, Languages, and Programming %Z date of event: 2021-07-12 - 2020-07-16 %C Glasgow, UK (Virtual Conference) %B 48th International Colloquium on Automata, Languages, and Programming %E Bansal, Nikhil; Merelli, Emanuela; Worrell, James %P 1 - 19 %Z sequence number: 106 %I Schloss Dagstuhl %@ 978-3-95977-195-5 %B Leibniz International Proceedings in Informatics %N 198 %@ false

[63]

B. Ray Chaudhury, J. Garg, and R. Mehta, “Fair and Efficient Allocations under Subadditive Valuations,” in AAAI Technical Track on Game Theory and Economic Paradigms, Virtual Conference, 2021.

Links

Export

BibTeX

@inproceedings{Chaudhury_AAAI21, TITLE = {Fair and Efficient Allocations under Subadditive Valuations}, AUTHOR = {Ray Chaudhury, Bhaskar and Garg, Jugal and Mehta, Ruta}, LANGUAGE = {eng}, ISBN = {978-1-57735-866-4}, URL = {https://ojs.aaai.org/index.php/AAAI/article/view/16665}, PUBLISHER = {AAAI}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {AAAI Technical Track on Game Theory and Economic Paradigms}, PAGES = {5269--5276}, ADDRESS = {Virtual Conference}, }

Endnote

%0 Conference Proceedings %A Ray Chaudhury, Bhaskar %A Garg, Jugal %A Mehta, Ruta %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Fair and Efficient Allocations under Subadditive Valuations : %G eng %U http://hdl.handle.net/21.11116/0000-0007-9370-4 %U https://ojs.aaai.org/index.php/AAAI/article/view/16665 %D 2021 %B Thirty-Fifth AAAI Conference on Artificial Intelligence %Z date of event: 2021-02-02 - 2021-02-09 %C Virtual Conference %B AAAI Technical Track on Game Theory and Economic Paradigms %P 5269 - 5276 %I AAAI %@ 978-1-57735-866-4 %U https://ojs.aaai.org/index.php/AAAI/article/view/16665

[64]

B. Ray Chaudhury, J. Garg, K. Mehlhorn, R. Mehta, and P. Misra, “Improving EFX Guarantees through Rainbow Cycle Number,” 2021. [Online]. Available: https://arxiv.org/abs/2103.01628. (arXiv: 2103.01628)

Abstract

We study the problem of fairly allocating a set of indivisible goods among $n$ agents with additive valuations. Envy-freeness up to any good (EFX) is arguably the most compelling fairness notion in this context. However, the existence of EFX allocations has not been settled and is one of the most important problems in fair division. Towards resolving this problem, many impressive results show the existence of its relaxations, e.g., the existence of $0.618$-EFX allocations, and the existence of EFX at most $n-1$ unallocated goods. The latter result was recently improved for three agents, in which the two unallocated goods are allocated through an involved procedure. Reducing the number of unallocated goods for arbitrary number of agents is a systematic way to settle the big question. In this paper, we develop a new approach, and show that for every $\varepsilon \in (0,1/2]$, there always exists a $(1-\varepsilon)$-EFX allocation with sublinear number of unallocated goods and high Nash welfare. For this, we reduce the EFX problem to a novel problem in extremal graph theory. We introduce the notion of rainbow cycle number $R(\cdot)$. For all $d \in \mathbb{N}$, $R(d)$ is the largest $k$ such that there exists a $k$-partite digraph $G =(\cup_{i \in [k]} V_i, E)$, in which 1) each part has at most $d$ vertices, i.e., $\lvert V_i \rvert \leq d$ for all $i \in [k]$, 2) for any two parts $V_i$ and $V_j$, each vertex in $V_i$ has an incoming edge from some vertex in $V_j$ and vice-versa, and 3) there exists no cycle in $G$ that contains at most one vertex from each part. We show that any upper bound on $R(d)$ directly translates to a sublinear bound on the number of unallocated goods. We establish a polynomial upper bound on $R(d)$, yielding our main result. Furthermore, our approach is constructive, which also gives a polynomial-time algorithm for finding such an allocation.

Links

Export

BibTeX

@online{RayChaudhury2103.01628, TITLE = {Improving {EFX} Guarantees through Rainbow Cycle Number}, AUTHOR = {Ray Chaudhury, Bhaskar and Garg, Jugal and Mehlhorn, Kurt and Mehta, Ruta and Misra, Pranabendu}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2103.01628}, EPRINT = {2103.01628}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We study the problem of fairly allocating a set of indivisible goods among $n$ agents with additive valuations. Envy-freeness up to any good (EFX) is arguably the most compelling fairness notion in this context. However, the existence of EFX allocations has not been settled and is one of the most important problems in fair division. Towards resolving this problem, many impressive results show the existence of its relaxations, e.g., the existence of $0.618$-EFX allocations, and the existence of EFX at most $n-1$ unallocated goods. The latter result was recently improved for three agents, in which the two unallocated goods are allocated through an involved procedure. Reducing the number of unallocated goods for arbitrary number of agents is a systematic way to settle the big question. In this paper, we develop a new approach, and show that for every $\varepsilon \in (0,1/2]$, there always exists a $(1-\varepsilon)$-EFX allocation with sublinear number of unallocated goods and high Nash welfare. For this, we reduce the EFX problem to a novel problem in extremal graph theory. We introduce the notion of rainbow cycle number $R(\cdot)$. For all $d \in \mathbb{N}$, $R(d)$ is the largest $k$ such that there exists a $k$-partite digraph $G =(\cup_{i \in [k]} V_i, E)$, in which 1) each part has at most $d$ vertices, i.e., $\lvert V_i \rvert \leq d$ for all $i \in [k]$, 2) for any two parts $V_i$ and $V_j$, each vertex in $V_i$ has an incoming edge from some vertex in $V_j$ and vice-versa, and 3) there exists no cycle in $G$ that contains at most one vertex from each part. We show that any upper bound on $R(d)$ directly translates to a sublinear bound on the number of unallocated goods. We establish a polynomial upper bound on $R(d)$, yielding our main result. Furthermore, our approach is constructive, which also gives a polynomial-time algorithm for finding such an allocation. }, }

Endnote

%0 Report %A Ray Chaudhury, Bhaskar %A Garg, Jugal %A Mehlhorn, Kurt %A Mehta, Ruta %A Misra, Pranabendu %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Improving EFX Guarantees through Rainbow Cycle Number : %G eng %U http://hdl.handle.net/21.11116/0000-0008-DB40-9 %U https://arxiv.org/abs/2103.01628 %D 2021 %X We study the problem of fairly allocating a set of indivisible goods among $n$ agents with additive valuations. Envy-freeness up to any good (EFX) is arguably the most compelling fairness notion in this context. However, the existence of EFX allocations has not been settled and is one of the most important problems in fair division. Towards resolving this problem, many impressive results show the existence of its relaxations, e.g., the existence of $0.618$-EFX allocations, and the existence of EFX at most $n-1$ unallocated goods. The latter result was recently improved for three agents, in which the two unallocated goods are allocated through an involved procedure. Reducing the number of unallocated goods for arbitrary number of agents is a systematic way to settle the big question. In this paper, we develop a new approach, and show that for every $\varepsilon \in (0,1/2]$, there always exists a $(1-\varepsilon)$-EFX allocation with sublinear number of unallocated goods and high Nash welfare. For this, we reduce the EFX problem to a novel problem in extremal graph theory. We introduce the notion of rainbow cycle number $R(\cdot)$. For all $d \in \mathbb{N}$, $R(d)$ is the largest $k$ such that there exists a $k$-partite digraph $G =(\cup_{i \in [k]} V_i, E)$, in which 1) each part has at most $d$ vertices, i.e., $\lvert V_i \rvert \leq d$ for all $i \in [k]$, 2) for any two parts $V_i$ and $V_j$, each vertex in $V_i$ has an incoming edge from some vertex in $V_j$ and vice-versa, and 3) there exists no cycle in $G$ that contains at most one vertex from each part. We show that any upper bound on $R(d)$ directly translates to a sublinear bound on the number of unallocated goods. We establish a polynomial upper bound on $R(d)$, yielding our main result. Furthermore, our approach is constructive, which also gives a polynomial-time algorithm for finding such an allocation. %K Computer Science, Computer Science and Game Theory, cs.GT,Computer Science, Data Structures and Algorithms, cs.DS

[65]

B. Ray Chaudhury, J. Garg, P. McGlaughlin, and R. Mehta, “Competitive Allocation of a Mixed Manna,” in Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, VA, USA (Virtual Conference), 2021.

Links

Export

BibTeX

@inproceedings{Chaudhury_SODA21, TITLE = {Competitive Allocation of a Mixed Manna}, AUTHOR = {Ray Chaudhury, Bhaskar and Garg, Jugal and McGlaughlin, Peter and Mehta, Ruta}, LANGUAGE = {eng}, ISBN = {978-1-61197-646-5}, DOI = {10.1137/1.9781611976465.85}, PUBLISHER = {SIAM}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, DATE = {2021}, BOOKTITLE = {Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)}, EDITOR = {Marx, D{\'a}niel}, PAGES = {1405--1424}, ADDRESS = {Alexandria, VA, USA (Virtual Conference)}, }

Endnote

%0 Conference Proceedings %A Ray Chaudhury, Bhaskar %A Garg, Jugal %A McGlaughlin, Peter %A Mehta, Ruta %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Competitive Allocation of a Mixed Manna : %G eng %U http://hdl.handle.net/21.11116/0000-0007-9365-1 %R 10.1137/1.9781611976465.85 %D 2021 %B 32nd Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2021-01-10 - 2021-01-13 %C Alexandria, VA, USA (Virtual Conference) %B Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms %E Marx, Dániel %P 1405 - 1424 %I SIAM %@ 978-1-61197-646-5

[66]

B. Ray Chaudhury, T. Kavitha, K. Mehlhorn, and A. Sgouritsa, “A Little Charity Guarantees Almost Envy-Freeness,” SIAM Journal on Computing, vol. 50, no. 4, 2021.

Links

Export

BibTeX

@article{RayChaudhury21, TITLE = {A Little Charity Guarantees Almost Envy-Freeness}, AUTHOR = {Ray Chaudhury, Bhaskar and Kavitha, Telikepalli and Mehlhorn, Kurt and Sgouritsa, Alkmini}, LANGUAGE = {eng}, ISSN = {0097-5397}, DOI = {10.1137/20M1359134}, PUBLISHER = {SIAM}, ADDRESS = {Philadelphia, PA}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {50}, NUMBER = {4}, PAGES = {1336--1358}, }

Endnote

%0 Journal Article %A Ray Chaudhury, Bhaskar %A Kavitha, Telikepalli %A Mehlhorn, Kurt %A Sgouritsa, Alkmini %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T A Little Charity Guarantees Almost Envy-Freeness : %G eng %U http://hdl.handle.net/21.11116/0000-0009-2B38-9 %R 10.1137/20M1359134 %7 2021 %D 2021 %J SIAM Journal on Computing %V 50 %N 4 %& 1336 %P 1336 - 1358 %I SIAM %C Philadelphia, PA %@ false

[67]

M. Roth, J. Schmitt, and P. Wellnitz, “Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders,” in 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Glasgow, UK (Virtual Conference), 2021.

Links

Export

BibTeX

@inproceedings{Roth_ICALP2021, TITLE = {Detecting and Counting Small Subgraphs, and Evaluating a Parameterized {Tutte} Polynomial: {L}ower Bounds via {Toroidal} Grids and {Cayley} Graph Expanders}, AUTHOR = {Roth, Marc and Schmitt, Johannes and Wellnitz, Philip}, LANGUAGE = {eng}, ISSN = {1868-8969}, ISBN = {978-3-95977-195-5}, URL = {urn:nbn:de:0030-drops-141778}, DOI = {10.4230/LIPIcs.ICALP.2021.108}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, EDITOR = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, PAGES = {1--16}, EID = {108}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {198}, ADDRESS = {Glasgow, UK (Virtual Conference)}, }

Endnote

%0 Conference Proceedings %A Roth, Marc %A Schmitt, Johannes %A Wellnitz, Philip %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders : %G eng %U http://hdl.handle.net/21.11116/0000-0009-AFBF-C %R 10.4230/LIPIcs.ICALP.2021.108 %U urn:nbn:de:0030-drops-141778 %D 2021 %B 48th International Colloquium on Automata, Languages, and Programming %Z date of event: 2021-07-12 - 2020-07-16 %C Glasgow, UK (Virtual Conference) %B 48th International Colloquium on Automata, Languages, and Programming %E Bansal, Nikhil; Merelli, Emanuela; Worrell, James %P 1 - 16 %Z sequence number: 108 %I Schloss Dagstuhl %@ 978-3-95977-195-5 %B Leibniz International Proceedings in Informatics %N 198 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2021/14177/

[68]

M. Roth, J. Schmitt, and P. Wellnitz, “Counting Small Induced Subgraphs Satisfying Monotone Properties,” in FOCS 2020, 61st Annual IEEE Symposium on Foundations of Computer Science, Durham, NC, USA (Virtual Conference), 2021.

Links

Export

BibTeX

@inproceedings{Roth_FOCS2020, TITLE = {Counting Small Induced Subgraphs Satisfying Monotone Properties}, AUTHOR = {Roth, Marc and Schmitt, Johannes and Wellnitz, Philip}, LANGUAGE = {eng}, ISBN = {978-1-7281-9621-3}, DOI = {10.1109/FOCS46700.2020}, PUBLISHER = {IEEE}, YEAR = {2020}, MARGINALMARK = {$\bullet$}, DATE = {2021}, BOOKTITLE = {FOCS 2020, 61st Annual IEEE Symposium on Foundations of Computer Science}, PAGES = {1356--1367}, ADDRESS = {Durham, NC, USA (Virtual Conference)}, }

Endnote

%0 Conference Proceedings %A Roth, Marc %A Schmitt, Johannes %A Wellnitz, Philip %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Counting Small Induced Subgraphs Satisfying Monotone Properties : %G eng %U http://hdl.handle.net/21.11116/0000-0007-8C5E-3 %R 10.1109/FOCS46700.2020 %D 2021 %B 61st Annual IEEE Symposium on Foundations of Computer Science %Z date of event: 2020-11-16 - 2020-11-19 %C Durham, NC, USA (Virtual Conference) %B FOCS 2020 %P 1356 - 1367 %I IEEE %@ 978-1-7281-9621-3

[69]

K. Vitting Klinkby, P. Misra, and S. Saurabh, “Strong Connectivity Augmentation is FPT,” in Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Alexandria, VA, USA (Virtual Conference), 2021.

Links

Export

BibTeX

@inproceedings{SCAug21, TITLE = {Strong Connectivity Augmentation is {FPT}}, AUTHOR = {Vitting Klinkby, Kristine and Misra, Pranabendu and Saurabh, Saket}, LANGUAGE = {eng}, ISBN = {978-1-61197-646-5}, DOI = {10.1137/1.9781611976465.15}, PUBLISHER = {SIAM}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, DATE = {2021}, BOOKTITLE = {Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)}, EDITOR = {Marx, D{\'a}niel}, PAGES = {219--234}, ADDRESS = {Alexandria, VA, USA (Virtual Conference)}, }

Endnote

%0 Conference Proceedings %A Vitting Klinkby, Kristine %A Misra, Pranabendu %A Saurabh, Saket %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Strong Connectivity Augmentation is FPT : %G eng %U http://hdl.handle.net/21.11116/0000-0007-D2A6-0 %R 10.1137/1.9781611976465.15 %D 2021 %B 32nd Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2021-01-10 - 2021-01-13 %C Alexandria, VA, USA (Virtual Conference) %B Proceedings of the Thirty-Second ACM-SIAM Symposium on Discrete Algorithms %E Marx, Dániel %P 219 - 234 %I SIAM %@ 978-1-61197-646-5

[70]

P. Wellnitz, “Counting Patterns in Strings and Graphs,” Universität des Saarlandes, Saarbrücken, 2021.

Links

Export

BibTeX

@phdthesis{WellnitzPhD21, TITLE = {Counting Patterns in Strings and Graphs}, AUTHOR = {Wellnitz, Philip}, LANGUAGE = {eng}, URL = {urn:nbn:de:bsz:291--ds-350981}, DOI = {10.22028/D291-35098}, SCHOOL = {Universit{\"a}t des Saarlandes}, ADDRESS = {Saarbr{\"u}cken}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, DATE = {2021}, }

Endnote

%0 Thesis %A Wellnitz, Philip %Y Mehlhorn, Kurt %A referee: Landau, Gad M. %A referee: Grohe, Martin %A referee: Bringmann, Karl %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society International Max Planck Research School, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Counting Patterns in Strings and Graphs : %G eng %U http://hdl.handle.net/21.11116/0000-000C-1ED8-0 %R 10.22028/D291-35098 %U urn:nbn:de:bsz:291--ds-350981 %F OTHER: hdl:20.500.11880/32103 %I Universität des Saarlandes %C Saarbrücken %D 2021 %P 253 p. %V phd %9 phd %U https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/32103

[71]

A. Zandieh, I. Han, H. Avron, N. Shoham, C. Kim, and J. Shin, “Scaling Neural Tangent Kernels via Sketching and Random Features,” in Advances in Neural Information Processing Systems 34 (NeurIPS 2021), Virtual, 2021.

Links

Export

BibTeX

@inproceedings{zandieh_NeurIPS21, TITLE = {Scaling Neural Tangent Kernels via Sketching and Random Features}, AUTHOR = {Zandieh, Amir and Han, Insu and Avron, Haim and Shoham, Neta and Kim, Chaewon and Shin, Jinwoo}, LANGUAGE = {eng}, PUBLISHER = {Curran Assoicates, Inc.}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {Advances in Neural Information Processing Systems 34 (NeurIPS 2021)}, EDITOR = {Ranzato, M. and Beygelzimer, A. and Dauphin, Y. and Liang, P. S. and Wortman Vaughan, J.}, PAGES = {1062--1073}, ADDRESS = {Virtual}, }

Endnote

%0 Conference Proceedings %A Zandieh, Amir %A Han, Insu %A Avron, Haim %A Shoham, Neta %A Kim, Chaewon %A Shin, Jinwoo %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations External Organizations External Organizations %T Scaling Neural Tangent Kernels via Sketching and Random Features : %G eng %U http://hdl.handle.net/21.11116/0000-000C-90E3-0 %D 2021 %B 35th Conference on Neural Information Processing Systems %Z date of event: 2021-12-06 - 2021-12-14 %C Virtual %B Advances in Neural Information Processing Systems 34 %E Ranzato, M.; Beygelzimer, A.; Dauphin, Y.; Liang, P. S.; Wortman Vaughan, J. %P 1062 - 1073 %I Curran Assoicates, Inc.