Publications - Current Year

Conference paper

A. Abboud, K. Bringmann, N. Fischer, and M. Künnemann

“The Time Complexity of Fully Sparse Matrix Multiplication,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Alexandria, VA, USA, 2024.

@inproceedings{Abboud_SODA24,
TITLE = {The Time Complexity of Fully Sparse Matrix Multiplication},
AUTHOR = {Abboud, Amir and Bringmann, Karl and Fischer, Nick and K{\"u}nnemann, Marvin},
LANGUAGE = {eng},
ISBN = {978-1-61197-791-2},
DOI = {10.1137/1.9781611977912.167},
PUBLISHER = {SIAM},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)},
EDITOR = {Woodruff, David P.},
PAGES = {4670--4703},
ADDRESS = {Alexandria, VA, USA},
}

Endnote

%0 Conference Proceedings
%A Abboud, Amir
%A Bringmann, Karl
%A Fischer, Nick
%A K&#252;nnemann, Marvin
%+ 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 The Time Complexity of Fully Sparse Matrix Multiplication : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-2E5D-4
%R 10.1137/1.9781611977912.167
%D 2024
%B Annual ACM-SIAM Symposium on Discrete Algorithms
%Z date of event: 2024-01-07 - 2024-01-10
%C Alexandria, VA, USA
%B Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms
%E Woodruff, David P.
%P 4670 - 4703
%I SIAM
%@ 978-1-61197-791-2
%U https://epubs.siam.org/doi/10.1137/1.9781611977912.167

Conference paper

A. Agrawal, P. T. Lima, D. Lokshtanov, S. Saurabh, and R. Sharma

“Odd Cycle Transversal on P5-free Graphs in Quasi-polynomial Time,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Alexandria, VA, USA, 2024.

@inproceedings{Agrawal_SODA24,
TITLE = {Odd Cycle Transversal on P5-free Graphs in Quasi-polynomial Time},
AUTHOR = {Agrawal, Akanksha and Lima, Paloma T. and Lokshtanov, Daniel and Saurabh, Saket and Sharma, Roohani},
LANGUAGE = {eng},
ISBN = {978-1-61197-791-2},
DOI = {10.1137/1.9781611977912.189},
PUBLISHER = {SIAM},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)},
EDITOR = {Woodruff, David P.},
PAGES = {5276--5290},
ADDRESS = {Alexandria, VA, USA},
}

Endnote

%0 Conference Proceedings
%A Agrawal, Akanksha
%A Lima, Paloma T.
%A Lokshtanov, Daniel
%A Saurabh, Saket
%A Sharma, Roohani
%+ External Organizations
External Organizations
External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Odd Cycle Transversal on P5-free Graphs in Quasi-polynomial Time : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-2ED4-C
%R 10.1137/1.9781611977912.189
%D 2024
%B Annual ACM-SIAM Symposium on Discrete Algorithms
%Z date of event: 2024-01-07 - 2024-01-10
%C Alexandria, VA, USA
%B Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms
%E Woodruff, David P.
%P 5276 - 5290
%I SIAM
%@ 978-1-61197-791-2

Article

H. Akrami, N. Alon, B. Ray Chaudhury, J. Garg, K. Mehlhorn, and R. Mehta

“EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number,” Operations Research, 2024.

@article{Akrami_24,
TITLE = {{EFX}: {A} Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number},
AUTHOR = {Akrami, Hannaneh and Alon, Noga and Ray Chaudhury, Bhaskar and Garg, Jugal and Mehlhorn, Kurt and Mehta, Ruta},
LANGUAGE = {eng},
ISSN = {0030-364X},
DOI = {10.1110.1287/opre.2023.0433},
PUBLISHER = {informs},
ADDRESS = {Catonsville, MD},
YEAR = {2024},
JOURNAL = {Operations Research},
}

Endnote

%0 Journal Article
%A Akrami, Hannaneh
%A Alon, Noga
%A Ray Chaudhury, Bhaskar
%A Garg, Jugal
%A Mehlhorn, Kurt
%A Mehta, Ruta
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-2CEB-5
%R 10.1110.1287/opre.2023.0433
%7 2024-10-21
%D 2024
%8 21.10.2024
%J Operations Research
%I informs
%C Catonsville, MD
%@ false

Conference paper

H. Akrami and J. Garg

“Breaking the 3/4 Barrier for Approximate Maximin Share,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Alexandria, VA, USA, 2024.

@inproceedings{Akrami_SODA24,
TITLE = {Breaking the 3/4 Barrier for Approximate Maximin Share},
AUTHOR = {Akrami, Hannaneh and Garg, Jugal},
LANGUAGE = {eng},
ISBN = {978-1-61197-791-2},
DOI = {10.1137/1.9781611977912},
PUBLISHER = {SIAM},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)},
EDITOR = {Woodruff, David P.},
PAGES = {74--91},
ADDRESS = {Alexandria, VA, USA},
}

Endnote

%0 Conference Proceedings
%A Akrami, Hannaneh
%A Garg, Jugal
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T Breaking the 3/4 Barrier for Approximate Maximin Share : 
%G eng
%U http://hdl.handle.net/21.11116/0000-000F-1439-B
%R 10.1137/1.9781611977912
%D 2024
%B Annual ACM-SIAM Symposium on Discrete Algorithms
%Z date of event: 2024-01-07 - 2024-01-10
%C Alexandria, VA, USA
%B Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms
%E Woodruff, David P.
%P 74 - 91
%I SIAM
%@ 978-1-61197-791-2
%U https://epubs.siam.org/doi/10.1137/1.9781611977912.4

Article

H. Bannai, I. Tomohiro, T. Kociumaka, D. Koeppl, and S. J. Puglisi

“Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences,” Algorithmica, vol. 86, 2024.

@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 = {2024},
DATE = {2024},
JOURNAL = {Algorithmica},
VOLUME = {86},
PAGES = {735--756},
}

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-05-06
%D 2024
%J Algorithmica
%V 86
%& 735
%P 735 - 756
%I Springer
%C New York, NY
%@ false

Conference paper

K. Bringmann, A. Grønlund, M. Künnemann, and K. Green Larsen

“The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds,” in 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), Berkeley, CA, USA, 2024.

