Large-scale Randomization and Certification

Large-scale Randomization and Certification

Description:

The main goals of this subproject are two-fold. The first goal is to support aforementioned subprojects with an algorithm engineering approach by complementing and extending the analytical results on algorithms and dynamics. For example, we will implement network creation models and generate large instances to empirically verify their properties at scale. Similarly, we plan the simulation and experimental evaluation of a variety of population protocols. The second goal is to advance the state of art in theoretical and practical graph algorithms and data structures for massive data sets with a focus on path finding and connectivity problems. We will augment these efforts by studying the existence of compact and easily understandable “certificates” for correct execution of randomized graph algorithms that rely on, e.g., streaming, sampling, and other randomized methods.

Staff:

Prof. Dr. Ulrich Meyer (Main PI)
Dr. Manuel Penschuck

Publications:

Daniel Allendorf.
A Simple Data Structure for Maintaining a Discrete Probability Distribution.
CoRR abs/2302.05682, 2023.
URL BibTeX

@article{DBLP:journals/corr/abs-2302-05682,
	author = "Daniel Allendorf",
	title = "A Simple Data Structure for Maintaining a Discrete Probability Distribution",
	journal = "CoRR",
	volume = "abs/2302.05682",
	url = "https://arxiv.org/abs/2302.05682",
	year = 2023
}

Manuel Penschuck.
Engineering Shared-Memory Parallel Shuffling to Generate Random Permutations In-Place.
CoRR abs/2302.03317, 2023.
URL BibTeX

@article{DBLP:journals/corr/abs-2302-03317,
	author = "Manuel Penschuck",
	title = "Engineering Shared-Memory Parallel Shuffling to Generate Random Permutations In-Place",
	journal = "CoRR",
	volume = "abs/2302.03317",
	url = "https://arxiv.org/abs/2302.03317",
	year = 2023
}

Daniel Allendorf, Ulrich Meyer, Manuel Penschuck and Hung Tran.
Parallel global edge switching for the uniform sampling of simple graphs with prescribed degrees.
Journal of Parallel and Distributed Computing 174:118-129, 2023.
URL, DOI BibTeX

@article{ALLENDORF2023118,
	title = "Parallel global edge switching for the uniform sampling of simple graphs with prescribed degrees",
	journal = "Journal of Parallel and Distributed Computing",
	volume = 174,
	pages = "118-129",
	year = 2023,
	issn = "0743-7315",
	doi = "https://doi.org/10.1016/j.jpdc.2022.12.010",
	url = "https://www.sciencedirect.com/science/article/pii/S0743731522002623",
	author = "Daniel Allendorf and Ulrich Meyer and Manuel Penschuck and Hung Tran"
}

Ulrich Meyer, Hung Tran and Konstantinos Tsakalidis.
Certifying Induced Subgraphs in Large Graphs.
In Proceedings of 17th International Conference and Workshops on Algorithms and Computation, WALCOM (accepted). 2023.
URL BibTeX

@inproceedings{toappear/nlpa3,
	author = "Ulrich Meyer and Hung Tran and Konstantinos Tsakalidis",
	title = "Certifying Induced Subgraphs in Large Graphs",
	booktitle = "Proceedings of 17th International Conference and Workshops on Algorithms and Computation, {WALCOM} (accepted)",
	note = "Accepted for WALCOM 2023",
	year = 2023,
	url = "https://ae.cs.uni-frankfurt.de/public_files/walcom23.pdf"
}

Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Ulrich Meyer, Manuel Penschuck and Christopher Weyand.
Efficiently generating geometric inhomogeneous and hyperbolic random graphs.
Netw. Sci. 10(4):361–380, 2022.
URL, DOI BibTeX

