Current Year

[1]
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.
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
[2]
I. Anagnostides, T. Gouleakis, and A. Marashian, “Robust Learning under Strong Noise via SQs,” in Proceedings of the Twenty Fourth International Conference on Artificial Intelligence and Statistics (AISTATS 2021), Virtual Conference. (Accepted/in press)
Export
BibTeX
@inproceedings{Anagnostides_AISTATS2020, TITLE = {Robust Learning under Strong Noise via {SQs}}, AUTHOR = {Anagnostides, Ioannis and Gouleakis, Themis and Marashian, Ali}, LANGUAGE = {eng}, PUBLISHER = {PMLR}, YEAR = {2021}, PUBLREMARK = {Accepted}, MARGINALMARK = {$\bullet$}, BOOKTITLE = {Proceedings of the Twenty Fourth International Conference on Artificial Intelligence and Statistics (AISTATS 2021)}, SERIES = {Proceedings of the Machine Learning Research}, 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 %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 Twenty Fourth International Conference on Artificial Intelligence and Statistics %I PMLR %B Proceedings of the Machine Learning Research
[3]
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.
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
[4]
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.
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
[5]
B. A. Berendsohn, L. Kozma, and D. Marx, “Finding and Counting Permutations via CSPs,” Algorithmica, vol. 148, 2021.
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 = {148}, }
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 148 %I Springer %C New York, NY %@ false
[6]
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.
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
[7]
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.
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
%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 A Fine-Grained Perspective on Approximating Subset Sum and Partition : %G eng %U http://hdl.handle.net/21.11116/0000-0007-90DD-D %R 10.1137/1.9781611976465.108 %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 1797 - 1815 %I SIAM %@ 978-1-61197-646-5
[8]
K. Bringmann and A. Nusser, “Translating Hausdorff Is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation,” in 37th International Symposium onComputational Geometry (SoCG 2021), Buffalo, NY, USA (Virtual Conference), 2021.
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 onComputational 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 onComputational 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
[9]
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.
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
[10]
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.
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
[11]
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.
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
[12]
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.
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
[13]
K. Bringmann, N. Fischer, and V. Nakos, “Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution,” in STOC ’21, Virtual, Italy, 2021.
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}, 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
[14]
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.
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
[15]
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.
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
[16]
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.
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,
[17]
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.
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,
[18]
K. Bringmann, A. Cassis, N. Fischer, and M. Künnemann, “Fine-Grained Completeness for Optimization in P,” 2021. [Online]. Available: https://arxiv.org/abs/2107.01721. (arXiv: 2107.01721)
Abstract
We initiate the study of fine-grained completeness theorems for exact and approximate optimization in the polynomial-time regime. Inspired by the first completeness results for decision problems in P (Gao, Impagliazzo, Kolokolova, Williams, TALG 2019) as well as the classic class MaxSNP and MaxSNP-completeness for NP optimization problems (Papadimitriou, Yannakakis, JCSS 1991), we define polynomial-time analogues MaxSP and MinSP, which contain a number of natural optimization problems in P, including Maximum Inner Product, general forms of nearest neighbor search and optimization variants of the $k$-XOR problem. Specifically, we define MaxSP as the class of problems definable as $\max_{x_1,\dots,x_k} \#\{ (y_1,\dots,y_\ell) : \phi(x_1,\dots,x_k, y_1,\dots,y_\ell) \}$, where $\phi$ is a quantifier-free first-order property over a given relational structure (with MinSP defined analogously). On $m$-sized structures, we can solve each such problem in time $O(m^{k+\ell-1})$. Our results are: - We determine (a sparse variant of) the Maximum/Minimum Inner Product problem as complete under *deterministic* fine-grained reductions: A strongly subquadratic algorithm for Maximum/Minimum Inner Product would beat the baseline running time of $O(m^{k+\ell-1})$ for *all* problems in MaxSP/MinSP by a polynomial factor. - This completeness transfers to approximation: Maximum/Minimum Inner Product is also complete in the sense that a strongly subquadratic $c$-approximation would give a $(c+\varepsilon)$-approximation for all MaxSP/MinSP problems in time $O(m^{k+\ell-1-\delta})$, where $\varepsilon > 0$ can be chosen arbitrarily small. Combining our completeness with~(Chen, Williams, SODA 2019), we obtain the perhaps surprising consequence that refuting the OV Hypothesis is *equivalent* to giving a $O(1)$-approximation for all MinSP problems in faster-than-$O(m^{k+\ell-1})$ time.
Export
BibTeX
@online{Bringmann_2107.01721, TITLE = {Fine-Grained Completeness for Optimization in P}, AUTHOR = {Bringmann, Karl and Cassis, Alejandro and Fischer, Nick and K{\"u}nnemann, Marvin}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/2107.01721}, EPRINT = {2107.01721}, EPRINTTYPE = {arXiv}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We initiate the study of fine-grained completeness theorems for exact and approximate optimization in the polynomial-time regime. Inspired by the first completeness results for decision problems in P (Gao, Impagliazzo, Kolokolova, Williams, TALG 2019) as well as the classic class MaxSNP and MaxSNP-completeness for NP optimization problems (Papadimitriou, Yannakakis, JCSS 1991), we define polynomial-time analogues MaxSP and MinSP, which contain a number of natural optimization problems in P, including Maximum Inner Product, general forms of nearest neighbor search and optimization variants of the $k$-XOR problem. Specifically, we define MaxSP as the class of problems definable as $\max_{x_1,\dots,x_k} \#\{ (y_1,\dots,y_\ell) : \phi(x_1,\dots,x_k, y_1,\dots,y_\ell) \}$, where $\phi$ is a quantifier-free first-order property over a given relational structure (with MinSP defined analogously). On $m$-sized structures, we can solve each such problem in time $O(m^{k+\ell-1})$. Our results are: -- We determine (a sparse variant of) the Maximum/Minimum Inner Product problem as complete under *deterministic* fine-grained reductions: A strongly subquadratic algorithm for Maximum/Minimum Inner Product would beat the baseline running time of $O(m^{k+\ell-1})$ for *all* problems in MaxSP/MinSP by a polynomial factor. -- This completeness transfers to approximation: Maximum/Minimum Inner Product is also complete in the sense that a strongly subquadratic $c$-approximation would give a $(c+\varepsilon)$-approximation for all MaxSP/MinSP problems in time $O(m^{k+\ell-1-\delta})$, where $\varepsilon > 0$ can be chosen arbitrarily small. Combining our completeness with~(Chen, Williams, SODA 2019), we obtain the perhaps surprising consequence that refuting the OV Hypothesis is *equivalent* to giving a $O(1)$-approximation for all MinSP problems in faster-than-$O(m^{k+\ell-1})$ time.}, }
Endnote
%0 Report %A Bringmann, Karl %A Cassis, Alejandro %A Fischer, Nick %A K&#252;nnemann, Marvin %+ 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 Fine-Grained Completeness for Optimization in P : %G eng %U http://hdl.handle.net/21.11116/0000-0008-E26A-2 %U https://arxiv.org/abs/2107.01721 %D 2021 %X We initiate the study of fine-grained completeness theorems for exact and approximate optimization in the polynomial-time regime. Inspired by the first completeness results for decision problems in P (Gao, Impagliazzo, Kolokolova, Williams, TALG 2019) as well as the classic class MaxSNP and MaxSNP-completeness for NP optimization problems (Papadimitriou, Yannakakis, JCSS 1991), we define polynomial-time analogues MaxSP and MinSP, which contain a number of natural optimization problems in P, including Maximum Inner Product, general forms of nearest neighbor search and optimization variants of the $k$-XOR problem. Specifically, we define MaxSP as the class of problems definable as $\max_{x_1,\dots,x_k} \#\{ (y_1,\dots,y_\ell) : \phi(x_1,\dots,x_k, y_1,\dots,y_\ell) \}$, where $\phi$ is a quantifier-free first-order property over a given relational structure (with MinSP defined analogously). On $m$-sized structures, we can solve each such problem in time $O(m^{k+\ell-1})$. Our results are: - We determine (a sparse variant of) the Maximum/Minimum Inner Product problem as complete under *deterministic* fine-grained reductions: A strongly subquadratic algorithm for Maximum/Minimum Inner Product would beat the baseline running time of $O(m^{k+\ell-1})$ for *all* problems in MaxSP/MinSP by a polynomial factor. - This completeness transfers to approximation: Maximum/Minimum Inner Product is also complete in the sense that a strongly subquadratic $c$-approximation would give a $(c+\varepsilon)$-approximation for all MaxSP/MinSP problems in time $O(m^{k+\ell-1-\delta})$, where $\varepsilon > 0$ can be chosen arbitrarily small. Combining our completeness with~(Chen, Williams, SODA 2019), we obtain the perhaps surprising consequence that refuting the OV Hypothesis is *equivalent* to giving a $O(1)$-approximation for all MinSP problems in faster-than-$O(m^{k+\ell-1})$ time. %K Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computational Complexity, cs.CC
[19]
K. Bringmann, M. Künnemann, and A. Nusser, “Discrete Fréchet Distance under Translation: Conditional Hardness and an Improved Algorithm,” ACM Transactions on Algorithms, vol. 17, no. 3, 2021.
Export
BibTeX
@article{Bringmann2021, TITLE = {Discrete {F}r\'{e}chet Distance under Translation: {C}onditional Hardness and an Improved Algorithm}, AUTHOR = {Bringmann, Karl and K{\"u}nnemann, Marvin and Nusser, Andr{\'e}}, LANGUAGE = {eng}, ISSN = {1549-6325}, DOI = {10.1145/3460656}, PUBLISHER = {ACM}, ADDRESS = {New York, NY}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, JOURNAL = {ACM Transactions on Algorithms}, VOLUME = {17}, NUMBER = {3}, PAGES = {1--42}, EID = {25}, }
Endnote
%0 Journal Article %A Bringmann, Karl %A K&#252;nnemann, Marvin %A Nusser, Andr&#233; %+ 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 Discrete Fr&#233;chet Distance under Translation: Conditional Hardness and an Improved Algorithm : %G eng %U http://hdl.handle.net/21.11116/0000-0009-2A8B-C %R 10.1145/3460656 %7 2021 %D 2021 %J ACM Transactions on Algorithms %V 17 %N 3 %& 1 %P 1 - 42 %Z sequence number: 25 %I ACM %C New York, NY %@ false
[20]
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.
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
[21]
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.
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
[22]
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.
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
[23]
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.
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
[24]
E. Cruciani, E. Natale, A. Nusser, and G. Scornavacca, “Phase Transition of the 2-Choices Dynamics on Core-Periphery Networks,” Distributed Computing, vol. Early Access, 2021.
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 = {Early Access}, }
Endnote
%0 Journal Article %A Cruciani, Emilio %A Natale, Emanuele %A Nusser, Andr&#233; %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 Early Access %I Springer International %C Berlin %@ false
[25]
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.
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
[26]
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.
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
[27]
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.
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&#233;lior&#233;: 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
[28]
M. Függer, A. Kinali, C. Lenzen, and B. Wiederhake, “Fast All-Digital Clock Frequency Adaptation Circuit for Voltage Droop Tolerance,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2021.
Export
BibTeX
@article{Fuegger2021, TITLE = {Fast All-Digital Clock Frequency Adaptation Circuit for Voltage Droop Tolerance}, AUTHOR = {F{\"u}gger, Matthias and Kinali, Attila and Lenzen, Christoph and Wiederhake, Ben}, LANGUAGE = {eng}, ISSN = {0278-0070}, DOI = {10.1109/TCAD.2021.3097599}, PUBLISHER = {IEEE}, ADDRESS = {Piscataway, NJ}, YEAR = {2021}, MARGINALMARK = {$\bullet$}, JOURNAL = {IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems}, }
Endnote
%0 Journal Article %A F&#252;gger, Matthias %A Kinali, Attila %A Lenzen, Christoph %A Wiederhake, Ben %+ External Organizations 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 Fast All-Digital Clock Frequency Adaptation Circuit for Voltage Droop Tolerance : %G eng %U http://hdl.handle.net/21.11116/0000-0009-201C-4 %R 10.1109/TCAD.2021.3097599 %7 2021 %D 2021 %J IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems %I IEEE %C Piscataway, NJ %@ false
[29]
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.
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
[30]
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.
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
[31]
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.
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&#322;aw, Poland (Online) %B Structural Information and Communication Complexity %E Jurdzi&#324;ski, Tomasz; Schmid, Stefan %P 352 - 369 %I Springer %@ 978-3-030-79526-9 %B Lecture Notes in Computer Science %N 12810
[32]
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.
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&#225;niel %P 199 - 218 %I SIAM %@ 978-1-61197-646-5
[33]
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.
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
[34]
J. Madathil, R. Sharma, and M. Zehavi, “A Sub-exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs,” Algorithmica, 2021.
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}, }
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 %I Springer %C New York, NY %@ false
[35]
A. Pandey, “Variety Membership Testing in Algebraic Complexity Theory,” Universität des Saarlandes, Saarbrücken, 2021.
Export
BibTeX
@phdthesis{Pandeyphd2021, TITLE = {Variety Membership Testing in Algebraic Complexity Theory}, AUTHOR = {Pandey, Anurag}, LANGUAGE = {eng}, 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&#228;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 %I Universit&#228;t des Saarlandes %C Saarbr&#252;cken %D 2021 %P 128 p. %V phd %9 phd %U https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/31479
[36]
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.
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&#225;niel %P 1405 - 1424 %I SIAM %@ 978-1-61197-646-5
[37]
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.
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
[38]
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.
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
[39]
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.
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
[40]
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.
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
[41]
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.
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&#225;niel %P 219 - 234 %I SIAM %@ 978-1-61197-646-5