@inproceedings{Bringmann_ITCS24,
TITLE = {The {NFA} Acceptance Hypothesis: {N}on-Combinatorial and Dynamic Lower Bounds},
AUTHOR = {Bringmann, Karl and Gr{\o}nlund, Allan and K{\"u}nnemann, Marvin and Green Larsen, Kasper},
LANGUAGE = {eng},
ISBN = {978-3-95977-309-6},
URL = {urn:nbn:de:0030-drops-195500},
DOI = {10.4230/LIPIcs.ITCS.2024.22},
PUBLISHER = {Schloss Dagstuhl},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
EDITOR = {Guruswami, Venkatesan},
PAGES = {1--25},
EID = {22},
SERIES = {Leibniz International Proceedings in Informatics},
VOLUME = {287},
ADDRESS = {Berkeley, CA, USA},
}

Endnote

%0 Conference Proceedings
%A Bringmann, Karl
%A Gr&#248;nlund, Allan
%A K&#252;nnemann, Marvin
%A Green Larsen, Kasper
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
External Organizations
%T The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-2D00-C
%R 10.4230/LIPIcs.ITCS.2024.22
%U urn:nbn:de:0030-drops-195500
%D 2024
%B 15th Innovations in Theoretical Computer Science Conference
%Z date of event: 2024-01-30 - 2024-02-02
%C Berkeley, CA, USA
%B 15th Innovations in Theoretical Computer Science Conference
%E Guruswami, Venkatesan
%P 1 - 25
%Z sequence number: 22
%I Schloss Dagstuhl
%@ 978-3-95977-309-6
%B Leibniz International Proceedings in Informatics
%N 287

Conference paper

K. Bringmann, N. Fischer, I. van der Hoog, E. Kipouridis, T. Kociumaka, and E. Rotenberg

“Dynamic Dynamic Time Warping,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Alexandria, VA, USA, 2024.

@inproceedings{BringmannSODA24,
TITLE = {Dynamic Dynamic Time Warping},
AUTHOR = {Bringmann, Karl and Fischer, Nick and van der Hoog, Ivor and Kipouridis, Evangelos and Kociumaka, Tomasz and Rotenberg, Eva},
LANGUAGE = {eng},
ISBN = {978-1-61197-791-2},
DOI = {10.1137/1.9781611977912.10},
PUBLISHER = {SIAM},
YEAR = {2024},
BOOKTITLE = {Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)},
EDITOR = {Woodruff, David P.},
PAGES = {208--242},
ADDRESS = {Alexandria, VA, USA},
}

Endnote

%0 Conference Proceedings
%A Bringmann, Karl
%A Fischer, Nick
%A van der Hoog, Ivor
%A Kipouridis, Evangelos
%A Kociumaka, Tomasz
%A Rotenberg, Eva
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
%T Dynamic Dynamic Time Warping : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-031B-D
%R 10.1137/1.9781611977912.10
%D 2024
%8 04.01.2024
%B Annual ACM-SIAM Symposium on Discrete Algorithms
%Z date of event: 2024-01-07 - 2024-01-10
%C Alexandria, VA, USA
%B Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms
%E Woodruff, David P.
%P 208 - 242
%I SIAM
%@ 978-1-61197-791-2

Conference paper

K. Bringmann, F. Staals, K. Węgrzycki, and G. van Wordragen

“Fine-Grained Complexity of Earth Mover’s Distance Under Translation,” in 40th International Symposium on Computational Geometry (SoCG 2024), Athens, Greece, 2024.

@inproceedings{Bringmann_SoCG2024,
TITLE = {Fine-Grained Complexity of Earth Mover{\textquoteright}s Distance Under Translation},
AUTHOR = {Bringmann, Karl and Staals, Frank and W{\c e}grzycki, Karol and van Wordragen, Geert},
LANGUAGE = {eng},
ISSN = {1868-8969},
ISBN = {978-3-95977-316-4},
URL = {urn:nbn:de:0030-drops-199706},
DOI = {10.4230/LIPIcs.SoCG.2024.25},
PUBLISHER = {Schloss Dagstuhl},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {40th International Symposium on Computational Geometry (SoCG 2024)},
EDITOR = {Mulzer, Wolfgang and Phillips, Jeff M.},
PAGES = {1--17},
EID = {25},
SERIES = {Leibniz International Proceedings in Informatics},
VOLUME = {293},
ADDRESS = {Athens, Greece},
}

Endnote

%0 Conference Proceedings
%A Bringmann, Karl
%A Staals, Frank
%A W&#281;grzycki, Karol
%A van Wordragen, Geert
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T Fine-Grained Complexity of Earth Mover&#8217;s Distance Under Translation : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-0E5C-9
%R 10.4230/LIPIcs.SoCG.2024.25
%U urn:nbn:de:0030-drops-199706
%D 2024
%B 40th International Symposium on Computational Geometry
%Z date of event: 2024-06-11 - 2024-06-14
%C Athens, Greece
%B 40th International Symposium on Computational Geometry
%E Mulzer, Wolfgang; Phillips , Jeff M.
%P 1 - 17
%Z sequence number: 25
%I Schloss Dagstuhl
%@ 978-3-95977-316-4
%B Leibniz International Proceedings in Informatics
%N 293
%@ false

Conference paper

K. Bringmann, A. Dürr, and A. Polak

“Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing,” in 32nd Annual European Symposium on Algorithms (ESA 2024), London, UK, 2024.

@inproceedings{Bringmann_ESA24x,
TITLE = {Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing},
AUTHOR = {Bringmann, Karl and D{\"u}rr, Anita and Polak, Adam},
LANGUAGE = {eng},
ISSN = {1868-8969},
ISBN = {978-3-95977-338-6},
URL = {urn:nbn:de:0030-drops-211047},
DOI = {10.4230/LIPIcs.ESA.2024.33},
PUBLISHER = {Schloss Dagstuhl},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {32nd Annual European Symposium on Algorithms (ESA 2024)},
EDITOR = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
PAGES = {1--15},
EID = {33},
SERIES = {Leibniz International Proceedings in Informatics},
VOLUME = {308},
ADDRESS = {London, UK},
}

Endnote

%0 Conference Proceedings
%A Bringmann, Karl
%A D&#252;rr, Anita
%A Polak, Adam
%+ 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 Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-0E6E-5
%R 10.4230/LIPIcs.ESA.2024.33
%U urn:nbn:de:0030-drops-211047
%D 2024
%B 32nd Annual European Symposium on Algorithms
%Z date of event: 2024-09-02 - 2024-09-04
%C London, UK
%B 32nd Annual European Symposium on Algorithms
%E Chan, Timothy; Fischer, Johannes; Iacono, John; Herman, Grzegorz
%P 1 - 15
%Z sequence number: 33
%I Schloss Dagstuhl
%@ 978-3-95977-338-6
%B Leibniz International Proceedings in Informatics
%N 308
%@ false

Conference paper

K. Bringmann, A. Cassis, N. Fischer, and T. Kociumaka

“Faster Sublinear-Time Edit Distance,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Alexandria, VA, USA, 2024.

@inproceedings{Bringmann_SODA24,
TITLE = {Faster Sublinear-Time Edit Distance},
AUTHOR = {Bringmann, Karl and Cassis, Alejandro and Fischer, Nick and Kociumaka, Tomasz},
LANGUAGE = {eng},
ISBN = {978-1-61197-791-2},
DOI = {10.1137/1.9781611977912.117},
PUBLISHER = {SIAM},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)},
EDITOR = {Woodruff, David P.},
PAGES = {3274--3301},
ADDRESS = {Alexandria, VA, USA},
}

Endnote

%0 Conference Proceedings
%A Bringmann, Karl
%A Cassis, Alejandro
%A Fischer, Nick
%A Kociumaka, Tomasz
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Faster Sublinear-Time Edit Distance : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-33A4-B
%R 10.1137/1.9781611977912.117
%D 2024
%B Annual ACM-SIAM Symposium on Discrete Algorithms
%Z date of event: 2024-01-07 - 2024-01-10
%C Alexandria, VA, USA
%B Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms
%E Woodruff, David P.
%P 3274 - 3301
%I SIAM
%@ 978-1-61197-791-2
%U https://epubs.siam.org/doi/10.1137/1.9781611977912.117

Conference paper

K. Bringmann

“Approximating Subset Sum Ratio faster than Subset Sum,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Alexandria, VA, USA, 2024.

@inproceedings{Bringmann_SODA24b,
TITLE = {Approximating Subset Sum Ratio faster than Subset Sum},
AUTHOR = {Bringmann, Karl},
LANGUAGE = {eng},
ISBN = {978-1-61197-791-2},
DOI = {10.1137/1.9781611977912.50},
PUBLISHER = {SIAM},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)},
EDITOR = {Woodruff, David P.},
PAGES = {1260--1277},
ADDRESS = {Alexandria, VA, USA},
}

