Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

This is an archived page of a former group member.
Martin Krejca is an assistant professor at the École Polytechnique in Palaiseau, France.

Research Interests

I like getting to the core of things. More specifically, I am interested in the complexity of discrete processes and the reasons behind their complexity. Currently, my main focus is on the analysis of randomized processes. However, I am also interested in complexity theory and game theory, where complexity seems to emerge from simple concepts. For all of these settings, I am not only interested in the complexity alone but also in the analysis and development of methods and tools used in order to derive good run time results.

Publications without Group Members

2024

  • Estimation-of-Distributio... - Download
    Ben Jedidia, Firas; Doerr, Benjamin; Krejca, Martin S. Estimation-of-Distribution Algorithms for Multi-Valued Decision VariablesTheoretical Computer Science 2024: 114622:1–114622:16
     
  • Proven Runtime Guarantees... - Download
    Doerr, Benjamin; Krejca, Martin S.; Weeks, Noé Proven Runtime Guarantees for How the MOEA/D Computes the Pareto Front From the Subproblem SolutionsParallel Problem Solving from Nature (PPSN) 2024
     
  • Runtime Analysis of the (... - Download
    Doerr, Benjamin; Echarghaoui, Aymen; Jamal, Mohammed; Krejca, Martin S. Runtime Analysis of the (µ + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse PopulationsAnnual AAAI Conference on Artificial Intelligence (AAAI) 2024: 20683–20691
     
  • A Flexible Evolutionary A... - Download
    Krejca, Martin S.; Witt, Carsten A Flexible Evolutionary Algorithm With Dynamic Mutation Rate ArchiveGenetic and Evolutionary Computation Conference (GECCO) 2024
     
  • Superior Genetic Algorith... - Download
    Doerr, Benjamin; Krejca, Martin S.; Vu, Nguyen Superior Genetic Algorithms for the Target Set Selection Problem Based on Power-Law Parameter Choices and Simple Greedy Heuristics 2024
     

2023

  • Run Time Analysis for Ran... - Download
    Doerr, Carola; Krejca, Martin S. Run Time Analysis for Random Local Search on Generalized Majority FunctionsIEEE Transactions on Evolutionary Computation 2023: 1385–1397
     
  • Bivariate Estimation-of-D... - Download
    Doerr, Benjamin; Krejca, Martin S. Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of OptimaTheoretical Computer Science 2023: 114074.1–114074.16
     
  • Estimation-of-Distributio... - Download
    Ben Jedidia, Firas; Doerr, Benjamin; Krejca, Martin S. Estimation-of-Distribution Algorithms for Multi-Valued Decision VariablesGenetic and Evolutionary Computation Conference (GECCO) 2023: 230–238
     

2022

  • Theory-inspired Parameter... - Download
    Biedenkapp, André; Dang, Nguyên; Krejca, Martin S.; Hutter, Frank; Doerr, Carola Theory-inspired Parameter Control Benchmarks for Dynamic Algorithm ConfigurationGenetic and Evolutionary Computation Conference (GECCO) 2022: 766–775
    Best-Paper Award (GECH Track)
     

2021

  • The Univariate Marginal D... - Download
    Doerr, Benjamin; Krejca, Martin S. The Univariate Marginal Distribution Algorithm Copes Well with Deception and EpistasisEvolutionary Computation 2021: 543–563
     

Publications with Group Members

[ 2024 ] [ 2023 ] [ 2022 ] [ 2021 ] [ 2020 ] [ 2019 ] [ 2018 ] [ 2017 ] [ 2016 ] [ 2015 ]

2024 [ nach oben ]

  • Analysis of the survival ... - Download
    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
     
  • The Irrelevance of Influe... - Download
    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
     
  • From Market Saturation to... - Download
    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
     
  • Robust Parameter Fitting ... - Download
    Bläsius, Thomas; Cohen, Sarel; Fischbeck, Philipp; Friedrich, Tobias; Krejca, Martin S. Robust Parameter Fitting to Realistic Network Models via Iterative Stochastic ApproximationCoRR 2024
    ArXiv preprint
     

2023 [ nach oben ]

  • The Impact of Geometry on... - Download
    Bläsius, Thomas; Friedrich, Tobias; Krejca, Martin S.; Molitor, Louise The Impact of Geometry on Monochrome Regions in the Flip Schelling ProcessComputational Geometry (CGTA) 2023: 101902
     
  • Evolutionary Minimization... - Download
    Böther, Maximilian; Schiller, Leon; Fischbeck, Philipp; Molitor, Louise; Krejca, Martin S.; Friedrich, Tobias Evolutionary Minimization of Traffic CongestionIEEE Transactions on Evolutionary Computation 2023: 1809–1821
     
  • Polymer Dynamics via Cliq... - Download
    Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, Marcus Polymer Dynamics via Cliques: New Conditions for ApproximationsTheoretical Computer Science 2023: 230–252
     
  • The Common-Neighbors Metr... - Download
    Cohen, Sarel; Fischbeck, Philipp; Friedrich, Tobias; Krejca, Martin S. The Common-Neighbors Metric is Noise-Robust and Reveals Substructures of Real-World NetworksPacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD) 2023: 67–79
     

2022 [ nach oben ]

  • A Spectral Independence V... - Download
    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
     
  • Algorithms for hard-const... - Download
    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
     
  • Escaping Local Optima Wit... - Download
    Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Rajabi, Amirhossein Escaping Local Optima With Local Search: A Theory-Driven DiscussionParallel Problem Solving from Nature (PPSN) 2022: 442–455
    Best Paper Award and Best Poster Award
     
  • Accelerated Information D... - Download
    Cohen, Sarel; Fischbeck, Philipp; Friedrich, Tobias; Krejca, Martin S.; Sauerwald, Thomas Accelerated Information Dissemination on Networks with Local and Global EdgesStructural Information and Communication Complexity (SIROCCO) 2022: 79–97
     

2021 [ nach oben ]

  • A Simplified Run Time Ana... - Download
    Doerr, Benjamin; Krejca, Martin S. A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnesTheoretical Computer Science 2021: 121–128
     
  • Evolutionary Minimization... - Download
    Böther, Maximilian; Schiller, Leon; Fischbeck, Philipp; Molitor, Louise; Krejca, Martin S.; Friedrich, Tobias Evolutionary Minimization of Traffic CongestionGenetic and Evolutionary Computation Conference (GECCO) 2021: 937–945
    Best-Paper Award (RWA Track)
     
  • A spectral independence v... - Download
    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
     
  • The Impact of Geometry on... - Download
    Bläsius, Thomas; Friedrich, Tobias; Krejca, Martin S.; Molitor, Louise The Impact of Geometry on Monochrome Regions in the Flip Schelling ProcessInternational Symposium on Algorithms and Computation, (ISAAC) 2021 2021: 29:1–29:17
     

2020 [ nach oben ]

  • Significance-based Estima... - Download
    Doerr, Benjamin; Krejca, Martin S. Significance-based Estimation-of-Distribution AlgorithmsIEEE Transactions on Evolutionary Computation 2020: 1025–1034
     
  • Lower Bounds on the Run T... - Download
    Krejca, Martin S.; Witt, Carsten Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMaxTheoretical Computer Science 2020: 143–165
     
  • Theory of Estimation-of-D... - Download
    Krejca, Martin S.; Witt, Carsten Theory of Estimation-of-Distribution AlgorithmsTheory of Evolutionary Computation: Recent Developments in Discrete Optimization 2020: 405–442
     
  • The Univariate Marginal D... - Download
    Doerr, Benjamin; Krejca, Martin S. The Univariate Marginal Distribution Algorithm Copes Well with Deception and EpistasisEvolutionary Computation in Combinatorial Optimization (EvoCOP) 2020: 51–66
    Best-Paper Award
     
  • Bivariate Estimation-of-D... - Download
    Doerr, Benjamin; Krejca, Martin S. Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of OptimaGenetic and Evolutionary Computation Conference (GECCO) 2020: 796–804
     
  • Memetic Genetic Algorithm... - Download
    Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rizzo, Manuel; Zahn, Arthur Memetic Genetic Algorithms for Time Series Compression by Piecewise Linear ApproximationInternational Conference on Neural Information Processing (ICONIP) 2020: 592–604
     

2019 [ nach oben ]

  • Routing for On-Street Par... - Download
    Friedrich, Tobias; Krejca, Martin S.; Rothenberger, Ralf; Arndt, Tobias; Hafner, Danijar; Kellermeier, Thomas; Krogmann, Simon; Razmjou, Armin Routing for On-Street Parking Search using Probabilistic DataAI Communications 2019: 113–124
     
  • Surfing on the seascape: ... - Download
    Trubenova, Barbora; Kötzing, Timo; Krejca, Martin S.; Lehre, Per Kristian Surfing on the seascape: Adaptation in a changing environmentEvolution: International Journal of Organic Evolution 2019: 1356–1374
     
  • Unbiasedness of Estimatio... - Download
    Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S. Unbiasedness of Estimation-of-Distribution AlgorithmsTheoretical Computer Science 2019: 46–59
     
  • First-hitting times under... - Download
    Kötzing, Timo; Krejca, Martin S. First-hitting times under driftTheoretical Computer Science 2019: 51–69
     
  • Mixed Integer Programming... - Download
    Peters, Jannik; Stephan, Daniel; Amon, Isabel; Gawendowicz, Hans; Lischeid, Julius; Salabarria, Julius; Umland, Jonas; Werner, Felix; Krejca, Martin S.; Rothenberger, Ralf; Kötzing, Timo; Friedrich, Tobias Mixed Integer Programming versus Evolutionary Computation for Optimizing a Hard Real-World Staff Assignment ProblemInternational Conference on Automated Planning and Scheduling (ICAPS) 2019: 541–554
     

2018 [ nach oben ]

  • Escaping Local Optima Usi... - Download
    Dang, Duc-Cuong; Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Lehre, Per Kristian; Oliveto, Pietro S.; Sudholt, Dirk; Sutton, Andrew M. Escaping Local Optima Using Crossover with Emergent DiversityIEEE Transactions on Evolutionary Computation 2018: 484–497
     
  • Significance-based Estima... - Download
    Doerr, Benjamin; Krejca, Martin S. Significance-based Estimation-of-Distribution AlgorithmsGenetic and Evolutionary Computation Conference (GECCO) 2018: 1483–1490
     
  • First-Hitting Times for F... - Download
    Kötzing, Timo; Krejca, Martin S. First-Hitting Times for Finite State SpacesParallel Problem Solving From Nature (PPSN) 2018: 79–91
     
  • First-Hitting Times Under... - Download
    Kötzing, Timo; Krejca, Martin S. First-Hitting Times Under Additive DriftParallel Problem Solving From Nature (PPSN) 2018: 92–104
     
  • Memory-restricted Routing... - Download
    Bläsius, Thomas; Eube, Jan; Feldtkeller, Thomas; Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rothenberger, Ralf; Severin, Julius; Sommer, Fabian; Trautmann, Justin Memory-restricted Routing With Tiled Map DataSystems, Man, and Cybernetics (SMC) 2018: 3347–3354
     

2017 [ nach oben ]

  • The Compact Genetic Algor... - Download
    Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. The Compact Genetic Algorithm is Efficient under Extreme Gaussian NoiseIEEE Transactions on Evolutionary Computation 2017: 477–490
     
  • Lower Bounds on the Run T... - Download
    Krejca, Martin S.; Witt, Carsten Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMaxFoundations of Genetic Algorithms (FOGA) 2017: 65–79
     

2016 [ nach oben ]

  • Robustness of Ant Colony ... - Download
    Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. Robustness of Ant Colony Optimization to NoiseEvolutionary Computation 2016: 237–254
     
  • Probabilistic Routing for... - Download
    Arndt, Tobias; Hafner, Danijar; Kellermeier, Thomas; Krogmann, Simon; Razmjou, Armin; Krejca, Martin S.; Rothenberger, Ralf; Friedrich, Tobias Probabilistic Routing for On-Street Parking SearchEuropean Symposium on Algorithms (ESA) 2016: 6:1–6:13
     
  • The Benefit of Recombinat... - Download
    Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. The Benefit of Recombination in Noisy Evolutionary SearchGenetic and Evolutionary Computation Conference (GECCO) 2016: 161–162
     
  • Escaping Local Optima wit... - Download
    Dang, Duc-Cuong; Friedrich, Tobias; Krejca, Martin S.; Kötzing, Timo; Lehre, Per Kristian; Oliveto, Pietro S.; Sudholt, Dirk; Sutton, Andrew Michael Escaping Local Optima with Diversity Mechanisms and CrossoverGenetic and Evolutionary Computation Conference (GECCO) 2016: 645–652
     
  • Fast Building Block Assem... - Download
    Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Nallaperuma, Samadhi; Neumann, Frank; Schirneck, Martin Fast Building Block Assembly by Majority Vote CrossoverGenetic and Evolutionary Computation Conference (GECCO) 2016: 661–668
     
  • EDAs cannot be Balanced a... - Download
    Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S. EDAs cannot be Balanced and StableGenetic and Evolutionary Computation Conference (GECCO) 2016: 1139–1146
     
  • Graceful Scaling on Unifo... - Download
    Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. Graceful Scaling on Uniform versus Steep-Tailed NoiseParallel Problem Solving From Nature (PPSN) 2016: 761–770
     
  • Emergence of Diversity an... - Download
    Dang, Duc-Cuong; Lehre, Per Kristian; Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Oliveto, Pietro S.; Sudholt, Dirk; Sutton, Andrew M. Emergence of Diversity and its Benefits for Crossover in Genetic AlgorithmsParallel Problem Solving From Nature (PPSN) 2016: 890–900
     

2015 [ nach oben ]

  • Robustness of Ant Colony ... - Download
    Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. Robustness of Ant Colony Optimization to NoiseGenetic and Evolutionary Computation Conference (GECCO) 2015: 17–24
    Best-Paper Award (ACO/SI Track)
     
  • The Benefit of Recombinat... - Download
    Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M. The Benefit of Recombination in Noisy Evolutionary SearchInternational Symposium of Algorithms and Computation (ISAAC) 2015: 140–150
     

Theses

[ 2019 ]

2019 [ nach oben ]

  • Theoretical Analyses of U... - Download
    Theoretical Analyses of Univariate Estimation-of-Distribution Algorithms. Technical Report (PhD dissertation), Krejca, Martin S. (2019).
    ACM SIGEVO Dissertation Award, Honorable Mention