Current Year
[1]
A. Abboud, K. Bringmann, and N. Fischer, “Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics,” in Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), Orlando, FL, USA. (Accepted/in press)
Export
BibTeX
@inproceedings{Abboud_STOC23,
TITLE = {Stronger 3-{SUM} Lower Bounds for Approximate Distance Oracles via Additive Combinatorics},
AUTHOR = {Abboud, Amir and Bringmann, Karl and Fischer, Nick},
LANGUAGE = {eng},
PUBLISHER = {ACM},
YEAR = {2023},
PUBLREMARK = {Accepted},
MARGINALMARK = {$\bullet$},
BOOKTITLE = {Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023)},
ADDRESS = {Orlando, FL, USA},
}
Endnote
%0 Conference Proceedings
%A Abboud, Amir
%A Bringmann, Karl
%A Fischer, Nick
%+ External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via
Additive Combinatorics :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-8C13-1
%D 2023
%B 55th Annual ACM Symposium on Theory of Computing
%Z date of event: 2023-06-20 - 2023-06-23
%C Orlando, FL, USA
%B Proceedings of the 55th Annual ACM Symposium on Theory of Computing
%I ACM
[2]
A. Antoniadis, C. Coester, M. Elias, A. Polak, and B. Simon, “Online Metric Algorithms with Untrusted Predictions,” ACM Transactions on Algorithms, vol. 19, no. 2, 2023.
Export
BibTeX
@article{Antoniadis23,
TITLE = {Online Metric Algorithms with Untrusted Predictions},
AUTHOR = {Antoniadis, Antonios and Coester, Christian and Elias, Marek and Polak, Adam and Simon, Bertrand},
LANGUAGE = {eng},
ISSN = {1549-6325},
DOI = {10.1145/3582689},
PUBLISHER = {ACM},
ADDRESS = {New York, NY},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
JOURNAL = {ACM Transactions on Algorithms},
VOLUME = {19},
NUMBER = {2},
PAGES = {1--34},
EID = {19},
}
Endnote
%0 Journal Article
%A Antoniadis, Antonios
%A Coester, Christian
%A Elias, Marek
%A Polak, Adam
%A Simon, Bertrand
%+ External Organizations
External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T Online Metric Algorithms with Untrusted Predictions :
%G eng
%U http://hdl.handle.net/21.11116/0000-000D-2D93-B
%R 10.1145/3582689
%7 2023
%D 2023
%J ACM Transactions on Algorithms
%V 19
%N 2
%& 1
%P 1 - 34
%Z sequence number: 19
%I ACM
%C New York, NY
%@ false
[3]
A. Antoniadis, T. Gouleakis, P. Kleer, and P. Kolev, “Secretary and Online Matching Problems with Machine Learned Advice,” Discrete Optimization, vol. 48, no. 2, 2023.
Export
BibTeX
@article{Antoniadis23,
TITLE = {Secretary and Online Matching Problems with Machine Learned Advice},
AUTHOR = {Antoniadis, Antonios and Gouleakis, Themis and Kleer, Pieter and Kolev, Pavel},
LANGUAGE = {eng},
ISSN = {1572-5286},
DOI = {10.1016/j.disopt.2023.100778},
PUBLISHER = {Elsevier},
ADDRESS = {Amsterdam},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
JOURNAL = {Discrete Optimization},
VOLUME = {48},
NUMBER = {2},
EID = {100778},
}
Endnote
%0 Journal Article
%A Antoniadis, Antonios
%A Gouleakis, Themis
%A Kleer, Pieter
%A Kolev, Pavel
%+ 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
%T Secretary and Online Matching Problems with Machine Learned Advice :
%G eng
%U http://hdl.handle.net/21.11116/0000-000D-9392-7
%R 10.1016/j.disopt.2023.100778
%7 2023
%D 2023
%J Discrete Optimization
%V 48
%N 2
%Z sequence number: 100778
%I Elsevier
%C Amsterdam
%@ false
[4]
P. S. Ardra, R. Krithika, S. Saurabh, and R. Sharma, “Balanced Substructures in Bicolored Graphs,” in SOFSEM 2023: Theory and Practice of Computer Science, Nový Smokovec, Slovakia, 2023.
Export
BibTeX
@inproceedings{Ardra_SOFSEM23,
TITLE = {Balanced Substructures in Bicolored Graphs},
AUTHOR = {Ardra, P. S. and Krithika, R. and Saurabh, Saket and Sharma, Roohani},
LANGUAGE = {eng},
ISBN = {978-3-031-23100-1},
DOI = {10.1007/978-3-031-23101-8_12},
PUBLISHER = {Springer},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
DATE = {2023},
BOOKTITLE = {SOFSEM 2023: Theory and Practice of Computer Science},
EDITOR = {G{\c a}sieniec, Leszek},
PAGES = {177--191},
SERIES = {Lecture Notes in Computer Science},
VOLUME = {13878},
ADDRESS = {Nov{\'y} Smokovec, Slovakia},
}
Endnote
%0 Conference Proceedings
%A Ardra, P. S.
%A Krithika, R.
%A Saurabh, Saket
%A Sharma, Roohani
%+ External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Balanced Substructures in Bicolored Graphs :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-1D8F-4
%R 10.1007/978-3-031-23101-8_12
%D 2023
%B 48th International Conference on Current Trends in Theory and Practice of Computer Science
%Z date of event: 2023-01-15 - 2023-01-18
%C Nový Smokovec, Slovakia
%B SOFSEM 2023: Theory and Practice of Computer Science
%E Gąsieniec, Leszek
%P 177 - 191
%I Springer
%@ 978-3-031-23100-1
%B Lecture Notes in Computer Science
%N 13878
%U https://rdcu.be/c2Gfk
[5]
H. Bannai, I. Tomohiro, T. Kociumaka, D. Koeppl, and S. J. Puglisi, “Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences,” Algorithmica, 2023.
Export
BibTeX
@article{Bannai23,
TITLE = {Computing Longest {Lyndon} Subsequences and Longest Common {Lyndon} Subsequences},
AUTHOR = {Bannai, Hideo and Tomohiro, I. and Kociumaka, Tomasz and Koeppl, Dominik and Puglisi, Simon J.},
LANGUAGE = {eng},
ISSN = {0178-4617},
DOI = {10.1007/s00453-023-01125-z},
PUBLISHER = {Springer},
ADDRESS = {New York, NY},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
JOURNAL = {Algorithmica},
}
Endnote
%0 Journal Article
%A Bannai, Hideo
%A Tomohiro, I.
%A Kociumaka, Tomasz
%A Koeppl, Dominik
%A Puglisi, Simon J.
%+ External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
%T Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences :
%G eng
%U http://hdl.handle.net/21.11116/0000-000D-3FF3-B
%R 10.1007/s00453-023-01125-z
%7 2023
%D 2023
%J Algorithmica
%I Springer
%C New York, NY
%@ false
[6]
M. Beck, J. Spoerhase, and S. Storandt, “Mind the Gap: Edge Facility Location Problems in Theory and Practice,” in Algorithms and Discrete Applied Mathematics (CALDAM 2023), Gandhinagar, India, 2023.
Export
BibTeX
@inproceedings{beck-etal23:mind-the-gap,
TITLE = {Mind the Gap: {E}dge Facility Location Problems in Theory and Practice},
AUTHOR = {Beck, Moritz and Spoerhase, Joachim and Storandt, Sabine},
LANGUAGE = {eng},
ISBN = {978-3-031-25210-5},
DOI = {10.1007/978-3-031-25211-2_25},
PUBLISHER = {Springer},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
DATE = {2023},
BOOKTITLE = {Algorithms and Discrete Applied Mathematics (CALDAM 2023)},
EDITOR = {Bagchi, Amitabha and Muthu, Rahul},
PAGES = {321--334},
SERIES = {Lecture Notes in Computer Science},
VOLUME = {13947},
ADDRESS = {Gandhinagar, India},
}
Endnote
%0 Conference Proceedings
%A Beck, Moritz
%A Spoerhase, Joachim
%A Storandt, Sabine
%+ External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T Mind the Gap: Edge Facility Location Problems in Theory and Practice :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-992D-6
%R 10.1007/978-3-031-25211-2_25
%D 2023
%B 9th International Conference on Algorithms and Discrete Applied Mathematics
%Z date of event: 2023-02-09 - 2023-02-11
%C Gandhinagar, India
%B Algorithms and Discrete Applied Mathematics
%E Bagchi, Amitabha; Muthu, Rahul
%P 321 - 334
%I Springer
%@ 978-3-031-25210-5
%B Lecture Notes in Computer Science
%N 13947
%U https://rdcu.be/c5J8c
[7]
S. Bhattacharya, P. Kiss, and T. Saranurak, “Sublinear Algorithms for (1.5+Epsilon)-Approximate Matching,” in Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), Orlando, FL, USA. (Accepted/in press)
Export
BibTeX
@inproceedings{Bhattacharya_STOC23,
TITLE = {Sublinear Algorithms for $(1.5+\epsilon)$-Approximate Matching},
AUTHOR = {Bhattacharya, Sayan and Kiss, Peter and Saranurak, Thatchaphol},
LANGUAGE = {eng},
PUBLISHER = {ACM},
YEAR = {2023},
PUBLREMARK = {Accepted},
MARGINALMARK = {$\bullet$},
BOOKTITLE = {Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023)},
ADDRESS = {Orlando, FL, USA},
}
Endnote
%0 Conference Proceedings
%A Bhattacharya, Sayan
%A Kiss, Peter
%A Saranurak, Thatchaphol
%+ External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T Sublinear Algorithms for (1.5+Epsilon)-Approximate Matching :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-9BA1-F
%D 2023
%B 55th Annual ACM Symposium on Theory of Computing
%Z date of event: 2023-06-20 - 2023-06-23
%C Orlando, FL, USA
%B Proceedings of the 55th Annual ACM Symposium on Theory of Computing
%I ACM
[8]
S. Bhattacharya, P. Kiss, and T. Saranurak, “Dynamic (1.5+Epsilon)-Approximate Matching Size in Truly Sublinear Update Time,” 2023. [Online]. Available: https://arxiv.org/abs/2302.05030. (arXiv: 2302.05030)
Abstract
We show a fully dynamic algorithm for maintaining $(1+\epsilon)$-approximate<br>\emph{size} of maximum matching of the graph with $n$ vertices and $m$ edges<br>using $m^{0.5-\Omega_{\epsilon}(1)}$ update time. This is the first polynomial<br>improvement over the long-standing $O(n)$ update time, which can be trivially<br>obtained by periodic recomputation. Thus, we resolve the value version of a<br>major open question of the dynamic graph algorithms literature (see, e.g.,<br>[Gupta and Peng FOCS'13], [Bernstein and Stein SODA'16],[Behnezhad and Khanna<br>SODA'22]).<br> Our key technical component is the first sublinear algorithm for $(1,\epsilon<br>n)$-approximate maximum matching with sublinear running time on dense graphs.<br>All previous algorithms suffered a multiplicative approximation factor of at<br>least $1.499$ or assumed that the graph has a very small maximum degree.<br>
Export
BibTeX
@online{Bhattacharya2302.05030,
TITLE = {Dynamic $(1+\epsilon)$-Approximate Matching Size in Truly Sublinear Update Time},
AUTHOR = {Bhattacharya, Sayan and Kiss, Peter and Saranurak, Thatchaphol},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2302.05030},
EPRINT = {2302.05030},
EPRINTTYPE = {arXiv},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
ABSTRACT = {We show a fully dynamic algorithm for maintaining $(1+\epsilon)$-approximate<br>\emph{size} of maximum matching of the graph with $n$ vertices and $m$ edges<br>using $m^{0.5-\Omega_{\epsilon}(1)}$ update time. This is the first polynomial<br>improvement over the long-standing $O(n)$ update time, which can be trivially<br>obtained by periodic recomputation. Thus, we resolve the value version of a<br>major open question of the dynamic graph algorithms literature (see, e.g.,<br>[Gupta and Peng FOCS'13], [Bernstein and Stein SODA'16],[Behnezhad and Khanna<br>SODA'22]).<br> Our key technical component is the first sublinear algorithm for $(1,\epsilon<br>n)$-approximate maximum matching with sublinear running time on dense graphs.<br>All previous algorithms suffered a multiplicative approximation factor of at<br>least $1.499$ or assumed that the graph has a very small maximum degree.<br>},
}
Endnote
%0 Report
%A Bhattacharya, Sayan
%A Kiss, Peter
%A Saranurak, Thatchaphol
%+ External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T Dynamic (1.5+Epsilon)-Approximate Matching Size in Truly Sublinear
Update Time :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-9BA8-8
%U https://arxiv.org/abs/2302.05030
%D 2023
%X We show a fully dynamic algorithm for maintaining $(1+\epsilon)$-approximate<br>\emph{size} of maximum matching of the graph with $n$ vertices and $m$ edges<br>using $m^{0.5-\Omega_{\epsilon}(1)}$ update time. This is the first polynomial<br>improvement over the long-standing $O(n)$ update time, which can be trivially<br>obtained by periodic recomputation. Thus, we resolve the value version of a<br>major open question of the dynamic graph algorithms literature (see, e.g.,<br>[Gupta and Peng FOCS'13], [Bernstein and Stein SODA'16],[Behnezhad and Khanna<br>SODA'22]).<br> Our key technical component is the first sublinear algorithm for $(1,\epsilon<br>n)$-approximate maximum matching with sublinear running time on dense graphs.<br>All previous algorithms suffered a multiplicative approximation factor of at<br>least $1.499$ or assumed that the graph has a very small maximum degree.<br>
%K Computer Science, Data Structures and Algorithms, cs.DS
[9]
S. Bhattacharya, P. Kiss, and T. Saranurak, “Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, 2023.
Export
BibTeX
@inproceedings{BhattacharyaSODA23,
TITLE = {Dynamic Algorithms for Packing-Covering {LPs} via Multiplicative Weight},
AUTHOR = {Bhattacharya, Sayan and Kiss, Peter and Saranurak, Thatchaphol},
LANGUAGE = {eng},
ISBN = {978-1-61197-755-4},
DOI = {10.1137/1.9781611977554.ch1},
PUBLISHER = {SIAM},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
BOOKTITLE = {Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)},
EDITOR = {Bansal, Nikhil and Nagarajan, Viswanath},
PAGES = {1--47},
ADDRESS = {Florence, Italy},
}
Endnote
%0 Conference Proceedings
%A Bhattacharya, Sayan
%A Kiss, Peter
%A Saranurak, Thatchaphol
%+ External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-4333-F
%R 10.1137/1.9781611977554.ch1
%D 2023
%B Annual ACM-SIAM Symposium on Discrete Algorithms
%Z date of event: 2023-01-22 - 2023-01-25
%C Florence, Italy
%B Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms
%E Bansal, Nikhil; Nagarajan, Viswanath
%P 1 - 47
%I SIAM
%@ 978-1-61197-755-4
[10]
S. Bhattacharya, P. Kiss, T. Saranurak, and D. Wajc, “Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, 2023.
Export
BibTeX
@inproceedings{BhattacharyaSODA23b,
TITLE = {Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time},
AUTHOR = {Bhattacharya, Sayan and Kiss, Peter and Saranurak, Thatchaphol and Wajc, David},
LANGUAGE = {eng},
ISBN = {978-1-61197-755-4},
DOI = {10.1137/1.9781611977554.ch5},
PUBLISHER = {SIAM},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
BOOKTITLE = {Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)},
EDITOR = {Bansal, Nikhil and Nagarajan, Viswanath},
PAGES = {100--128},
ADDRESS = {Florence, Italy},
}
Endnote
%0 Conference Proceedings
%A Bhattacharya, Sayan
%A Kiss, Peter
%A Saranurak, Thatchaphol
%A Wajc, David
%+ External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
%T Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-4336-C
%R 10.1137/1.9781611977554.ch5
%D 2023
%B Annual ACM-SIAM Symposium on Discrete Algorithms
%Z date of event: 2023-01-22 - 2023-01-25
%C Florence, Italy
%B Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms
%E Bansal, Nikhil; Nagarajan, Viswanath
%P 100 - 128
%I SIAM
%@ 978-1-61197-755-4
[11]
J. Blikstad, T.-W. Tu, D. Nanongkai, and S. Mukhopadhyay, “Fast Algorithms via Dynamic-Oracle Matroids,” in Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), Orlando, FL, USA. (Accepted/in press)
Export
BibTeX
@inproceedings{Blikstad_STOC23,
TITLE = {Fast Algorithms via Dynamic-Oracle Matroids},
AUTHOR = {Blikstad, Joakim and Tu, Ta-Wei and Nanongkai, Danupon and Mukhopadhyay, Sagnik},
LANGUAGE = {eng},
PUBLISHER = {ACM},
YEAR = {2023},
PUBLREMARK = {Accepted},
MARGINALMARK = {$\bullet$},
BOOKTITLE = {Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023)},
ADDRESS = {Orlando, FL, USA},
}
Endnote
%0 Conference Proceedings
%A Blikstad, Joakim
%A Tu, Ta-Wei
%A Nanongkai, Danupon
%A Mukhopadhyay, Sagnik
%+ External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T Fast Algorithms via Dynamic-Oracle Matroids :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-8C18-C
%D 2023
%B 55th Annual ACM Symposium on Theory of Computing
%Z date of event: 2023-06-20 - 2023-06-23
%C Orlando, FL, USA
%B Proceedings of the 55th Annual ACM Symposium on Theory of Computing
%I ACM
[12]
J. Blikstad and P. Kiss, “Incremental (1 - ε)-approximate dynamic matching in O(poly(1/ε)) update time,” 2023. [Online]. Available: https://arxiv.org/abs/2302.08432. (arXiv: 2302.08432)
Abstract
In the dynamic approximate maximum bipartite matching problem we are given<br>bipartite graph $G$ undergoing updates and our goal is to maintain a matching<br>of $G$ which is large compared the maximum matching size $\mu(G)$. We define a<br>dynamic matching algorithm to be $\alpha$ (respectively $(\alpha,<br>\beta)$)-approximate if it maintains matching $M$ such that at all times $|M |<br>\geq \mu(G) \cdot \alpha$ (respectively $|M| \geq \mu(G) \cdot \alpha -<br>\beta$).<br> We present the first deterministic $(1-\epsilon )$-approximate dynamic<br>matching algorithm with $O(poly(\epsilon ^{-1}))$ amortized update time for<br>graphs undergoing edge insertions. Previous solutions either required<br>super-constant [Gupta FSTTCS'14, Bhattacharya-Kiss-Saranurak SODA'23] or<br>exponential in $1/\epsilon $<br>[Grandoni-Leonardi-Sankowski-Schwiegelshohn-Solomon SODA'19] update time. Our<br>implementation is arguably simpler than the mentioned algorithms and its<br>description is self contained. Moreover, we show that if we allow for additive<br>$(1, \epsilon \cdot n)$-approximation our algorithm seamlessly extends to also<br>handle vertex deletions, on top of edge insertions. This makes our algorithm<br>one of the few small update time algorithms for $(1-\epsilon )$-approximate<br>dynamic matching allowing for updates both increasing and decreasing the<br>maximum matching size of $G$ in a fully dynamic manner.<br>
Export
BibTeX
@online{Blikstad2302.08432,
TITLE = {Incremental $(1-\epsilon)$-approximate dynamic matching in $O(poly(1/\epsilon))$ update time},
AUTHOR = {Blikstad, Joakim and Kiss, Peter},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2302.08432},
EPRINT = {2302.08432},
EPRINTTYPE = {arXiv},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
ABSTRACT = {In the dynamic approximate maximum bipartite matching problem we are given<br>bipartite graph $G$ undergoing updates and our goal is to maintain a matching<br>of $G$ which is large compared the maximum matching size $\mu(G)$. We define a<br>dynamic matching algorithm to be $\alpha$ (respectively $(\alpha,<br>\beta)$)-approximate if it maintains matching $M$ such that at all times $|M |<br>\geq \mu(G) \cdot \alpha$ (respectively $|M| \geq \mu(G) \cdot \alpha -<br>\beta$).<br> We present the first deterministic $(1-\epsilon )$-approximate dynamic<br>matching algorithm with $O(poly(\epsilon ^{-1}))$ amortized update time for<br>graphs undergoing edge insertions. Previous solutions either required<br>super-constant [Gupta FSTTCS'14, Bhattacharya-Kiss-Saranurak SODA'23] or<br>exponential in $1/\epsilon $<br>[Grandoni-Leonardi-Sankowski-Schwiegelshohn-Solomon SODA'19] update time. Our<br>implementation is arguably simpler than the mentioned algorithms and its<br>description is self contained. Moreover, we show that if we allow for additive<br>$(1, \epsilon \cdot n)$-approximation our algorithm seamlessly extends to also<br>handle vertex deletions, on top of edge insertions. This makes our algorithm<br>one of the few small update time algorithms for $(1-\epsilon )$-approximate<br>dynamic matching allowing for updates both increasing and decreasing the<br>maximum matching size of $G$ in a fully dynamic manner.<br>},
}
Endnote
%0 Report
%A Blikstad, Joakim
%A Kiss, Peter
%+ External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Incremental (1 - ε)-approximate dynamic matching in O(poly(1/ε)) update time :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-A006-8
%U https://arxiv.org/abs/2302.08432
%D 2023
%X In the dynamic approximate maximum bipartite matching problem we are given<br>bipartite graph $G$ undergoing updates and our goal is to maintain a matching<br>of $G$ which is large compared the maximum matching size $\mu(G)$. We define a<br>dynamic matching algorithm to be $\alpha$ (respectively $(\alpha,<br>\beta)$)-approximate if it maintains matching $M$ such that at all times $|M |<br>\geq \mu(G) \cdot \alpha$ (respectively $|M| \geq \mu(G) \cdot \alpha -<br>\beta$).<br> We present the first deterministic $(1-\epsilon )$-approximate dynamic<br>matching algorithm with $O(poly(\epsilon ^{-1}))$ amortized update time for<br>graphs undergoing edge insertions. Previous solutions either required<br>super-constant [Gupta FSTTCS'14, Bhattacharya-Kiss-Saranurak SODA'23] or<br>exponential in $1/\epsilon $<br>[Grandoni-Leonardi-Sankowski-Schwiegelshohn-Solomon SODA'19] update time. Our<br>implementation is arguably simpler than the mentioned algorithms and its<br>description is self contained. Moreover, we show that if we allow for additive<br>$(1, \epsilon \cdot n)$-approximation our algorithm seamlessly extends to also<br>handle vertex deletions, on top of edge insertions. This makes our algorithm<br>one of the few small update time algorithms for $(1-\epsilon )$-approximate<br>dynamic matching allowing for updates both increasing and decreasing the<br>maximum matching size of $G$ in a fully dynamic manner.<br>
%K Computer Science, Data Structures and Algorithms, cs.DS
[13]
M. Briański, G. Joret, K. Majewski, P. Micek, M. T. Seweryn, and R. Sharma, “Treedepth Vs Circumference,” Combinatorica. (Accepted/in press)
Export
BibTeX
@article{Brianski23,
TITLE = {Treedepth Vs Circumference},
AUTHOR = {Bria{\'n}ski, Marcin and Joret, Gwena{\"e}l and Majewski, Konrad and Micek, Piotr and Seweryn, Micha{\l} T. and Sharma, Roohani},
LANGUAGE = {eng},
ISSN = {0209-9683},
PUBLISHER = {Springer},
ADDRESS = {Heidelberg},
YEAR = {2023},
PUBLREMARK = {Accepted},
MARGINALMARK = {$\bullet$},
JOURNAL = {Combinatorica},
}
Endnote
%0 Journal Article
%A Briański, Marcin
%A Joret, Gwenaël
%A Majewski, Konrad
%A Micek, Piotr
%A Seweryn, Michał T.
%A Sharma, Roohani
%+ External Organizations
External Organizations
External Organizations
External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Treedepth Vs Circumference :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-8E4E-E
%D 2023
%J Combinatorica
%I Springer
%C Heidelberg
%@ false
[14]
M. Briánski, G. Joret, K. Majewski, P. Micek, M. T. Seweryn, and R. Sharma, “Treedepth Versus Circumference,” Combinatorica, 2023.
Export
BibTeX
@article{Brianski23,
TITLE = {Treedepth Versus Circumference},
AUTHOR = {Bri{\'a}nski, Marcin and Joret, Gwenal and Majewski, Konrad and Micek, Piotr and Seweryn, Micha{\l} T. and Sharma, Roohani},
LANGUAGE = {eng},
ISSN = {0209-9683},
DOI = {10.1007/s00493-023-00028-5},
PUBLISHER = {Springer},
ADDRESS = {Heidelberg},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
JOURNAL = {Combinatorica},
}
Endnote
%0 Journal Article
%A Briánski, Marcin
%A Joret, Gwenal
%A Majewski, Konrad
%A Micek, Piotr
%A Seweryn, Michał T.
%A Sharma, Roohani
%+ External Organizations
External Organizations
External Organizations
External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Treedepth Versus Circumference :
%G eng
%U http://hdl.handle.net/21.11116/0000-000D-6343-8
%R 10.1007/s00493-023-00028-5
%7 2023
%D 2023
%J Combinatorica
%I Springer
%C Heidelberg
%@ false
%U https://rdcu.be/dfJGd
[15]
K. Bringmann, M. Kapralov, M. Makarov, V. Nakos, A. Yagudin, and A. Zandieh, “Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, 2023.
Export
BibTeX
@inproceedings{BringmannSODA23,
TITLE = {Traversing the {FFT} Computation Tree for Dimension-Independent Sparse {F}ourier Transforms},
AUTHOR = {Bringmann, Karl and Kapralov, Michael and Makarov, Mikhail and Nakos, Vasileios and Yagudin, Amir and Zandieh, Amir},
LANGUAGE = {eng},
ISBN = {978-1-61197-755-4},
DOI = {10.1137/1.9781611977554.ch177},
PUBLISHER = {SIAM},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
BOOKTITLE = {Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)},
EDITOR = {Bansal, Nikhil and Nagarajan, Viswanath},
PAGES = {4768--4845},
ADDRESS = {Florence, Italy},
}
Endnote
%0 Conference Proceedings
%A Bringmann, Karl
%A Kapralov, Michael
%A Makarov, Mikhail
%A Nakos, Vasileios
%A Yagudin, Amir
%A Zandieh, Amir
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-26DB-3
%R 10.1137/1.9781611977554.ch177
%D 2023
%B Annual ACM-SIAM Symposium on Discrete Algorithms
%Z date of event: 2023-01-22 - 2023-01-25
%C Florence, Italy
%B Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms
%E Bansal, Nikhil; Nagarajan, Viswanath
%P 4768 - 4845
%I SIAM
%@ 978-1-61197-755-4
[16]
K. Bringmann, V. Cohen-Addad, and D. Das, “A Linear-Time n0.4-Approximation for Longest Common Subsequence,” ACM Transactions on Algorithms, vol. 19, no. 1, 2023.
Export
BibTeX
@article{Bringmann_TOA23,
TITLE = {A Linear-Time $n^{0.4}$-Approximation for Longest Common Subsequence},
AUTHOR = {Bringmann, Karl and Cohen-Addad, Vincent and Das, Debarati},
LANGUAGE = {eng},
ISSN = {1549-6325},
DOI = {10.1145/3568398},
PUBLISHER = {ACM},
ADDRESS = {New York, NY},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
JOURNAL = {ACM Transactions on Algorithms},
VOLUME = {19},
NUMBER = {1},
PAGES = {1--24},
EID = {9},
}
Endnote
%0 Journal Article
%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-000C-A7EC-E
%R 10.1145/3568398
%7 2023
%D 2023
%J ACM Transactions on Algorithms
%V 19
%N 1
%& 1
%P 1 - 24
%Z sequence number: 9
%I ACM
%C New York, NY
%@ false
[17]
C. Coupette, S. Dalleiger, and B. Rieck, “Ollivier-Ricci Curvature for Hypergraphs: A Unified Framework,” in Eleventh International Conference on Learning Representations (ICLR 2023), Kigali, Rwanda. (Accepted/in press)
Abstract
Bridging geometry and topology, curvature is a powerful and expressive invariant. While the utility of curvature has been theoretically and empirically confirmed in the context of manifolds and graphs, its generalization to the emerging domain of hypergraphs has remained largely unexplored. On graphs, Ollivier-Ricci curvature measures differences between random walks via Wasserstein distances, thus grounding a geometric concept in ideas from probability and optimal transport. We develop ORCHID, a flexible framework generalizing Ollivier-Ricci curvature to hypergraphs, and prove that the resulting curvatures have favorable theoretical properties. Through extensive experiments on synthetic and real-world hypergraphs from different domains, we demonstrate that ORCHID curvatures are both scalable and useful to perform a variety of hypergraph tasks in practice.
Export
BibTeX
@inproceedings{Coupette_ICLR23,
TITLE = {{Ollivier-Ricc}i Curvature for Hypergraphs: {A} Unified Framework},
AUTHOR = {Coupette, Corinna and Dalleiger, Sebastian and Rieck, Bastian},
LANGUAGE = {eng},
PUBLISHER = {OpenReview.net},
YEAR = {2023},
PUBLREMARK = {Accepted},
MARGINALMARK = {$\bullet$},
ABSTRACT = {Bridging geometry and topology, curvature is a powerful and expressive invariant. While the utility of curvature has been theoretically and empirically confirmed in the context of manifolds and graphs, its generalization to the emerging domain of hypergraphs has remained largely unexplored. On graphs, Ollivier-Ricci curvature measures differences between random walks via Wasserstein distances, thus grounding a geometric concept in ideas from probability and optimal transport. We develop ORCHID, a flexible framework generalizing Ollivier-Ricci curvature to hypergraphs, and prove that the resulting curvatures have favorable theoretical properties. Through extensive experiments on synthetic and real-world hypergraphs from different domains, we demonstrate that ORCHID curvatures are both scalable and useful to perform a variety of hypergraph tasks in practice.},
BOOKTITLE = {Eleventh International Conference on Learning Representations (ICLR 2023)},
ADDRESS = {Kigali, Rwanda},
}
Endnote
%0 Conference Proceedings
%A Coupette, Corinna
%A Dalleiger, Sebastian
%A Rieck, Bastian
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
%T Ollivier-Ricci Curvature for Hypergraphs: A Unified Framework :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-10CD-B
%D 2023
%B Eleventh International Conference on Learning Representations
%Z date of event: 2023-05-01 - 2023-05-05
%C Kigali, Rwanda
%X Bridging geometry and topology, curvature is a powerful and expressive invariant. While the utility of curvature has been theoretically and empirically confirmed in the context of manifolds and graphs, its generalization to the emerging domain of hypergraphs has remained largely unexplored. On graphs, Ollivier-Ricci curvature measures differences between random walks via Wasserstein distances, thus grounding a geometric concept in ideas from probability and optimal transport. We develop ORCHID, a flexible framework generalizing Ollivier-Ricci curvature to hypergraphs, and prove that the resulting curvatures have favorable theoretical properties. Through extensive experiments on synthetic and real-world hypergraphs from different domains, we demonstrate that ORCHID curvatures are both scalable and useful to perform a variety of hypergraph tasks in practice.
%K Computer Science, Learning, cs.LG,cs.SI,Statistics, Machine Learning, stat.ML
%B Eleventh International Conference on Learning Representations
%I OpenReview.net
%U https://openreview.net/forum?id=sPCKNl5qDps
[18]
D. Das, J. Gilbert, M. Hajiaghayi, T. Kociumaka, and B. Saha, “Weighted Edit Distance Computation: Strings, Trees, and Dyck,” in Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), Orlando, FL, USA. (Accepted/in press)
Export
BibTeX
@inproceedings{Debarati_STOC23,
TITLE = {Weighted Edit Distance Computation: {S}trings, Trees, and {Dyck}},
AUTHOR = {Das, Debarati and Gilbert, Jacob and Hajiaghayi, MohammadTaghi and Kociumaka, Tomasz and Saha, Barna},
LANGUAGE = {eng},
PUBLISHER = {ACM},
YEAR = {2023},
PUBLREMARK = {Accepted},
MARGINALMARK = {$\bullet$},
BOOKTITLE = {Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023)},
ADDRESS = {Orlando, FL, USA},
}
Endnote
%0 Conference Proceedings
%A Das, Debarati
%A Gilbert, Jacob
%A Hajiaghayi, MohammadTaghi
%A Kociumaka, Tomasz
%A Saha, Barna
%+ External Organizations
External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T Weighted Edit Distance Computation: Strings, Trees, and Dyck :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-8B20-3
%D 2023
%B 55th Annual ACM Symposium on Theory of Computing
%Z date of event: 2023-06-20 - 2023-06-23
%C Orlando, FL, USA
%B Proceedings of the 55th Annual ACM Symposium on Theory of Computing
%I ACM
[19]
F. Dross, K. Fleszar, K. Węgrzycki, and A. Zych-Pawlewicz, “Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, 2023.
Export
BibTeX
@inproceedings{DrossSODA23,
TITLE = {Gap-{ETH}-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing {E}uclidean Travelling Salesman Tours},
AUTHOR = {Dross, Fran{\c c}ois and Fleszar, Krzysztof and W{\c e}grzycki, Karol and Zych-Pawlewicz, Anna},
LANGUAGE = {eng},
ISBN = {978-1-61197-755-4},
DOI = {10.1137/1.9781611977554.ch52},
PUBLISHER = {SIAM},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
BOOKTITLE = {Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)},
EDITOR = {Bansal, Nikhil and Nagarajan, Viswanath},
PAGES = {1433--1463},
ADDRESS = {Florence, Italy},
}
Endnote
%0 Conference Proceedings
%A Dross, François
%A Fleszar, Krzysztof
%A Węgrzycki, Karol
%A Zych-Pawlewicz, Anna
%+ External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-1F6C-A
%R 10.1137/1.9781611977554.ch52
%D 2023
%B Annual ACM-SIAM Symposium on Discrete Algorithms
%Z date of event: 2023-01-22 - 2023-01-25
%C Florence, Italy
%B Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms
%E Bansal, Nikhil; Nagarajan, Viswanath
%P 1433 - 1463
%I SIAM
%@ 978-1-61197-755-4
[20]
S. Fallat, D. Kirkpatrick, H. U. Simon, A. Soltani, and S. Zilles, “On Batch Teaching Without Collusion,” Journal of Machine Learning Research, vol. 24, 2023.
Export
BibTeX
@article{Fallat23,
TITLE = {On Batch Teaching Without Collusion},
AUTHOR = {Fallat, Shaun and Kirkpatrick, David and Simon, Hans U. and Soltani, Abolghasem and Zilles, Sandra},
LANGUAGE = {eng},
ISSN = {1532-4435},
URL = {http://jmlr.org/papers/v24/22-0330.html},
PUBLISHER = {Microtome Publishing},
ADDRESS = {Brookline, MA},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
JOURNAL = {Journal of Machine Learning Research},
VOLUME = {24},
PAGES = {1--33},
}
Endnote
%0 Journal Article
%A Fallat, Shaun
%A Kirkpatrick, David
%A Simon, Hans U.
%A Soltani, Abolghasem
%A Zilles, Sandra
%+ External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
%T On Batch Teaching Without Collusion :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-7CCF-1
%U http://jmlr.org/papers/v24/22-0330.html
%7 2023
%D 2023
%J Journal of Machine Learning Research
%V 24
%& 1
%P 1 - 33
%I Microtome Publishing
%C Brookline, MA
%@ false
[21]
J. Focke, D. Marx, F. M. Inerney, D. Neuen, G. S. Sankar, P. Schepper, and P. Wellnitz, “Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, 2023.
Export
BibTeX
@inproceedings{FockeSODA23,
TITLE = {Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs},
AUTHOR = {Focke, Jacob and Marx, D{\'a}niel and Inerney, Fionn Mc and Neuen, Daniel and Sankar, Govind S. and Schepper, Philipp and Wellnitz, Philip},
LANGUAGE = {eng},
ISBN = {978-1-61197-755-4},
DOI = {10.1137/1.9781611977554.ch140},
PUBLISHER = {SIAM},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
BOOKTITLE = {Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)},
EDITOR = {Bansal, Nikhil and Nagarajan, Viswanath},
PAGES = {3664--3683},
ADDRESS = {Florence, Italy},
}
Endnote
%0 Conference Proceedings
%A Focke, Jacob
%A Marx, Dániel
%A Inerney, Fionn Mc
%A Neuen, Daniel
%A Sankar, Govind S.
%A Schepper, Philipp
%A Wellnitz, Philip
%+ External Organizations
External Organizations
External Organizations
External Organizations
External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-1EA4-A
%R 10.1137/1.9781611977554.ch140
%D 2023
%B Annual ACM-SIAM Symposium on Discrete Algorithms
%Z date of event: 2023-01-22 - 2023-01-25
%C Florence, Italy
%B Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms
%E Bansal, Nikhil; Nagarajan, Viswanath
%P 3664 - 3683
%I SIAM
%@ 978-1-61197-755-4
[22]
Y. Gao, R. Kyng, and D. A. Spielman, “Robust and Practical Solution of Laplacian Equations by Approximate Elimination,” 2023. [Online]. Available: https://arxiv.org/abs/2303.00709. (arXiv: 2303.00709)
Abstract
We introduce a new algorithm and software for solving linear equations in<br>symmetric diagonally dominant matrices with non-positive off-diagonal entries<br>(SDDM matrices), including Laplacian matrices. We use pre-conditioned conjugate<br>gradient (PCG) to solve the system of linear equations. Our preconditioner is a<br>variant of the Approximate Cholesky factorization of Kyng and Sachdeva (FOCS<br>2016). Our factorization approach is simple: we eliminate matrix rows/columns<br>one at a time and update the remaining matrix using sampling to approximate the<br>outcome of complete Cholesky factorization. Unlike earlier approaches, our<br>sampling always maintains a connectivity in the remaining non-zero structure.<br>Our algorithm comes with a tuning parameter that upper bounds the number of<br>samples made per original entry. We implement our algorithm in Julia, providing<br>two versions, AC and AC2, that respectively use 1 and 2 samples per original<br>entry. We compare their single-threaded performance to that of current<br>state-of-the-art solvers Combinatorial Multigrid (CMG),<br>BoomerAMG-preconditioned Krylov solvers from HyPre and PETSc, Lean Algebraic<br>Multigrid (LAMG), and MATLAB's with Incomplete Cholesky Factorization (ICC).<br>Our evaluation uses a broad class of problems, including all large SDDM<br>matrices from the SuiteSparse collection and diverse programmatically generated<br>instances. Our experiments suggest that our algorithm attains a level of<br>robustness and reliability not seen before in SDDM solvers, while retaining<br>good performance across all instances. Our code and data are public, and we<br>provide a tutorial on how to replicate our tests. We hope that others will<br>adopt this suite of tests as a benchmark, which we refer to as SDDM2023. Our<br>solver code is available at: https://github.com/danspielman/Laplacians.jl/ Our<br>benchmarking data and tutorial are available at:<br>https://rjkyng.github.io/SDDM2023/<br>
Export
BibTeX
@online{Yuan_2303.00709,
TITLE = {Robust and Practical Solution of Laplacian Equations by Approximate Elimination},
AUTHOR = {Gao, Yuan and Kyng, Rasmus and Spielman, Daniel A.},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2303.00709},
EPRINT = {2303.00709},
EPRINTTYPE = {arXiv},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
ABSTRACT = {We introduce a new algorithm and software for solving linear equations in<br>symmetric diagonally dominant matrices with non-positive off-diagonal entries<br>(SDDM matrices), including Laplacian matrices. We use pre-conditioned conjugate<br>gradient (PCG) to solve the system of linear equations. Our preconditioner is a<br>variant of the Approximate Cholesky factorization of Kyng and Sachdeva (FOCS<br>2016). Our factorization approach is simple: we eliminate matrix rows/columns<br>one at a time and update the remaining matrix using sampling to approximate the<br>outcome of complete Cholesky factorization. Unlike earlier approaches, our<br>sampling always maintains a connectivity in the remaining non-zero structure.<br>Our algorithm comes with a tuning parameter that upper bounds the number of<br>samples made per original entry. We implement our algorithm in Julia, providing<br>two versions, AC and AC2, that respectively use 1 and 2 samples per original<br>entry. We compare their single-threaded performance to that of current<br>state-of-the-art solvers Combinatorial Multigrid (CMG),<br>BoomerAMG-preconditioned Krylov solvers from HyPre and PETSc, Lean Algebraic<br>Multigrid (LAMG), and MATLAB's with Incomplete Cholesky Factorization (ICC).<br>Our evaluation uses a broad class of problems, including all large SDDM<br>matrices from the SuiteSparse collection and diverse programmatically generated<br>instances. Our experiments suggest that our algorithm attains a level of<br>robustness and reliability not seen before in SDDM solvers, while retaining<br>good performance across all instances. Our code and data are public, and we<br>provide a tutorial on how to replicate our tests. We hope that others will<br>adopt this suite of tests as a benchmark, which we refer to as SDDM2023. Our<br>solver code is available at: https://github.com/danspielman/Laplacians.jl/ Our<br>benchmarking data and tutorial are available at:<br>https://rjkyng.github.io/SDDM2023/<br>},
}
Endnote
%0 Report
%A Gao, Yuan
%A Kyng, Rasmus
%A Spielman, Daniel A.
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
%T Robust and Practical Solution of Laplacian Equations by Approximate
Elimination :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-B1C8-A
%U https://arxiv.org/abs/2303.00709
%D 2023
%X We introduce a new algorithm and software for solving linear equations in<br>symmetric diagonally dominant matrices with non-positive off-diagonal entries<br>(SDDM matrices), including Laplacian matrices. We use pre-conditioned conjugate<br>gradient (PCG) to solve the system of linear equations. Our preconditioner is a<br>variant of the Approximate Cholesky factorization of Kyng and Sachdeva (FOCS<br>2016). Our factorization approach is simple: we eliminate matrix rows/columns<br>one at a time and update the remaining matrix using sampling to approximate the<br>outcome of complete Cholesky factorization. Unlike earlier approaches, our<br>sampling always maintains a connectivity in the remaining non-zero structure.<br>Our algorithm comes with a tuning parameter that upper bounds the number of<br>samples made per original entry. We implement our algorithm in Julia, providing<br>two versions, AC and AC2, that respectively use 1 and 2 samples per original<br>entry. We compare their single-threaded performance to that of current<br>state-of-the-art solvers Combinatorial Multigrid (CMG),<br>BoomerAMG-preconditioned Krylov solvers from HyPre and PETSc, Lean Algebraic<br>Multigrid (LAMG), and MATLAB's with Incomplete Cholesky Factorization (ICC).<br>Our evaluation uses a broad class of problems, including all large SDDM<br>matrices from the SuiteSparse collection and diverse programmatically generated<br>instances. Our experiments suggest that our algorithm attains a level of<br>robustness and reliability not seen before in SDDM solvers, while retaining<br>good performance across all instances. Our code and data are public, and we<br>provide a tutorial on how to replicate our tests. We hope that others will<br>adopt this suite of tests as a benchmark, which we refer to as SDDM2023. Our<br>solver code is available at: https://github.com/danspielman/Laplacians.jl/ Our<br>benchmarking data and tutorial are available at:<br>https://rjkyng.github.io/SDDM2023/<br>
%K Mathematics, Numerical Analysis, math.NA,Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Mathematical Software, cs.MS,Computer Science, Numerical Analysis, cs.NA
[23]
J. Garg, M. Hoefer, and K. Mehlhorn, “Satiation in Fisher Markets and Approximation of Nash Social Welfare,” Mathematics of Operations Research, 2023.
Export
BibTeX
@article{Garg23x,
TITLE = {Satiation in {F}isher Markets and Approximation of {N}ash Social Welfare},
AUTHOR = {Garg, Jugal and Hoefer, Martin and Mehlhorn, Kurt},
LANGUAGE = {eng},
ISSN = {0364-765X},
DOI = {10.1287/moor.2019.0129},
PUBLISHER = {INFORMS},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
JOURNAL = {Mathematics of Operations Research},
}
Endnote
%0 Journal Article
%A Garg, Jugal
%A Hoefer, Martin
%A Mehlhorn, Kurt
%+ 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 Satiation in Fisher Markets and Approximation of Nash Social Welfare :
%G eng
%U http://hdl.handle.net/21.11116/0000-000D-944A-9
%R 10.1287/moor.2019.0129
%7 2023
%D 2023
%J Mathematics of Operations Research
%I INFORMS
%@ false
[24]
P. Gawrychowski, T. Kociumaka, W. Rytter, and T. Waleń, “Tight Bound for the Number of Distinct Palindromes in a Tree,” The Electronic Journal of Combinatorics, vol. 30, no. 2, 2023.
Export
BibTeX
@article{Gawrychowski23,
TITLE = {Tight Bound for the Number of Distinct Palindromes in a Tree},
AUTHOR = {Gawrychowski, Pawe{\l} and Kociumaka, Tomasz and Rytter, Wojciech and Wale{\'n}, Tomasz},
LANGUAGE = {eng},
ISSN = {1077-8926},
DOI = {10.37236/10842},
PUBLISHER = {N.J. Calkin and H.S. Wilf},
ADDRESS = {Atlanta, Ga.},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
JOURNAL = {The Electronic Journal of Combinatorics},
VOLUME = {30},
NUMBER = {2},
EID = {P2.10},
}
Endnote
%0 Journal Article
%A Gawrychowski, Paweł
%A Kociumaka, Tomasz
%A Rytter, Wojciech
%A Waleń, Tomasz
%+ External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
%T Tight Bound for the Number of Distinct Palindromes in a Tree :
%G eng
%U http://hdl.handle.net/21.11116/0000-000D-1B73-4
%R 10.37236/10842
%7 2023
%D 2023
%J The Electronic Journal of Combinatorics
%V 30
%N 2
%Z sequence number: P2.10
%I N.J. Calkin and H.S. Wilf
%C Atlanta, Ga.
%@ false
[25]
A. Gionis, K. Khodamoradi, B. Ordozgoiti, B. Riegel, and J. Spoerhase, “A Constant-Factor Approximation Algorithm for Reconciliation k-Median,” in Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS 2023), Valencia, Spain. (Accepted/in press)
Export
BibTeX
@inproceedings{Gionis_AISTATS2023,
TITLE = {A Constant-Factor Approximation Algorithm for Reconciliation $k$-Median},
AUTHOR = {Gionis, Aristides and Khodamoradi, Kamyar and Ordozgoiti, Bruno and Riegel, Benedikt and Spoerhase, Joachim},
LANGUAGE = {eng},
PUBLISHER = {PMLR},
YEAR = {2023},
PUBLREMARK = {Accepted},
MARGINALMARK = {$\bullet$},
BOOKTITLE = {Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS 2023)},
SERIES = {Proceedings of the Machine Learning Research},
ADDRESS = {Valencia, Spain},
}
Endnote
%0 Conference Proceedings
%A Gionis, Aristides
%A Khodamoradi, Kamyar
%A Ordozgoiti, Bruno
%A Riegel, Benedikt
%A Spoerhase, Joachim
%+ External Organizations
External Organizations
External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T A Constant-Factor Approximation Algorithm for Reconciliation k-Median :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-739D-2
%D 2023
%B 26th International Conference on Artificial Intelligence and Statistics
%Z date of event: 2023-04-25 - 2023-04-27
%C Valencia, Spain
%B Proceedings of the 26th International Conference on Artificial Intelligence and Statistics
%I PMLR
%B Proceedings of the Machine Learning Research
[26]
E. Goldenberg, T. Kociumaka, R. Krauthgamer, and B. Saha, “An Algorithmic Bridge Between Hamming and Levenshtein Distances,” in 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), Cambridge, MA, USA, 2023.
Export
BibTeX
@inproceedings{Goldenberg_ITCS23,
TITLE = {An Algorithmic Bridge Between {H}amming and {L}evenshtein Distances},
AUTHOR = {Goldenberg, Elazar and Kociumaka, Tomasz and Krauthgamer, Robert and Saha, Barna},
LANGUAGE = {eng},
ISBN = {978-3-95977-263-1},
URL = {urn:nbn:de:0030-drops-175615},
DOI = {10.4230/LIPIcs.ITCS.2023.58},
PUBLISHER = {Schloss Dagstuhl},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
BOOKTITLE = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
EDITOR = {Tauman Kalai, Yael},
PAGES = {1--23},
EID = {58},
SERIES = {Leibniz International Proceedings in Informatics},
ADDRESS = {Cambridge, MA, USA},
}
Endnote
%0 Conference Proceedings
%A Goldenberg, Elazar
%A Kociumaka, Tomasz
%A Krauthgamer, Robert
%A Saha, Barna
%+ External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
%T An Algorithmic Bridge Between Hamming and Levenshtein Distances :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-1588-3
%R 10.4230/LIPIcs.ITCS.2023.58
%U urn:nbn:de:0030-drops-175615
%D 2023
%B 14th Innovations in Theoretical Computer Science Conference
%Z date of event: 2023-01-10 - 2023-01-13
%C Cambridge, MA, USA
%B 14th Innovations in Theoretical Computer Science Conference
%E Tauman Kalai, Yael
%P 1 - 23
%Z sequence number: 58
%I Schloss Dagstuhl
%@ 978-3-95977-263-1
%B Leibniz International Proceedings in Informatics
%U https://drops.dagstuhl.de/opus/volltexte/2023/17561/
[27]
G. Goranci, M. Henzinger, D. Nanongkai, T. Saranurak, M. Thorup, and C. Wulff, “Fully Dynamic Exact Edge Connectivity in Sublinear Time,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, 2023.
Export
BibTeX
@inproceedings{GoranciSODA23,
TITLE = {Fully Dynamic Exact Edge Connectivity in Sublinear Time},
AUTHOR = {Goranci, Gramoz and Henzinger, Monika and Nanongkai, Danupon and Saranurak, Thatchaphol and Thorup, Mikkel and Wulff, Christian},
LANGUAGE = {eng},
ISBN = {978-1-61197-755-4},
DOI = {10.1137/1.9781611977554.ch3},
PUBLISHER = {SIAM},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
BOOKTITLE = {Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)},
EDITOR = {Bansal, Nikhil and Nagarajan, Viswanath},
PAGES = {70--86},
ADDRESS = {Florence, Italy},
}
Endnote
%0 Conference Proceedings
%A Goranci, Gramoz
%A Henzinger, Monika
%A Nanongkai, Danupon
%A Saranurak, Thatchaphol
%A Thorup, Mikkel
%A Wulff, Christian
%+ External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
External Organizations
%T Fully Dynamic Exact Edge Connectivity in Sublinear Time :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-9383-9
%R 10.1137/1.9781611977554.ch3
%D 2023
%B Annual ACM-SIAM Symposium on Discrete Algorithms
%Z date of event: 2023-01-22 - 2023-01-25
%C Florence, Italy
%B Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms
%E Bansal, Nikhil; Nagarajan, Viswanath
%P 70 - 86
%I SIAM
%@ 978-1-61197-755-4
%U https://epubs.siam.org/doi/reader/10.1137/1.9781611977554.ch3
[28]
T. Gouleakis, K. Lakis, and G. Shahkarami, “Learning-Augmented Algorithms for Online TSP on the Line,” in Proceedings of the 37th AAAI Conference on Artificial Intelligence, Washington, DC, USA. (Accepted/in press)
Export
BibTeX
@inproceedings{Gouleakis_AAAI23,
TITLE = {Learning-Augmented Algorithms for Online {TSP} on the Line},
AUTHOR = {Gouleakis, Themis and Lakis, Konstantinos and Shahkarami, Golnoosh},
LANGUAGE = {eng},
PUBLISHER = {AAAI},
YEAR = {2023},
PUBLREMARK = {Accepted},
MARGINALMARK = {$\bullet$},
BOOKTITLE = {Proceedings of the 37th AAAI Conference on Artificial Intelligence},
ADDRESS = {Washington, DC, USA},
}
Endnote
%0 Conference Proceedings
%A Gouleakis, Themis
%A Lakis, Konstantinos
%A Shahkarami, Golnoosh
%+ External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Learning-Augmented Algorithms for Online TSP on the Line :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-466C-D
%D 2023
%B 37th AAAI Conference on Artificial Intelligence
%Z date of event: 2023-02-07 - 2023-02-14
%C Washington, DC, USA
%B Proceedings of the 37th AAAI Conference on Artificial Intelligence
%I AAAI
[29]
G. Gutowski, F. Mittelstädt, I. Rutter, J. Spoerhase, A. Wolff, and J. Zink, “Coloring Mixed and Directional Interval Graphs,” in Graph Drawing and Network Visualization (GD 2022), Tokyo, Japan, 2023.
Export
BibTeX
@inproceedings{gutowski-etal22:gd,
TITLE = {Coloring Mixed and Directional Interval Graphs},
AUTHOR = {Gutowski, Grzegorz and Mittelst{\"a}dt, Florian and Rutter, Ignaz and Spoerhase, Joachim and Wolff, Alexander and Zink, Johannes},
LANGUAGE = {eng},
ISBN = {978-3-031-22202-3},
DOI = {10.1007/978-3-031-22203-0_30},
PUBLISHER = {Springer},
YEAR = {2022},
MARGINALMARK = {$\bullet$},
DATE = {2023},
BOOKTITLE = {Graph Drawing and Network Visualization (GD 2022)},
EDITOR = {Angelini, Patrizio and von Hanxleden, Reinhard},
PAGES = {418--431},
SERIES = {Lecture Notes in Computer Science},
VOLUME = {13764},
ADDRESS = {Tokyo, Japan},
}
Endnote
%0 Conference Proceedings
%A Gutowski, Grzegorz
%A Mittelstädt, Florian
%A Rutter, Ignaz
%A Spoerhase, Joachim
%A Wolff, Alexander
%A Zink, Johannes
%+ External Organizations
External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
%T Coloring Mixed and Directional Interval Graphs :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-26A4-0
%R 10.1007/978-3-031-22203-0_30
%D 2023
%B 30th International Symposium on Graph Drawing and Network Visualization
%Z date of event: 2022-09-13 - 2022-09-16
%C Tokyo, Japan
%B Graph Drawing and Network Visualization
%E Angelini, Patrizio; von Hanxleden, Reinhard
%P 418 - 431
%I Springer
%@ 978-3-031-22202-3
%B Lecture Notes in Computer Science
%N 13764
[30]
M. Hatzel, L. Jaffke, P. T. Lima, T. Masařík, M. Pilipczuk, R. Sharma, and M. Sorge, “Fixed-Parameter Tractability of Directed Multicut with Three Terminal Pairs Parameterized by the Size of the Cutset: Twin-width Meets Flow-Augmentation,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, 2023.
Export
BibTeX
@inproceedings{Hatzel_SODA23,
TITLE = {Fixed-parameter tractability of {DIRECTED MULTICUT} with three terminal pairs parameterized by the size of the cutset: {T}win-width meets flow-augmentation},
AUTHOR = {Hatzel, Meike and Jaffke, Lars and Lima, Paloma T. and Masa{\v r}{\'i}k, Tom{\'a}{\v s} and Pilipczuk, Marcin and Sharma, Roohani and Sorge, Manuel},
LANGUAGE = {eng},
ISBN = {978-1-61197-755-4},
DOI = {10.1137/1.9781611977554.ch123},
PUBLISHER = {SIAM},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
BOOKTITLE = {Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)},
EDITOR = {Bansal, Nikhil and Nagarajan, Viswanath},
PAGES = {3229--3244},
ADDRESS = {Florence, Italy},
}
Endnote
%0 Conference Proceedings
%A Hatzel, Meike
%A Jaffke, Lars
%A Lima, Paloma T.
%A Masařík, Tomáš
%A Pilipczuk, Marcin
%A Sharma, Roohani
%A Sorge, Manuel
%+ External Organizations
External Organizations
External Organizations
External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T Fixed-Parameter Tractability of Directed Multicut with Three Terminal
Pairs Parameterized by the Size of the Cutset: Twin-width Meets
Flow-Augmentation :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-8E4C-0
%R 10.1137/1.9781611977554.ch123
%D 2023
%B Annual ACM-SIAM Symposium on Discrete Algorithms
%Z date of event: 2023-01-22 - 2023-01-25
%C Florence, Italy
%B Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms
%E Bansal, Nikhil; Nagarajan, Viswanath
%P 3229 - 3244
%I SIAM
%@ 978-1-61197-755-4
[31]
Y. Jiang and S. Mukhopadhyay, “Finding a Small Vertex Cut on Distributed Networks,” in Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), Orlando, FL, USA. (Accepted/in press)
Export
BibTeX
@inproceedings{Jiang_STOC23,
TITLE = {Finding a Small Vertex Cut on Distributed Networks},
AUTHOR = {Jiang, Yonggang and Mukhopadhyay, Sagnik},
LANGUAGE = {eng},
PUBLISHER = {ACM},
YEAR = {2023},
PUBLREMARK = {Accepted},
MARGINALMARK = {$\bullet$},
BOOKTITLE = {Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023)},
ADDRESS = {Orlando, FL, USA},
}
Endnote
%0 Conference Proceedings
%A Jiang, Yonggang
%A Mukhopadhyay, Sagnik
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T Finding a Small Vertex Cut on Distributed Networks :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-947A-4
%D 2023
%B 55th Annual ACM Symposium on Theory of Computing
%Z date of event: 2023-06-20 - 2023-06-23
%C Orlando, FL, USA
%B Proceedings of the 55th Annual ACM Symposium on Theory of Computing
%I ACM
[32]
D. Kempa and T. Kociumaka, “Breaking the O(n)-Barrier in the Construction of Compressed Suffix Arrays,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, 2023.
Export
BibTeX
@inproceedings{KempaSODA23,
TITLE = {Breaking the {$O(n)$}-{B}arrier in the Construction of Compressed Suffix Arrays},
AUTHOR = {Kempa, Dominik and Kociumaka, Tomasz},
LANGUAGE = {eng},
ISBN = {978-1-61197-755-4},
DOI = {10.1137/1.9781611977554.ch187},
PUBLISHER = {SIAM},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
BOOKTITLE = {Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)},
EDITOR = {Bansal, Nikhil and Nagarajan, Viswanath},
PAGES = {5122--5202},
ADDRESS = {Florence, Italy},
}
Endnote
%0 Conference Proceedings
%A Kempa, Dominik
%A Kociumaka, Tomasz
%+ External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Breaking the O(n)-Barrier in the Construction of Compressed Suffix
Arrays :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-158F-C
%R 10.1137/1.9781611977554.ch187
%D 2023
%B Annual ACM-SIAM Symposium on Discrete Algorithms
%Z date of event: 2023-01-22 - 2023-01-25
%C Florence, Italy
%B Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms
%E Bansal, Nikhil; Nagarajan, Viswanath
%P 5122 - 5202
%I SIAM
%@ 978-1-61197-755-4
[33]
P. Kleer and H. U. Simon, “Primal and Dual Combinatorial Dimensions,” Discrete Applied Mathematics, vol. 327, 2023.
Export
BibTeX
@article{Kleer2023,
TITLE = {Primal and Dual Combinatorial Dimensions},
AUTHOR = {Kleer, Pieter and Simon, Hans U.},
LANGUAGE = {eng},
ISSN = {0166-218X},
DOI = {10.1016/j.dam.2022.11.010},
PUBLISHER = {Elsevier},
ADDRESS = {Amsterdam},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
JOURNAL = {Discrete Applied Mathematics},
VOLUME = {327},
PAGES = {185--196},
}
Endnote
%0 Journal Article
%A Kleer, Pieter
%A Simon, Hans U.
%+ External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Primal and Dual Combinatorial Dimensions :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-15FE-F
%R 10.1016/j.dam.2022.11.010
%7 2023
%D 2023
%J Discrete Applied Mathematics
%V 327
%& 185
%P 185 - 196
%I Elsevier
%C Amsterdam
%@ false
[34]
J. Li, D. Nanongkai, D. Panigrahi, and T. Saranurak, “Near-Linear Time Approximations for Cut Problems via Fair Cuts,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, 2023.
Export
BibTeX
@inproceedings{LiSODA23,
TITLE = {Near-Linear Time Approximations for Cut Problems via Fair Cuts},
AUTHOR = {Li, Jason and Nanongkai, Danupon and Panigrahi, Debmalya and Saranurak, Thatchaphol},
LANGUAGE = {eng},
ISBN = {978-1-61197-755-4},
DOI = {10.1137/1.9781611977554.ch10},
PUBLISHER = {SIAM},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
BOOKTITLE = {Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)},
EDITOR = {Bansal, Nikhil and Nagarajan, Viswanath},
PAGES = {240--257},
ADDRESS = {Florence, Italy},
}
Endnote
%0 Conference Proceedings
%A Li, Jason
%A Nanongkai, Danupon
%A Panigrahi, Debmalya
%A Saranurak, Thatchaphol
%+ External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
%T Near-Linear Time Approximations for Cut Problems via Fair Cuts :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-9381-B
%R 10.1137/1.9781611977554.ch10
%D 2023
%B Annual ACM-SIAM Symposium on Discrete Algorithms
%Z date of event: 2023-01-22 - 2023-01-25
%C Florence, Italy
%B Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms
%E Bansal, Nikhil; Nagarajan, Viswanath
%P 240 - 257
%I SIAM
%@ 978-1-61197-755-4
%U https://epubs.siam.org/doi/pdf/10.1137/1.9781611977554.ch10?download=true
[35]
F. Mazowiecki, H. Sinclair-Banks, and K. Węgrzycki, “Coverability in 2-VASS with One Unary Counter is in NP,” in Foundations of Software Science and Computation Structures (FoSSaCS 2023), Paris, France, 2023.
Export
BibTeX
@inproceedings{Mazowieckie_FoSSaCS23,
TITLE = {Coverability in 2-{VASS} with One Unary Counter is in {NP}},
AUTHOR = {Mazowiecki, Filip and Sinclair-Banks, Henry and W{\c e}grzycki, Karol},
LANGUAGE = {eng},
ISBN = {978-3-031-30828-4},
DOI = {10.1007/978-3-031-30829-1_10},
PUBLISHER = {Springer},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
DATE = {2023},
BOOKTITLE = {Foundations of Software Science and Computation Structures (FoSSaCS 2023)},
EDITOR = {Kupferman, Orna and Sobocinski, Pawel},
PAGES = {196--217},
SERIES = {Lecture Notes in Computer Science},
VOLUME = {13992},
ADDRESS = {Paris, France},
}
Endnote
%0 Conference Proceedings
%A Mazowiecki, Filip
%A Sinclair-Banks, Henry
%A Węgrzycki, Karol
%+ External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Coverability in 2-VASS with One Unary Counter is in NP : Coverability in 2-{VASS} with One Unary Counter is in {NP}
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-4678-F
%R 10.1007/978-3-031-30829-1_10
%D 2023
%B 26th International Conference on Foundations of Software Science and Computation Structures
%Z date of event: 2023-04-22 - 2023-04-27
%C Paris, France
%B Foundations of Software Science and Computation Structures
%E Kupferman, Orna; Sobocinski, Pawel
%P 196 - 217
%I Springer
%@ 978-3-031-30828-4
%B Lecture Notes in Computer Science
%N 13992
[36]
P. Misra, S. Saket, R. Sharma, and M. Zehavi, “Sub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number,” Algorithmica, 2023.
Export
BibTeX
@article{Misra23b,
TITLE = {Sub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number},
AUTHOR = {Misra, Pranabendu and Saket, Saurabh and Sharma, Roohani and Zehavi, Meirav},
LANGUAGE = {eng},
ISSN = {0178-4617},
DOI = {10.1007/s00453-022-01093-w},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
JOURNAL = {Algorithmica},
}
Endnote
%0 Journal Article
%A Misra, Pranabendu
%A Saket, Saurabh
%A Sharma, Roohani
%A Zehavi, Meirav
%+ External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T Sub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-9037-3
%R 10.1007/s00453-022-01093-w
%7 2023
%D 2023
%J Algorithmica
%I Springer-Verlag
%C New York
%@ false
[37]
J. Olkowski, M. Pilipczuk, M. Rychlicki, K. Węgrzycki, and A. Zych-Pawlewicz, “Dynamic Data Structures for Parameterized String Problems,” in 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), Hamburg, Germany, 2023.
Export
BibTeX
@inproceedings{OlkowskiSTACS23,
TITLE = {Dynamic Data Structures for Parameterized String Problems},
AUTHOR = {Olkowski, J{\c e}drzej and Pilipczuk, Micha{\l} and Rychlicki, Mateusz and W{\c e}grzycki, Karol and Zych-Pawlewicz, Anna},
LANGUAGE = {eng},
ISSN = {1868-8969},
ISBN = {978-3-95977-266-2},
URL = {urn:nbn:de:0030-drops-177026},
DOI = {10.4230/LIPIcs.STACS.2023.50},
PUBLISHER = {Schloss Dagstuhl},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
BOOKTITLE = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
EDITOR = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant{\'e}, Mamadou Moustapha},
PAGES = {1--22},
EID = {50},
SERIES = {Leibniz International Proceedings in Informatics},
VOLUME = {254},
ADDRESS = {Hamburg, Germany},
}
Endnote
%0 Conference Proceedings
%A Olkowski, Jędrzej
%A Pilipczuk, Michał
%A Rychlicki, Mateusz
%A Węgrzycki, Karol
%A Zych-Pawlewicz, Anna
%+ External Organizations
External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T Dynamic Data Structures for Parameterized String Problems :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-1F0E-4
%R 10.4230/LIPIcs.STACS.2023.50
%U urn:nbn:de:0030-drops-177026
%D 2023
%B 40th International Symposium on Theoretical Aspects of Computer Science
%Z date of event: 2023-03-07 - 2023-03-09
%C Hamburg, Germany
%B 40th International Symposium on Theoretical Aspects of Computer Science
%E Berenbrink, Petra; Bouyer, Patricia; Dawar, Anuj; Kanté, Mamadou Moustapha
%P 1 - 22
%Z sequence number: 50
%I Schloss Dagstuhl
%@ 978-3-95977-266-2
%B Leibniz International Proceedings in Informatics
%N 254
%@ false
[38]
N. Peyerimhoff, M. Roth, J. Schmitt, J. Stix, A. Vdovina, and P. Wellnitz, “Parameterized Counting and Cayley Graph Expanders,” SIAM Journal on Discrete Mathematics, vol. 37, no. 2, 2023.
Export
BibTeX
@article{Peyerimhoff23,
TITLE = {Parameterized Counting and {C}ayley Graph Expanders},
AUTHOR = {Peyerimhoff, Norbert and Roth, Marc and Schmitt, Johannes and Stix, Jakob and Vdovina, Alina and Wellnitz, Philip},
LANGUAGE = {eng},
ISSN = {0895-4801},
DOI = {10.1137/22M1479804},
PUBLISHER = {SIAM},
ADDRESS = {Philadelphia, Pa.},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
JOURNAL = {SIAM Journal on Discrete Mathematics},
VOLUME = {37},
NUMBER = {2},
PAGES = {405--486},
}
Endnote
%0 Journal Article
%A Peyerimhoff, Norbert
%A Roth, Marc
%A Schmitt, Johannes
%A Stix, Jakob
%A Vdovina, Alina
%A Wellnitz, Philip
%+ External Organizations
External Organizations
External Organizations
External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Parameterized Counting and Cayley Graph Expanders :
%G eng
%U http://hdl.handle.net/21.11116/0000-000D-6355-4
%R 10.1137/22M1479804
%7 2023
%D 2023
%J SIAM Journal on Discrete Mathematics
%V 37
%N 2
%& 405
%P 405 - 486
%I SIAM
%C Philadelphia, Pa.
%@ false
[39]
H. U. Simon, “Tournaments, Johnson Graphs, and NC-Teaching,” in Proceedings of the 34th International Conference on Algorithmic Learning Theory (ALT 2023), Singapore, Singapore, 2023.
Export
BibTeX
@inproceedings{SimonALT23,
TITLE = {Tournaments, {Johnson} Graphs, and {NC}-Teaching},
AUTHOR = {Simon, Hans U.},
LANGUAGE = {eng},
PUBLISHER = {PMLR},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
BOOKTITLE = {Proceedings of the 34th International Conference on Algorithmic Learning Theory (ALT 2023)},
EDITOR = {Agrawal, Shipra and Orabona, Francesco},
PAGES = {1411--1428},
SERIES = {Proceedings of the Machine Learning Research},
VOLUME = {201},
ADDRESS = {Singapore, Singapore},
}
Endnote
%0 Conference Proceedings
%A Simon, Hans U.
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Tournaments, Johnson Graphs, and NC-Teaching :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-1606-5
%D 2023
%B The 34th International Conference on Algorithmic Learning Theory
%Z date of event: 2023-02-20 - 2023-02-23
%C Singapore, Singapore
%B Proceedings of the 34th International Conference on Algorithmic Learning Theory
%E Agrawal, Shipra; Orabona, Francesco
%P 1411 - 1428
%I PMLR
%B Proceedings of the Machine Learning Research
%N 201
[40]
A. Zandieh, I. Han, M. Daliri, and A. Karbasi, “KDEformer: Accelerating Transformers via Kernel Density Estimation,” 2023. [Online]. Available: https://arxiv.org/abs/2302.02451. (arXiv: 2302.02451)
Abstract
Dot-product attention mechanism plays a crucial role in modern deep<br>architectures (e.g., Transformer) for sequence modeling, however, na\"ive exact<br>computation of this model incurs quadratic time and memory complexities in<br>sequence length, hindering the training of long-sequence models. Critical<br>bottlenecks are due to the computation of partition functions in the<br>denominator of softmax function as well as the multiplication of the softmax<br>matrix with the matrix of values. Our key observation is that the former can be<br>reduced to a variant of the kernel density estimation (KDE) problem, and an<br>efficient KDE solver can be further utilized to accelerate the latter via<br>subsampling-based fast matrix products. Our proposed KDEformer can approximate<br>the attention in sub-quadratic time with provable spectral norm bounds, while<br>all prior results merely provide entry-wise error bounds. Empirically, we<br>verify that KDEformer outperforms other attention approximations in terms of<br>accuracy, memory, and runtime on various pre-trained models. On BigGAN image<br>generation, we achieve better generative scores than the exact computation with<br>over $4\times$ speedup. For ImageNet classification with T2T-ViT, KDEformer<br>shows over $18\times$ speedup while the accuracy drop is less than $0.5\%$.<br>
Export
BibTeX
@online{zandieh2302.02451,
TITLE = {{KDEformer}: Accelerating Transformers via Kernel Density Estimation},
AUTHOR = {Zandieh, Amir and Han, Insu and Daliri, Majid and Karbasi, Amin},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2302.02451},
EPRINT = {2302.02451},
EPRINTTYPE = {arXiv},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
ABSTRACT = {Dot-product attention mechanism plays a crucial role in modern deep<br>architectures (e.g., Transformer) for sequence modeling, however, na\"ive exact<br>computation of this model incurs quadratic time and memory complexities in<br>sequence length, hindering the training of long-sequence models. Critical<br>bottlenecks are due to the computation of partition functions in the<br>denominator of softmax function as well as the multiplication of the softmax<br>matrix with the matrix of values. Our key observation is that the former can be<br>reduced to a variant of the kernel density estimation (KDE) problem, and an<br>efficient KDE solver can be further utilized to accelerate the latter via<br>subsampling-based fast matrix products. Our proposed KDEformer can approximate<br>the attention in sub-quadratic time with provable spectral norm bounds, while<br>all prior results merely provide entry-wise error bounds. Empirically, we<br>verify that KDEformer outperforms other attention approximations in terms of<br>accuracy, memory, and runtime on various pre-trained models. On BigGAN image<br>generation, we achieve better generative scores than the exact computation with<br>over $4\times$ speedup. For ImageNet classification with T2T-ViT, KDEformer<br>shows over $18\times$ speedup while the accuracy drop is less than $0.5\%$.<br>},
}
Endnote
%0 Report
%A Zandieh, Amir
%A Han, Insu
%A Daliri, Majid
%A Karbasi, Amin
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
External Organizations
%T KDEformer: Accelerating Transformers via Kernel Density Estimation :
%G eng
%U http://hdl.handle.net/21.11116/0000-000C-90F7-A
%U https://arxiv.org/abs/2302.02451
%D 2023
%X Dot-product attention mechanism plays a crucial role in modern deep<br>architectures (e.g., Transformer) for sequence modeling, however, na\"ive exact<br>computation of this model incurs quadratic time and memory complexities in<br>sequence length, hindering the training of long-sequence models. Critical<br>bottlenecks are due to the computation of partition functions in the<br>denominator of softmax function as well as the multiplication of the softmax<br>matrix with the matrix of values. Our key observation is that the former can be<br>reduced to a variant of the kernel density estimation (KDE) problem, and an<br>efficient KDE solver can be further utilized to accelerate the latter via<br>subsampling-based fast matrix products. Our proposed KDEformer can approximate<br>the attention in sub-quadratic time with provable spectral norm bounds, while<br>all prior results merely provide entry-wise error bounds. Empirically, we<br>verify that KDEformer outperforms other attention approximations in terms of<br>accuracy, memory, and runtime on various pre-trained models. On BigGAN image<br>generation, we achieve better generative scores than the exact computation with<br>over $4\times$ speedup. For ImageNet classification with T2T-ViT, KDEformer<br>shows over $18\times$ speedup while the accuracy drop is less than $0.5\%$.<br>
%K Computer Science, Learning, cs.LG,Computer Science, Computer Vision and Pattern Recognition, cs.CV,Computer Science, Data Structures and Algorithms, cs.DS