@article{DBLP:journals/netsci/BlasiusFKMPW22,
	author = {Thomas Bl{\"{a}}sius and Tobias Friedrich and Maximilian Katzmann and Ulrich Meyer and Manuel Penschuck and Christopher Weyand},
	title = "Efficiently generating geometric inhomogeneous and hyperbolic random graphs",
	journal = "Netw. Sci.",
	volume = 10,
	number = 4,
	pages = "361--380",
	year = 2022,
	url = "https://doi.org/10.1017/nws.2022.32",
	doi = "10.1017/nws.2022.32",
	timestamp = "Mon, 13 Feb 2023 21:53:13 +0100",
	biburl = "https://dblp.org/rec/journals/netsci/BlasiusFKMPW22.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Manuel Penschuck, Ulrik Brandes, Michael Hamann, Sebastian Lamm, Ulrich Meyer, Ilya Safro, Peter Sanders and Christian Schulz.
Recent Advances in Scalable Network Generation.
In David A Bader (ed.). Massive Graph Analytics. CRC Press, 2022, pages 333–376.
BibTeX

@incollection{PBHLMSSS22,
	editor = "David A. Bader",
	author = "Manuel Penschuck and Ulrik Brandes and Michael Hamann and Sebastian Lamm and Ulrich Meyer and Ilya Safro and Peter Sanders and Christian Schulz",
	title = "Recent Advances in Scalable Network Generation",
	booktitle = "Massive Graph Analytics",
	pages = "333--376",
	year = 2022,
	publisher = "CRC Press"
}

Daniel Allendorf, Ulrich Meyer, Manuel Penschuck, Hung Tran and Nick Wormald.
Engineering Uniform Sampling of Graphs with a Prescribed Power-law Degree Sequence.
In Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2022, Alexandria, VA, USA, January 9-10, 2022. 2022, 27–40.
URL, DOI BibTeX

@inproceedings{DBLP:conf/alenex/Allendorf0PTW22,
	author = "Daniel Allendorf and Ulrich Meyer and Manuel Penschuck and Hung Tran and Nick Wormald",
	title = "Engineering Uniform Sampling of Graphs with a Prescribed Power-law Degree Sequence",
	booktitle = "Proceedings of the Symposium on Algorithm Engineering and Experiments, {ALENEX} 2022, Alexandria, VA, USA, January 9-10, 2022",
	pages = "27--40",
	publisher = "{SIAM}",
	year = 2022,
	url = "https://doi.org/10.1137/1.9781611977042.3",
	doi = "10.1137/1.9781611977042.3",
	timestamp = "Mon, 11 Apr 2022 13:26:42 +0200",
	biburl = "https://dblp.org/rec/conf/alenex/Allendorf0PTW22.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Daniel Allendorf, Ulrich Meyer, Manuel Penschuck and Hung Tran.
Parallel Global Edge Switching for the Uniform Sampling of Simple Graphs with Prescribed Degrees.
In 2022 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2022, Lyon, France, May 30 - June 3, 2022. 2022, 269–279.
URL, DOI BibTeX

@inproceedings{DBLP:conf/ipps/Allendorf0PT22,
	author = "Daniel Allendorf and Ulrich Meyer and Manuel Penschuck and Hung Tran",
	title = "Parallel Global Edge Switching for the Uniform Sampling of Simple Graphs with Prescribed Degrees",
	booktitle = "2022 {IEEE} International Parallel and Distributed Processing Symposium, {IPDPS} 2022, Lyon, France, May 30 - June 3, 2022",
	pages = "269--279",
	publisher = "{IEEE}",
	year = 2022,
	url = "https://doi.org/10.1109/IPDPS53621.2022.00034",
	doi = "10.1109/IPDPS53621.2022.00034",
	timestamp = "Fri, 22 Jul 2022 11:43:23 +0200",
	biburl = "https://dblp.org/rec/conf/ipps/Allendorf0PT22.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Oliver Gebhard, Max Hahn-Klimroth, Olaf Parczyk, Manuel Penschuck, Maurice Rolvien, Jonathan Scarlett and Nelvin Tan.
Near-Optimal Sparsity-Constrained Group Testing: Improved Bounds and Algorithms.
IEEE Trans. Inf. Theory 68(5):3253–3280, 2022.
URL, DOI BibTeX

@article{DBLP:journals/tit/GebhardHPPRST22,
	author = "Oliver Gebhard and Max Hahn{-}Klimroth and Olaf Parczyk and Manuel Penschuck and Maurice Rolvien and Jonathan Scarlett and Nelvin Tan",
	title = "Near-Optimal Sparsity-Constrained Group Testing: Improved Bounds and Algorithms",
	journal = "{IEEE} Trans. Inf. Theory",
	volume = 68,
	number = 5,
	pages = "3253--3280",
	year = 2022,
	url = "https://doi.org/10.1109/TIT.2022.3141244",
	doi = "10.1109/TIT.2022.3141244",
	timestamp = "Wed, 18 May 2022 10:21:10 +0200",
	biburl = "https://dblp.org/rec/journals/tit/GebhardHPPRST22.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Amin Coja-Oghlan, Max Hahn-Klimroth, Philipp Loick and Manuel Penschuck.
Efficient and Accurate Group Testing via Belief Propagation: An Empirical Study.
In 20th International Symposium on Experimental Algorithms, SEA 2022, July 25-27, 2022, Heidelberg, Germany 233. 2022, 8:1–8:18.
URL, DOI BibTeX

@inproceedings{DBLP:conf/wea/Coja-OghlanHLP22,
	author = "Amin Coja{-}Oghlan and Max Hahn{-}Klimroth and Philipp Loick and Manuel Penschuck",
	title = "Efficient and Accurate Group Testing via Belief Propagation: An Empirical Study",
	booktitle = "20th International Symposium on Experimental Algorithms, {SEA} 2022, July 25-27, 2022, Heidelberg, Germany",
	series = "LIPIcs",
	volume = 233,
	pages = "8:1--8:18",
	publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
	year = 2022,
	url = "https://doi.org/10.4230/LIPIcs.SEA.2022.8",
	doi = "10.4230/LIPIcs.SEA.2022.8",
	timestamp = "Mon, 11 Jul 2022 15:33:19 +0200",
	biburl = "https://dblp.org/rec/conf/wea/Coja-OghlanHLP22.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Manuel Penschuck.
Scalable generation of random graphs.
Doctoral Thesis, Universitätsbibliothek Johann Christian Senckenberg, 2021.
URL, DOI BibTeX

@phdthesis{Penschuck2021,
	author = "Manuel Penschuck",
	title = "Scalable generation of random graphs",
	type = "Doctoral Thesis",
	pages = 298,
	school = {Universit{\"a}tsbibliothek Johann Christian Senckenberg},
	url = "https://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/61035",
	doi = "10.21248/gups.61035",
	year = 2021
}

Gerth Stølting Brodal, Rolf Fagerberg, David Hammer, Ulrich Meyer, Manuel Penschuck and Hung Tran.
An Experimental Study of External Memory Algorithms for Connected Components.
In 19th International Symposium on Experimental Algorithms, SEA 2021, June 7-9, 2021, Nice, France 190. 2021, 23:1–23:23.
URL, DOI BibTeX

@inproceedings{DBLP:conf/wea/BrodalFH0PT21,
	author = "Gerth St{\o}lting Brodal and Rolf Fagerberg and David Hammer and Ulrich Meyer and Manuel Penschuck and Hung Tran",
	title = "An Experimental Study of External Memory Algorithms for Connected Components",
	booktitle = "19th International Symposium on Experimental Algorithms, {SEA} 2021, June 7-9, 2021, Nice, France",
	series = "LIPIcs",
	volume = 190,
	pages = "23:1--23:23",
	publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
	year = 2021,
	url = "https://doi.org/10.4230/LIPIcs.SEA.2021.23",
	doi = "10.4230/LIPIcs.SEA.2021.23",
	timestamp = "Mon, 03 Jan 2022 22:20:17 +0100",
	biburl = "https://dblp.org/rec/conf/wea/BrodalFH0PT21.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Dimitris Achlioptas, Amin Coja-Oghlan, Max Hahn-Klimroth, Joon Lee, Noëla Müller, Manuel Penschuck and Guangyan Zhou.
The number of satisfying assignments of random 2-SAT formulas.
Random Struct. Algorithms 58(4):609–647, 2021.
URL, DOI BibTeX

@article{DBLP:journals/rsa/AchlioptasCHLMP21,
	author = {Dimitris Achlioptas and Amin Coja{-}Oghlan and Max Hahn{-}Klimroth and Joon Lee and No{\"{e}}la M{\"{u}}ller and Manuel Penschuck and Guangyan Zhou},
	title = "The number of satisfying assignments of random 2-SAT formulas",
	journal = "Random Struct. Algorithms",
	volume = 58,
	number = 4,
	pages = "609--647",
	year = 2021,
	url = "https://doi.org/10.1002/rsa.20993",
	doi = "10.1002/rsa.20993",
	timestamp = "Thu, 14 Oct 2021 08:50:41 +0200",
	biburl = "https://dblp.org/rec/journals/rsa/AchlioptasCHLMP21.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Petra Berenbrink, David Hammer, Dominik Kaaser, Ulrich Meyer, Manuel Penschuck and Hung Tran.
Simulating Population Protocols in Sub-Constant Time per Interaction.
In 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference) 173. 2020, 16:1–16:22.
URL, DOI BibTeX

@inproceedings{DBLP:conf/esa/BerenbrinkHK0PT20,
	author = "Petra Berenbrink and David Hammer and Dominik Kaaser and Ulrich Meyer and Manuel Penschuck and Hung Tran",
	title = "Simulating Population Protocols in Sub-Constant Time per Interaction",
	booktitle = "28th Annual European Symposium on Algorithms, {ESA} 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference)",
	series = "LIPIcs",
	volume = 173,
	pages = "16:1--16:22",
	publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
	year = 2020,
	url = "https://doi.org/10.4230/LIPIcs.ESA.2020.16",
	doi = "10.4230/LIPIcs.ESA.2020.16",
	timestamp = "Thu, 16 Sep 2021 18:07:51 +0200",
	biburl = "https://dblp.org/rec/conf/esa/BerenbrinkHK0PT20.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Daniel Allendorf, Ulrich Meyer, Manuel Penschuck and Hung Tran.
Parallel and I/O-Efficient Algorithms for Non-Linear Preferential Attachment.
In 2023 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX). 65-76.
URL, DOI BibTeX

@inproceedings{doi:10.1137/1.9781611977561.ch6,
	author = "Daniel Allendorf and Ulrich Meyer and Manuel Penschuck and Hung Tran",
	title = "Parallel and I/O-Efficient Algorithms for Non-Linear Preferential Attachment",
	booktitle = "2023 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX)",
	chapter = "",
	pages = "65-76",
	doi = "10.1137/1.9781611977561.ch6",
	url = "https://epubs.siam.org/doi/abs/10.1137/1.9781611977561.ch6"
}

Algorithms, Dynamics, and Information Flow in NetworksDFG Research Unit

Description:

Staff:

Publications:

Algorithms, Dynamics, and Information Flow in Networks
DFG Research Unit