Marcus Pappik
Chair for Algorithm Engineering
Hasso Plattner Institute
Office: K-2.07
Tel.: +49 331 5509-424
E-Mail: Marcus.Pappik(at)hpi.de
Research Interests
My research interests include a variety of topics such as data science, computational statistics (especially causal inference), game theory and stochastic processes. Currently, I am focusing on the application of Markov chains to discrete and continuous systems from statistical physics and the resulting algorithmic applications.
A variety of connections between theoretical computer science and statistical physics has been investigated within recent years. Some of the most remarkable results relate phase transitions of physical systems with the traceability of computational problems. The ongoing effort to connect those scientific branches leads to a two-way exchange: tools from statistical physics are used to explain computational properties of various algorithmic problems, and results from theoretical computer science are used to investigate phenomena from statistical physics. Probabilistic properties, such as spatial decay of correlations and rapid mixing of certain Markov chains, seem to be at the very core of these connections.
Teaching
During my masters and Ph.D. studies, I was Teaching Assistant for the following courses:
- Introduction to Quantum Computing (Sommer 2021)
- Theorie der künstlichen Intelligenz (Winter 2020/2021)
- Theory of Evolutionary Algorithms (Summer 2020)
- Probability and Computing (Summer 2019)
- Probability Theory (Winter 2018/2019)
Moreover, I was co-supervising the following projects and theses:
- Bachelor Project: Algorithm Auditing via Statistical Hypothesis Testing (Winter 2022/2023 + Summer 2023)
- Master's Thesis: Epidemic thresholds for the SIS contact process on stars and clique stars (by Nicolas Klodt, Summer 2021)
Invited Talks
- talk on 'Discretization-based algorithms for repulsive Gibbs point processes' at the Dagstuhl Seminar on Counting and Sampling: Algorithms and Complexity 2022
- presentation of our publication 'Algorithms for hard-constraint point processes via discretization' at COCOON 2022 (online)
- presentation of our publication 'A spectral independence view on hard spheres via block dynamics' at ICALP 2021 (online); recording available online
- presentation of our publication 'Convergence and Hardness of Strategic Schelling Segregation' at WINE 2019; slides and recording (at 02:05:00) available online
Publications
2025
Baguley, Samuel; Friedrich, Tobias; Neumann, Aneta; Neumann, Frank; Pappik, Marcus; Zeif, Ziena Fixed Parameter Multi-Objective Evolutionary Algorithms for the W-Separator ProblemAlgorithmica 2025: 1432–0541
Göbel, Andreas; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus Resistance is Futile: Gradually Declining Immunity Retains the Exponential Duration of Immunity-Free DiffusionInternational Joint Conferences on Artifical Intelligence (IJCAI) 2025
[ ] [ ] [ Download ]
2024
Friedrich, Tobias; Göbel, Andres; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus Analysis of the survival time of the SIRS process via expansionElectronic Journal of Probability 2024: 1–29
Friedrich, Tobias; Göbel, Andreas; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus The Irrelevance of Influencers: Information Diffusion with Re-Activation and Immunity Lasts Exponentially Long on Social Network ModelsAnnual AAAI Conference on Artificial Intelligence 2024
Friedrich, Tobias; Göbel, Andreas; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus From Market Saturation to Social Reinforcement: Understanding the Impact of Non-Linearity in Information Diffusion ModelsThe 23rd International Conference on Autonomous Agents and Multi-Agent Systems 2024
2023
Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, Marcus Polymer Dynamics via Cliques: New Conditions for ApproximationsTheoretical Computer Science 2023: 230–252
Baguley, Samuel; Friedrich, Tobias; Neumann, Aneta; Neumann, Frank; Pappik, Marcus; Zeif, Ziena Fixed Parameter Multi-Objective Evolutionary Algorithms for the W-Separator ProblemGenetic and Evolutionary Computation Conference (GECCO) 2023
Anand, Konrad; Göbel, Andreas; Pappik, Marcus; Perkins, Will Perfect Sampling for Hard Spheres from Strong Spatial MixingInternational Conference on Randomization and Computation (Random) 2023: 38:1–38:18
2022
Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, Marcus A Spectral Independence View on Hard Spheres via Block DynamicsSIAM Journal on Discrete Mathematics 2022: 2282–2322
Friedrich, Tobias; Göbel, Andreas; Katzmann, Maximilian; Krejca, Martin S.; Pappik, Marcus Algorithms for hard-constraint point processes via discretizationInternational Computing and Combinatorics Conference (COCOON) 2022: 242–254
Baguley, Samuel; Friedrich, Tobias; Timo, Kötzing; Li, Xiaoyue; Pappik, Marcus; Zeif, Ziena Analysis of a Gray-Box Operator for Vertex CoverGenetic and Evolutionary Computation Conference (GECCO) 2022: 1363–1371
2021
Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, Marcus A spectral independence view on hard spheres via block dynamicsInternational Colloquium on Automata, Languages and Programming (ICALP) 2021: 66:1–66:15
2019
Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Molitor, Louise; Pappik, Marcus; Schöne, Friedrich; Sommer, Fabian; Stangl, David Convergence and Hardness of Strategic Schelling SegregationWeb and Internet Economics (WINE) 2019: 156–170
2018
Kumar Shekar, Arvind; Pappik, Marcus; Iglesias Sánchez, Patricia; Müller, Emmanuel Selection of Relevant and Non-Redundant Multivariate Ordinal Patterns for Time Series ClassificationDiscovery Science (DS) 2018: 224–240
[ ] [ ] [ DOI ]
2017
Kirsch, Louis; Riekenbrauck, Niklas; Thevessen, Daniel; Pappik, Marcus; Stebner, Axel; Kunze, Julius; Meissner, Alexander; Kumar Shekar, Arvind; Müller, Emmanuel Framework for Exploring and Understanding Multivariate CorrelationsMachine Learning and Knowledge Discovery in Databases (ECML/PKDD) 2017: 404–408
Theses
[ 2020 ]
2020
Pappik, Marcus New Conditions via Markov Chains: Approximating Partition Functions of Abstract Polymer Models without Cluster Expansionmaster’s thesis, Hasso Plattner Institute 2020
[ ] [ ] [ Download ]