Endnote

%0 Conference Proceedings
%A Bringmann, Karl
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Approximating Subset Sum Ratio faster than Subset Sum : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-34F6-E
%R 10.1137/1.9781611977912.50
%D 2024
%B Annual ACM-SIAM Symposium on Discrete Algorithms
%Z date of event: 2024-01-07 - 2024-01-10
%C Alexandria, VA, USA
%B Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms
%E Woodruff, David P.
%P 1260 - 1277
%I SIAM
%@ 978-1-61197-791-2

Conference paper

K. Bringmann, A. Ghazy, and M. Künnemann

“Exploring the Approximability Landscape of 3SUM,” in 32nd Annual European Symposium on Algorithms (ESA 2024), London, UK, 2024.

@inproceedings{Bringmann_ESA24y,
TITLE = {Exploring the Approximability Landscape of {3SUM}},
AUTHOR = {Bringmann, Karl and Ghazy, Ahmed and K{\"u}nnemann, Marvin},
LANGUAGE = {eng},
ISSN = {1868-8969},
ISBN = {978-3-95977-338-6},
URL = {urn:nbn:de:0030-drops-211057},
DOI = {10.4230/LIPIcs.ESA.2024.34},
PUBLISHER = {Schloss Dagstuhl},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {32nd Annual European Symposium on Algorithms (ESA 2024)},
EDITOR = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
PAGES = {1--15},
EID = {34},
SERIES = {Leibniz International Proceedings in Informatics},
VOLUME = {308},
ADDRESS = {London, UK},
}

Endnote

%0 Conference Proceedings
%A Bringmann, Karl
%A Ghazy, Ahmed
%A K&#252;nnemann, Marvin
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
%T Exploring the Approximability Landscape of 3SUM : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-34EA-C
%R 10.4230/LIPIcs.ESA.2024.34
%U urn:nbn:de:0030-drops-211057
%D 2024
%B 32nd Annual European Symposium on Algorithms
%Z date of event: 2024-09-02 - 2024-09-04
%C London, UK
%B 32nd Annual European Symposium on Algorithms
%E Chan, Timothy; Fischer, Johannes; Iacono, John; Herman, Grzegorz
%P 1 - 15
%Z sequence number: 34
%I Schloss Dagstuhl
%@ 978-3-95977-338-6
%B Leibniz International Proceedings in Informatics
%N 308
%@ false

Conference paper

K. Bringmann

“Knapsack with Small Items in Near-Quadratic Time,” in STOC ’24, 56th Annual ACM Symposium on Theory of Computing, Vancouver, Canada, 2024.

@inproceedings{Bringmann_STOC24,
TITLE = {Knapsack with Small Items in Near-Quadratic Time},
AUTHOR = {Bringmann, Karl},
LANGUAGE = {eng},
ISBN = {979-8-4007-0383-6},
DOI = {10.1145/3618260.3649719},
PUBLISHER = {ACM},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {STOC '24, 56th Annual ACM Symposium on Theory of Computing},
EDITOR = {Moha, Bojan and Shinkar, Igor and O'Donnell, Ryan},
PAGES = {259--270},
ADDRESS = {Vancouver, Canada},
}

Endnote

%0 Conference Proceedings
%A Bringmann, Karl
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Knapsack with Small Items in Near-Quadratic Time : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-34EF-7
%R 10.1145/3618260.3649719
%D 2024
%B 56th Annual ACM Symposium on Theory of Computing
%Z date of event: 2024-06-24 - 2024-06-28
%C Vancouver, Canada
%B STOC '24
%E Moha, Bojan; Shinkar, Igor; O'Donnell, Ryan
%P 259 - 270
%I ACM
%@ 979-8-4007-0383-6

Article

I. Caragiannis and N. Rathi

“Optimizing Over Serial Dictatorships,” Theory of Computing Systems, 2024.

@article{Caragiannis24,
TITLE = {Optimizing Over Serial Dictatorships},
AUTHOR = {Caragiannis, Ioannis and Rathi, Nidhi},
LANGUAGE = {eng},
ISSN = {1432-4350},
DOI = {10.1007/s00224-024-10196-6},
PUBLISHER = {Springer},
ADDRESS = {New York, NY},
YEAR = {2024},
JOURNAL = {Theory of Computing Systems},
}

Endnote

%0 Journal Article
%A Caragiannis, Ioannis
%A Rathi, Nidhi
%+ External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Optimizing Over Serial Dictatorships : 
%G eng
%U http://hdl.handle.net/21.11116/0000-000F-F1BA-F
%R 10.1007/s00224-024-10196-6
%7 2024-10-03
%D 2024
%8 03.10.2024
%J Theory of Computing Systems
%I Springer
%C New York, NY
%@ false

Article

L. S. Chandran, T. Hashim, D. Jacob, R. Mathew, D. Rajendraprasad, and N. Singh

“New bounds on the anti-Ramsey numbers of star graphs via maximum edge q-coloring,” Discrete Mathematics, vol. 347, no. 4, 2024.

@article{Chandran24,
TITLE = {New bounds on the anti-{R}amsey numbers of star graphs via maximum edge q-coloring},
AUTHOR = {Chandran, L. Sunil and Hashim, Talha and Jacob, Dalu and Mathew, Rogers and Rajendraprasad, Deepak and Singh, Nitin},
LANGUAGE = {eng},
ISSN = {0012-365X},
DOI = {10.1016/j.disc.2024.113894},
PUBLISHER = {North-Holland},
ADDRESS = {Amsterdam},
YEAR = {2024},
DATE = {2024},
JOURNAL = {Discrete Mathematics},
VOLUME = {347},
NUMBER = {4},
EID = {113894},
}

Endnote

%0 Journal Article
%A Chandran, L. Sunil
%A Hashim, Talha
%A Jacob, Dalu
%A Mathew, Rogers
%A Rajendraprasad, Deepak
%A Singh, Nitin
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
External Organizations
External Organizations
External Organizations
%T New bounds on the anti-Ramsey numbers of star graphs via maximum edge q-coloring : 
%G eng
%U http://hdl.handle.net/21.11116/0000-000F-1AB5-8
%R 10.1016/j.disc.2024.113894
%7 2024
%D 2024
%J Discrete Mathematics
%V 347
%N 4
%Z sequence number: 113894
%I North-Holland
%C Amsterdam
%@ false

Article

C. Coupette, D. Hartung, and D. M. Katz

“Legal Hypergraphs,” Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 382, no. 2270, 2024.

@article{Coupette2024,
TITLE = {Legal Hypergraphs},
AUTHOR = {Coupette, Corinna and Hartung, Dirk and Katz, Daniel Martin},
LANGUAGE = {eng},
ISSN = {1364-503X},
DOI = {10.1098/rsta.2023.0141},
PUBLISHER = {Royal Society},
ADDRESS = {London},
YEAR = {2024},
DATE = {2024},
JOURNAL = {Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences},
VOLUME = {382},
NUMBER = {2270},
PAGES = {1--19},
EID = {20230141},
}

Endnote

%0 Journal Article
%A Coupette, Corinna
%A Hartung, Dirk
%A Katz, Daniel Martin
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
%T Legal Hypergraphs : 
%G eng
%U http://hdl.handle.net/21.11116/0000-000E-888E-9
%R 10.1098/rsta.2023.0141
%2 PMC10894694
%D 2024
%J Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences
%O Phil. Trans. R. Soc. A
%V 382
%N 2270
%& 1
%P 1 - 19
%Z sequence number: 20230141
%I Royal Society
%C London
%@ false

Conference paper

J. Cslovjecsek, M. Pilipczuk, and K. Węgrzycki

“Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments,” in 32nd Annual European Symposium on Algorithms (ESA 2024), London, UK, 2024.

@inproceedings{Cslovjecsek_ESA24,
TITLE = {Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments},
AUTHOR = {Cslovjecsek, Jana and Pilipczuk, Micha{\l} and W{\c e}grzycki, Karol},
LANGUAGE = {eng},
ISSN = {1868-8969},
ISBN = {978-3-95977-338-6},
URL = {urn:nbn:de:0030-drops-211146},
DOI = {10.4230/LIPIcs.ESA.2024.43},
PUBLISHER = {Schloss Dagstuhl},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {32nd Annual European Symposium on Algorithms (ESA 2024)},
EDITOR = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
PAGES = {1--18},
EID = {43},
SERIES = {Leibniz International Proceedings in Informatics},
VOLUME = {308},
ADDRESS = {London, UK},
}

Endnote

%0 Conference Proceedings
%A Cslovjecsek, Jana
%A Pilipczuk, Micha&#322;
%A W&#281;grzycki, Karol
%+ External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-0E62-1
%R 10.4230/LIPIcs.ESA.2024.43
%U urn:nbn:de:0030-drops-211146
%D 2024
%B 32nd Annual European Symposium on Algorithms
%Z date of event: 2024-09-02 - 2024-09-04
%C London, UK
%B 32nd Annual European Symposium on Algorithms
%E Chan, Timothy; Fischer, Johannes; Iacono, John; Herman, Grzegorz
%P 1 - 18
%Z sequence number: 43
%I Schloss Dagstuhl
%@ 978-3-95977-338-6
%B Leibniz International Proceedings in Informatics
%N 308
%@ false

Conference paper

J. Cslovjecsek, M. Pilipczuk, and K. Węgrzycki

“A Polynomial-time OPT Ɛ-Approximation Algorithm for Maximum Independent Set of Connected Subgraphs in a Planar Graph,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Alexandria, VA, USA, 2024.

@inproceedings{Cslovjecsek_SODA24,
TITLE = {A Polynomial-time $\text{OPT}^\epsilon$-Approximation Algorithm for Maximum Independent Set of Connected Subgraphs in a Planar Graph},
AUTHOR = {Cslovjecsek, Jana and Pilipczuk, Micha{\l} and W{\c e}grzycki, Karol},
LANGUAGE = {eng},
ISBN = {978-1-61197-791-2},
DOI = {10.1137/1.9781611977912.23},
PUBLISHER = {SIAM},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)},
EDITOR = {Woodruff, David P.},
PAGES = {625--638},
ADDRESS = {Alexandria, VA, USA},
}

Endnote

%0 Conference Proceedings
%A Cslovjecsek, Jana
%A Pilipczuk, Micha&#322;
%A W&#281;grzycki, Karol
%+ External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T A Polynomial-time OPT &#400;-Approximation Algorithm for Maximum Independent Set of Connected Subgraphs in a Planar Graph : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-0E74-D
%R 10.1137/1.9781611977912.23
%D 2024
%B Annual ACM-SIAM Symposium on Discrete Algorithms
%Z date of event: 2024-01-07 - 2024-01-10
%C Alexandria, VA, USA
%B Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms
%E Woodruff, David P.
%P 625 - 638
%I SIAM
%@ 978-1-61197-791-2

Conference paper

A. Duyster and T. Kociumaka

“Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts,” in String Processing and Information Retrieval (SPIRES 2024), Puerto Vallarta, Mexico, 2024.

@inproceedings{Duyster_SPIRES24,
TITLE = {Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts},
AUTHOR = {Duyster, Anouk and Kociumaka, Tomasz},
LANGUAGE = {eng},
ISBN = {978-3-031-72199-1},
DOI = {10.1007/978-3-031-72200-4_8},
PUBLISHER = {Springer},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {String Processing and Information Retrieval (SPIRES 2024)},
EDITOR = {Lipt{\'a}k, Zsuzsanna and Moura, Edleno and Figueroa, Karina and Baeza-Yates, Ricardo},
PAGES = {102--117},
SERIES = {Lecture Notes in Computer Science},
VOLUME = {14899},
ADDRESS = {Puerto Vallarta, Mexico},
}

Endnote

%0 Conference Proceedings
%A Duyster, Anouk
%A Kociumaka, Tomasz
%+ External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-0E51-4
%R 10.1007/978-3-031-72200-4_8
%D 2024
%B 31st International Symposium on String Processing and Information Retrieval
%Z date of event: 2024-09-23 - 2024-09-25
%C Puerto Vallarta, Mexico
%B String Processing and Information Retrieval
%E Lipt&#225;k, Zsuzsanna; Moura, Edleno; Figueroa, Karina; Baeza-Yates, Ricardo
%P 102 - 117
%I Springer
%@ 978-3-031-72199-1
%B Lecture Notes in Computer Science
%N 14899
%U https://rdcu.be/dZM2q

Article

B. C. Esmer, A. Kulik, D. Marx, P. Schepper, and K. Węgrzycki

“Computing Generalized Convolutions Faster Than Brute Force,” Algorithmica, vol. 86, 2024.

@article{Esmer_23,
TITLE = {Computing Generalized Convolutions Faster Than Brute Force},
AUTHOR = {Esmer, Bari{\c s} Can and Kulik, Ariel and Marx, D{\'a}niel and Schepper, Philipp and W{\c e}grzycki, Karol},
LANGUAGE = {eng},
ISSN = {0178-4617},
DOI = {10.1007/s00453-023-01176-2},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
YEAR = {2024},
DATE = {2024},
JOURNAL = {Algorithmica},
VOLUME = {86},
PAGES = {334--366},
}

Endnote

%0 Journal Article
%A Esmer, Bari&#351; Can
%A Kulik, Ariel
%A Marx, D&#225;niel
%A Schepper, Philipp
%A W&#281;grzycki, Karol
%+ External Organizations
External Organizations
External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Computing Generalized Convolutions Faster Than Brute Force : 
%G eng
%U http://hdl.handle.net/21.11116/0000-000E-36C4-8
%R 10.1007/s00453-023-01176-2
%7 2023
%D 2024
%J Algorithmica
%V 86
%& 334
%P 334 - 366
%I Springer-Verlag
%C New York
%@ false

Conference paper

N. Fischer, P. Kaliciak, and A. Polak

“Deterministic 3SUM-Hardness,” in 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), Berkeley, CA, USA, 2024.

@inproceedings{Fischer_ITCS24,
TITLE = {Deterministic {3SUM}-Hardness},
AUTHOR = {Fischer, Nick and Kaliciak, Piotr and Polak, Adam},
LANGUAGE = {eng},
ISBN = {978-3-95977-309-6},
URL = {urn:nbn:de:0030-drops-195772},
DOI = {10.4230/LIPIcs.ITCS.2024.49},
PUBLISHER = {Schloss Dagstuhl},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
EDITOR = {Guruswami, Venkatesan},
PAGES = {1--24},
EID = {49},
SERIES = {Leibniz International Proceedings in Informatics},
VOLUME = {287},
ADDRESS = {Berkeley, CA, USA},
}

Endnote

%0 Conference Proceedings
%A Fischer, Nick
%A Kaliciak, Piotr
%A Polak, Adam
%+ External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Deterministic 3SUM-Hardness : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-2D9A-F
%R 10.4230/LIPIcs.ITCS.2024.49
%U urn:nbn:de:0030-drops-195772
%D 2024
%B 15th Innovations in Theoretical Computer Science Conference
%Z date of event: 2024-01-30 - 2024-02-02
%C Berkeley, CA, USA
%B 15th Innovations in Theoretical Computer Science Conference
%E Guruswami, Venkatesan
%P 1 - 24
%Z sequence number: 49
%I Schloss Dagstuhl
%@ 978-3-95977-309-6
%B Leibniz International Proceedings in Informatics
%N 287

Conference paper

J. Focke, F. Frei, S. Li, D. Marx, P. Schepper, R. Sharma, and K. Węgrzycki

“Hitting Meets Packing: How Hard Can It Be?,” in 32nd Annual European Symposium on Algorithms (ESA 2024), London, UK, 2024.

@inproceedings{Focke_ESA24,
TITLE = {Hitting Meets Packing: {H}ow Hard Can It Be?},
AUTHOR = {Focke, Jacob and Frei, Fabian and Li, Shaohua and Marx, D{\'a}niel and Schepper, Philipp and Sharma, Roohani and W{\c e}grzycki, Karol},
LANGUAGE = {eng},
ISSN = {1868-8969},
ISBN = {978-3-95977-338-6},
URL = {urn:nbn:de:0030-drops-211261},
DOI = {10.4230/LIPIcs.ESA.2024.55},
PUBLISHER = {Schloss Dagstuhl},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {32nd Annual European Symposium on Algorithms (ESA 2024)},
EDITOR = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
PAGES = {1--21},
EID = {55},
SERIES = {Leibniz International Proceedings in Informatics},
VOLUME = {308},
ADDRESS = {London, UK},
}

Endnote

%0 Conference Proceedings
%A Focke, Jacob
%A Frei, Fabian
%A Li, Shaohua
%A Marx, D&#225;niel
%A Schepper, Philipp
%A Sharma, Roohani
%A W&#281;grzycki, Karol
%+ External Organizations
External Organizations
External Organizations
External Organizations
External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Hitting Meets Packing: How Hard Can It Be? : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-0E65-E
%R 10.4230/LIPIcs.ESA.2024.55
%U urn:nbn:de:0030-drops-211261
%D 2024
%B 32nd Annual European Symposium on Algorithms
%Z date of event: 2024-09-02 - 2024-09-04
%C London, UK
%B 32nd Annual European Symposium on Algorithms
%E Chan, Timothy; Fischer, Johannes; Iacono, John; Herman, Grzegorz
%P 1 - 21
%Z sequence number: 55
%I Schloss Dagstuhl
%@ 978-3-95977-338-6
%B Leibniz International Proceedings in Informatics
%N 308
%@ false

Article

F. Folz, K. Mehlhorn, and G. Morigi

“Self-organized Transport in Noisy Dynamic Networks,” Physical Review E, vol. 110, no. 4, 2024.

@article{Folz24,
TITLE = {Self-organized Transport in Noisy Dynamic Networks},
AUTHOR = {Folz, Frederic and Mehlhorn, Kurt and Morigi, Giovanna},
LANGUAGE = {eng},
ISSN = {1539-3755},
DOI = {10.1103/PhysRevE.110.044310},
PUBLISHER = {American Physical Society},
ADDRESS = {Melville, NY},
YEAR = {2024},
DATE = {2024},
JOURNAL = {Physical Review E},
VOLUME = {110},
NUMBER = {4},
EID = {044310},
}

Endnote

%0 Journal Article
%A Folz, Frederic
%A Mehlhorn, Kurt
%A Morigi, Giovanna
%+ External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T Self-organized Transport in Noisy Dynamic Networks : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-2CF2-C
%R 10.1103/PhysRevE.110.044310
%7 2024-10-21
%D 2024
%J Physical Review E
%O Phys. Rev. E
%V 110
%N 4
%Z sequence number: 044310
%I American Physical Society
%C Melville, NY
%@ false

Article

D. Fried, S. Golan, T. Kociumaka, T. Kopelowitz, E. Porat, and T. Starikovskaya

“An Improved Algorithm for The k-Dyck Edit Distance Problem,” ACM Transactions on Algorithms, vol. 20, no. 3, 2024.

@article{Fried24,
TITLE = {An Improved Algorithm for The $k$-{D}yck Edit Distance Problem},
AUTHOR = {Fried, Dvir and Golan, Shay and Kociumaka, Tomasz and Kopelowitz, Tsvi and Porat, Ely and Starikovskaya, Tatiana},
LANGUAGE = {eng},
ISSN = {1549-6325},
DOI = {10.1145/3627539},
PUBLISHER = {ACM},
ADDRESS = {New York, NY},
YEAR = {2024},
DATE = {2024},
JOURNAL = {ACM Transactions on Algorithms},
VOLUME = {20},
NUMBER = {3},
PAGES = {1--25},
EID = {26},
}

Endnote

%0 Journal Article
%A Fried, Dvir
%A Golan, Shay
%A Kociumaka, Tomasz
%A Kopelowitz, Tsvi
%A Porat, Ely
%A Starikovskaya, Tatiana
%+ External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
External Organizations
%T An Improved Algorithm for The k-Dyck Edit Distance Problem : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-2E2D-A
%R 10.1145/3627539
%7 2024-06-21
%D 2024
%J ACM Transactions on Algorithms
%V 20
%N 3
%& 1
%P 1 - 25
%Z sequence number: 26
%I ACM
%C New York, NY
%@ false

Conference paper

D. Gibney, C. Jin, T. Kociumaka, and S. V. Thankachan

“Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Alexandria, VA, USA, 2024.

@inproceedings{Gibney_SODA24,
TITLE = {Near-Optimal Quantum Algorithms for Bounded Edit Distance and {L}empel-{Z}iv Factorization},
AUTHOR = {Gibney, Daniel and Jin, Ce and Kociumaka, Tomasz and Thankachan, Sharma V.},
LANGUAGE = {eng},
ISBN = {978-1-61197-791-2},
DOI = {10.1137/1.9781611977912.118},
PUBLISHER = {SIAM},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)},
EDITOR = {Woodruff, David P.},
PAGES = {3302--3332},
ADDRESS = {Alexandria, VA, USA},
}

Endnote

%0 Conference Proceedings
%A Gibney, Daniel
%A Jin, Ce
%A Kociumaka, Tomasz
%A Thankachan, Sharma V.
%+ External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-33E3-4
%R 10.1137/1.9781611977912.118
%D 2024
%B Annual ACM-SIAM Symposium on Discrete Algorithms
%Z date of event: 2024-01-07 - 2024-01-10
%C Alexandria, VA, USA
%B Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms
%E Woodruff, David P.
%P 3302 - 3332
%I SIAM
%@ 978-1-61197-791-2
%U https://epubs.siam.org/doi/10.1137/1.9781611977912.118

Article

E. J. Kim, T. Masařík, M. Pilipczuk, R. Sharma, and M. Wahlström

“On Weighted Graph Separation Problems and Flow-Augmentation,” SIAM Journal on Discrete Mathematics, 2024.

@article{Kim24,
TITLE = {On Weighted Graph Separation Problems and Flow-Augmentation},
AUTHOR = {Kim, Eun Jung and Masa{\v r}{\'i}k, Tom{\'a}{\v s} and Pilipczuk, Marcin and Sharma, Roohani and Wahlstr{\"o}m, Magnus},
LANGUAGE = {eng},
ISSN = {0895-4801},
DOI = {10.1137/22M153118X},
PUBLISHER = {SIAM},
ADDRESS = {Philadelphia, Pa.},
YEAR = {2024},
DATE = {2024},
JOURNAL = {SIAM Journal on Discrete Mathematics},
PAGES = {170--189},
}

Endnote

%0 Journal Article
%A Kim, Eun Jung
%A Masa&#345;&#237;k, Tom&#225;&#353;
%A Pilipczuk, Marcin
%A Sharma, Roohani
%A Wahlstr&#246;m, Magnus
%+ External Organizations
External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T On Weighted Graph Separation Problems and Flow-Augmentation : 
%G eng
%U http://hdl.handle.net/21.11116/0000-000F-7599-1
%R 10.1137/22M153118X
%7 2024
%D 2024
%J SIAM Journal on Discrete Mathematics
%& 170
%P 170 - 189
%I SIAM
%C Philadelphia, Pa.
%@ false

Conference paper

S. Kisfaludi-Bak, J. Masaříková, E. J. van Leeuwen, B. Walczak, and K. Węgrzycki

“Separator Theorem and Algorithms for Planar Hyperbolic Graphs,” in 40th International Symposium on Computational Geometry (SoCG 2024), Athens, Greece, 2024.

@inproceedings{Kisfaludi-Bak_SoCG2024,
TITLE = {Separator Theorem and Algorithms for Planar Hyperbolic Graphs},
AUTHOR = {Kisfaludi-Bak, S{\'a}ndor and Masa{\v r}{\'i}kov{\'a}, Jana and van Leeuwen, Erik Jan and Walczak, Bartosz and W{\c e}grzycki, Karol},
LANGUAGE = {eng},
ISSN = {1868-8969},
ISBN = {978-3-95977-316-4},
URL = {urn:nbn:de:0030-drops-200126},
DOI = {10.4230/LIPIcs.SoCG.2024.67},
PUBLISHER = {Schloss Dagstuhl},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {40th International Symposium on Computational Geometry (SoCG 2024)},
EDITOR = {Mulzer, Wolfgang and Phillips, Jeff M.},
PAGES = {1--17},
EID = {67},
SERIES = {Leibniz International Proceedings in Informatics},
VOLUME = {293},
ADDRESS = {Athens, Greece},
}

Endnote

%0 Conference Proceedings
%A Kisfaludi-Bak, S&#225;ndor
%A Masa&#345;&#237;kov&#225;, Jana
%A van Leeuwen, Erik Jan
%A Walczak, Bartosz
%A W&#281;grzycki, Karol
%+ External Organizations
External Organizations
External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Separator Theorem and Algorithms for Planar Hyperbolic Graphs : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-0E5F-6
%R 10.4230/LIPIcs.SoCG.2024.67
%U urn:nbn:de:0030-drops-200126
%D 2024
%B 40th International Symposium on Computational Geometry
%Z date of event: 2024-06-11 - 2024-06-14
%C Athens, Greece
%B 40th International Symposium on Computational Geometry
%E Mulzer, Wolfgang; Phillips , Jeff M.
%P 1 - 17
%Z sequence number: 67
%I Schloss Dagstuhl
%@ 978-3-95977-316-4
%B Leibniz International Proceedings in Informatics
%N 293
%@ false

Article

T. Kociumaka, J. Radoszewski, W. Rytter, and T. Waleń

“Internal Pattern Matching Queries in a Text and Applications,” SIAM Journal on Computing, vol. 53, no. 5, 2024.

@article{Kociumaka_2024c,
TITLE = {Internal Pattern Matching Queries in a Text and Applications},
AUTHOR = {Kociumaka, Tomasz and Radoszewski, Jakub and Rytter, Wojciech and Wale{\'n}, Tomasz},
LANGUAGE = {eng},
ISSN = {0097-5397},
DOI = {10.1137/23M156761},
PUBLISHER = {SIAM},
ADDRESS = {Philadelphia, PA},
YEAR = {2024},
DATE = {2024},
JOURNAL = {SIAM Journal on Computing},
VOLUME = {53},
NUMBER = {5},
PAGES = {1524--1577},
}

Endnote

%0 Journal Article
%A Kociumaka, Tomasz
%A Radoszewski, Jakub
%A Rytter, Wojciech
%A Wale&#324;, Tomasz
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
External Organizations
%T Internal Pattern Matching Queries in a Text and Applications : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-3350-A
%R 10.1137/23M156761
%7 2024
%D 2024
%J SIAM Journal on Computing
%V 53
%N 5
%& 1524
%P 1524 - 1577
%I SIAM
%C Philadelphia, PA
%@ false

Article

T. Kociumaka, G. Navarro, and F. Olivares

“Near-Optimal Search Time in δ-Optimal Space,” Algorithmica, vol. 86, 2024.

@article{Kociumaka_Algorithmica23,
TITLE = {Near-optimal search time in $\delta$-optimal space},
AUTHOR = {Kociumaka, Tomasz and Navarro, Gonzalo and Olivares, Francisco},
LANGUAGE = {eng},
ISSN = {0178-4617},
DOI = {10.1007/s00453-023-01186-0},
PUBLISHER = {Springer},
ADDRESS = {New York, NY},
YEAR = {2024},
DATE = {2024},
JOURNAL = {Algorithmica},
VOLUME = {86},
PAGES = {1031--1056},
}

Endnote

%0 Journal Article
%A Kociumaka, Tomasz
%A Navarro, Gonzalo
%A Olivares, Francisco
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
%T Near-Optimal Search Time in &#948;-Optimal Space : 
%G eng
%U http://hdl.handle.net/21.11116/0000-000E-0D73-3
%R 10.1007/s00453-023-01186-0
%7 2023-11-06
%D 2024
%J Algorithmica
%V 86
%& 1031
%P 1031 - 1056
%I Springer
%C New York, NY
%@ false
%U https://rdcu.be/d0Kn4

Conference paper

T. Kociumaka, J. Nogler, and P. Wellnitz

“On the Communication Complexity of Approximate Pattern Matching,” in STOC ’24, 56th Annual ACM Symposium on Theory of Computing, Vancouver, Canada, 2024.

@inproceedings{Kociumaka_STOC24,
TITLE = {On the Communication Complexity of Approximate Pattern Matching},
AUTHOR = {Kociumaka, Tomasz and Nogler, Jakob and Wellnitz, Philip},
LANGUAGE = {eng},
ISBN = {979-8-4007-0383-6},
DOI = {10.1145/3618260.3649604},
PUBLISHER = {ACM},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {STOC '24, 56th Annual ACM Symposium on Theory of Computing},
EDITOR = {Moha, Bojan and Shinkar, Igor and O'Donnell, Ryan},
PAGES = {1758--1768},
ADDRESS = {Vancouver, Canada},
}

Endnote

%0 Conference Proceedings
%A Kociumaka, Tomasz
%A Nogler, Jakob
%A Wellnitz, Philip
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T On the Communication Complexity of Approximate Pattern Matching : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-33F0-5
%R 10.1145/3618260.3649604
%D 2024
%B 56th Annual ACM Symposium on Theory of Computing
%Z date of event: 2024-06-24 - 2024-06-28
%C Vancouver, Canada
%B STOC '24
%E Moha, Bojan; Shinkar, Igor; O'Donnell, Ryan
%P 1758 - 1768
%I ACM
%@ 979-8-4007-0383-6

Conference paper

L. Kowalik, A. Lassota, K. Majewski, M. Pilipczuk, and M. Sokołowski

“Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard,” in Symposium on Simplicity in Algorithms (SOSA 2024), Alexandria, VA, USA, 2024.

@inproceedings{Kowalik_SOSA24,
TITLE = {Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard},
AUTHOR = {Kowalik, Lukasz and Lassota, Alexandra and Majewski, Konrad and Pilipczuk, Micha{\l} and Soko{\l}owski, Marek},
LANGUAGE = {eng},
ISBN = {978-1-61197-793-6},
DOI = {10.1137/1.9781611977936.25},
PUBLISHER = {SIAM},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {Symposium on Simplicity in Algorithms (SOSA 2024)},
EDITOR = {Parter, Merav and Pettie, Seth},
PAGES = {279--285},
ADDRESS = {Alexandria, VA, USA},
}

Endnote

%0 Conference Proceedings
%A Kowalik, Lukasz
%A Lassota, Alexandra
%A Majewski, Konrad
%A Pilipczuk, Micha&#322;
%A Soko&#322;owski, Marek
%+ External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
External Organizations
%T Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-2E3A-B
%R 10.1137/1.9781611977936.25
%D 2024
%B Seventh SIAM Symposium on Simplicity in Algorithms
%Z date of event: 2024-01-08 - 2024-01-10
%C Alexandria, VA, USA
%B Symposium on Simplicity in Algorithms
%E Parter, Merav; Pettie, Seth
%P 279 - 285
%I SIAM
%@ 978-1-61197-793-6

Conference paper

A. Merino

Namrata, and A. Williams, “On the Hardness of Gray Code Problems for Combinatorial Objects,” in WALCOM: Algorithms and Computation, Kanazawa, Japan, 2024.

@inproceedings{Merino_WALCOM24,
TITLE = {On the Hardness of Gray Code Problems for Combinatorial Objects},
AUTHOR = {Merino, Arturo and Namrata and Williams, Aaron},
LANGUAGE = {eng},
ISBN = {978-981-97-0565-8},
DOI = {10.1007/978-981-97-0566-5_9},
PUBLISHER = {Springer},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {WALCOM: Algorithms and Computation},
EDITOR = {Uehara, Ryuhei and Yamanaka, Katsuhisa and Yen, Hsu-Chun},
PAGES = {328--339},
SERIES = {Lecture Notes in Computer Science},
VOLUME = {14549},
ADDRESS = {Kanazawa, Japan},
}

Endnote

%0 Conference Proceedings
%A Merino, Arturo
%A Namrata, 
%A Williams, Aaron
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
%T On the Hardness of Gray Code Problems for Combinatorial Objects : 
%G eng
%U http://hdl.handle.net/21.11116/0000-000F-4EEB-2
%R 10.1007/978-981-97-0566-5_9
%D 2024
%B 18th International Conference and Workshops on Algorithms and
Computation
%Z date of event: 2024-03-18 - 2024-03-20
%C Kanazawa, Japan
%B WALCOM: Algorithms and Computation
%E Uehara, Ryuhei; Yamanaka, Katsuhisa; Yen, Hsu-Chun
%P 328 - 339
%I Springer
%@ 978-981-97-0565-8
%B Lecture Notes in Computer Science
%N 14549
%U https://rdcu.be/dIy4F

Article

A. Merino and A. Wiese

“On the Two-Dimensional Knapsack Problem for Convex Polygons,” ACM Transactions on Algorithms, vol. 20, no. 2, 2024.

@article{Merino24,
TITLE = {On the Two-Dimensional Knapsack Problem for Convex Polygons},
AUTHOR = {Merino, Arturo and Wiese, Andreas},
LANGUAGE = {eng},
ISSN = {1549-6325},
DOI = {10.1145/3644390},
PUBLISHER = {ACM},
ADDRESS = {New York, NY},
YEAR = {2024},
DATE = {2024},
JOURNAL = {ACM Transactions on Algorithms},
VOLUME = {20},
NUMBER = {2},
PAGES = {1--38},
EID = {16},
}

Endnote

%0 Journal Article
%A Merino, Arturo
%A Wiese, Andreas
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T On the Two-Dimensional Knapsack Problem for Convex Polygons : 
%G eng
%U http://hdl.handle.net/21.11116/0000-000F-5226-A
%R 10.1145/3644390
%7 2024
%D 2024
%J ACM Transactions on Algorithms
%V 20
%N 2
%& 1
%P 1 - 38
%Z sequence number: 16
%I ACM
%C New York, NY
%@ false

Conference paper

T. Randolph and K. Węgrzycki

“Parameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM,” in 32nd Annual European Symposium on Algorithms (ESA 2024), London, UK, 2024.

@inproceedings{Randolph_ESA24,
TITLE = {Parameterized Algorithms on Integer Sets with Small Doubling: {I}nteger Programming, Subset Sum and k-{SUM}},
AUTHOR = {Randolph, Tim and W{\c e}grzycki, Karol},
LANGUAGE = {eng},
ISSN = {1868-8969},
ISBN = {978-3-95977-338-6},
URL = {urn:nbn:de:0030-drops-211672},
DOI = {10.4230/LIPIcs.ESA.2024.96},
PUBLISHER = {Schloss Dagstuhl},
YEAR = {2024},
DATE = {2024},
BOOKTITLE = {32nd Annual European Symposium on Algorithms (ESA 2024)},
EDITOR = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
PAGES = {1--19},
EID = {96},
SERIES = {Leibniz International Proceedings in Informatics},
VOLUME = {308},
ADDRESS = {London, UK},
}

Endnote

%0 Conference Proceedings
%A Randolph, Tim
%A W&#281;grzycki, Karol
%+ External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Parameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-0E6B-8
%R 10.4230/LIPIcs.ESA.2024.96
%U urn:nbn:de:0030-drops-211672
%D 2024
%B 32nd Annual European Symposium on Algorithms
%Z date of event: 2024-09-02 - 2024-09-04
%C London, UK
%B 32nd Annual European Symposium on Algorithms
%E Chan, Timothy; Fischer, Johannes; Iacono, John; Herman, Grzegorz
%P 1 - 19
%Z sequence number: 96
%I Schloss Dagstuhl
%@ 978-3-95977-338-6
%B Leibniz International Proceedings in Informatics
%N 308
%@ false

Article

B. Ray Chaudhury, J. Garg, and K. Mehlhorn

“EFX Exists for Three Agents,” Journal of the ACM, vol. 71, no. 1, 2024.

@article{RayChaudhury24,
TITLE = {{EFX} Exists for Three Agents},
AUTHOR = {Ray Chaudhury, Bhaskar and Garg, Jugal and Mehlhorn, Kurt},
LANGUAGE = {eng},
ISSN = {0004-5411},
DOI = {10.1145/3616009},
PUBLISHER = {ACM},
ADDRESS = {New York, NY},
YEAR = {2024},
DATE = {2024},
JOURNAL = {Journal of the ACM},
VOLUME = {71},
NUMBER = {1},
PAGES = {1--27},
EID = {4},
}

Endnote

%0 Journal Article
%A Ray Chaudhury, Bhaskar
%A Garg, Jugal
%A Mehlhorn, Kurt
%+ External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T EFX Exists for Three Agents : 
%G eng
%U http://hdl.handle.net/21.11116/0000-000E-6961-F
%R 10.1145/3616009
%D 2024
%J Journal of the ACM
%V 71
%N 1
%& 1
%P 1 - 27
%Z sequence number: 4
%I ACM
%C New York, NY
%@ false

Article

H. U. Simon and J. A. Telle

“MAP- and MLE-Based Teaching,” Journal of Machine Learning Research, vol. 25, 2024.

@article{Simon24JMLR,
TITLE = {{MAP}- and {MLE}-Based Teaching},
AUTHOR = {Simon, Hans Ulrich and Telle, Jan Arne},
LANGUAGE = {eng},
ISSN = {1532-4435},
URL = {http://jmlr.org/papers/v25/23-1086.html},
PUBLISHER = {Microtome Publishing},
ADDRESS = {Brookline, MA},
YEAR = {2024},
JOURNAL = {Journal of Machine Learning Research},
VOLUME = {25},
PAGES = {1--34},
EID = {96},
}

Endnote

%0 Journal Article
%A Simon, Hans Ulrich
%A Telle, Jan Arne
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T MAP- and MLE-Based Teaching : 
%G eng
%U http://hdl.handle.net/21.11116/0000-000F-4ED2-D
%U http://jmlr.org/papers/v25/23-1086.html
%7 2024
%D 2024
%J Journal of Machine Learning Research
%O JMLR
%V 25
%& 1
%P 1 - 34
%Z sequence number: 96
%I Microtome Publishing
%C Brookline, MA
%@ false

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote

BibTeX

Endnote