Asst.-Prof. (I’X) Dr. Martin Krejca
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
2025
Doerr, Benjamin; Korkotashvili, Dimitri; Krejca, Martin S.Difficulties of the NSGA-II with the Many-Objective LeadingOnes ProblemIEEE Transactions on Evolutionary Computation 2025
[ ][ ][ Download ]
Chwiałkowski, Marcel; Doerr, Benjamin; Krejca, Martin S.Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes BenchmarkIEEE Transactions on Evolutionary Computation 2025
Doerr, Benjamin; Krejca, Martin S.; Rudolph, GünterRuntime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer SpacesAnnual AAAI Conference on Artificial Intelligence (AAAI) 2025: 26955–26963
Doerr, Benjamin; Ivan, Tudor; Krejca, Martin S.Speeding Up the NSGA-II With a Simple Tie-Breaking RuleAnnual AAAI Conference on Artificial Intelligence (AAAI) 2025: 26964–26972
Alghouass, Yasser; Doerr, Benjamin; Krejca, Martin S.; Lagmah, MohammedProven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-IIInternational Joint Conferences on Artifical Intelligence (IJCAI) 2025
[ ][ ][ Download ]
Doerr, Benjamin; Krejca, Martin S.; Opris, AndreTight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary AlgorithmInternational Joint Conferences on Artifical Intelligence (IJCAI) 2025
[ ][ ][ Download ]
2024
Ben Jedidia, Firas; Doerr, Benjamin; Krejca, Martin S.Estimation-of-Distribution Algorithms for Multi-Valued Decision VariablesTheoretical Computer Science 2024: 114622:1–114622:16
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
Doerr, Benjamin; Krejca, Martin S.; Vu, NguyenSuperior Genetic Algorithms for the Target Set Selection Problem Based on Power-Law Parameter Choices and Simple Greedy HeuristicsGenetic and Evolutionary Computation Conference (GECCO) 2024: 169–177
Krejca, Martin S.; Witt, CarstenA Flexible Evolutionary Algorithm With Dynamic Mutation Rate ArchiveGenetic and Evolutionary Computation Conference (GECCO) 2024: 1578–1586
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: 197–212
2023
Doerr, Carola; Krejca, Martin S.Run Time Analysis for Random Local Search on Generalized Majority FunctionsIEEE Transactions on Evolutionary Computation 2023: 1385–1397
Doerr, Benjamin; Krejca, Martin S.Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of OptimaTheoretical Computer Science 2023: 114074.1–114074.16
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
Biedenkapp, André; Dang, Nguyên; Krejca, Martin S.; Hutter, Frank; Doerr, CarolaTheory-inspired Parameter Control Benchmarks for Dynamic Algorithm ConfigurationGenetic and Evolutionary Computation Conference (GECCO) 2022: 766–775
Best-Paper Award (GECH Track)
2021
Doerr, Benjamin; Krejca, Martin S.The Univariate Marginal Distribution Algorithm Copes Well with Deception and EpistasisEvolutionary Computation 2021: 543–563
Publications with Group Members
[ 2025 ][ 2024 ][ 2023 ][ 2022 ][ 2021 ][ 2020 ][ 2019 ][ 2018 ][ 2017 ][ 2016 ][ 2015 ]
2025
Göbel, Andreas; Klodt, Nicolas; Krejca, Martin S.; Pappik, MarcusResistance 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, MarcusAnalysis 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, MarcusThe 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, MarcusFrom 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
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
Bläsius, Thomas; Friedrich, Tobias; Krejca, Martin S.; Molitor, LouiseThe Impact of Geometry on Monochrome Regions in the Flip Schelling ProcessComputational Geometry (CGTA) 2023: 101902
Böther, Maximilian; Schiller, Leon; Fischbeck, Philipp; Molitor, Louise; Krejca, Martin S.; Friedrich, TobiasEvolutionary Minimization of Traffic CongestionIEEE Transactions on Evolutionary Computation 2023: 1809–1821
Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, MarcusPolymer Dynamics via Cliques: New Conditions for ApproximationsTheoretical Computer Science 2023: 230–252
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
Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, MarcusA 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, MarcusAlgorithms for hard-constraint point processes via discretizationInternational Computing and Combinatorics Conference (COCOON) 2022: 242–254
Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Rajabi, AmirhosseinEscaping Local Optima With Local Search: A Theory-Driven DiscussionParallel Problem Solving from Nature (PPSN) 2022: 442–455
Best Paper Award and Best Poster Award
Cohen, Sarel; Fischbeck, Philipp; Friedrich, Tobias; Krejca, Martin S.; Sauerwald, ThomasAccelerated Information Dissemination on Networks with Local and Global EdgesStructural Information and Communication Complexity (SIROCCO) 2022: 79–97
2021
Doerr, Benjamin; Krejca, Martin S.A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnesTheoretical Computer Science 2021: 121–128
Böther, Maximilian; Schiller, Leon; Fischbeck, Philipp; Molitor, Louise; Krejca, Martin S.; Friedrich, TobiasEvolutionary Minimization of Traffic CongestionGenetic and Evolutionary Computation Conference (GECCO) 2021: 937–945
Best-Paper Award (RWA Track)
Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, MarcusA spectral independence view on hard spheres via block dynamicsInternational Colloquium on Automata, Languages and Programming (ICALP) 2021: 66:1–66:15
Bläsius, Thomas; Friedrich, Tobias; Krejca, Martin S.; Molitor, LouiseThe Impact of Geometry on Monochrome Regions in the Flip Schelling ProcessInternational Symposium on Algorithms and Computation, (ISAAC) 2021 2021: 29:1–29:17
2020
Doerr, Benjamin; Krejca, Martin S.Significance-based Estimation-of-Distribution AlgorithmsIEEE Transactions on Evolutionary Computation 2020: 1025–1034
Krejca, Martin S.; Witt, CarstenLower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMaxTheoretical Computer Science 2020: 143–165
Krejca, Martin S.; Witt, CarstenTheory of Estimation-of-Distribution AlgorithmsTheory of Evolutionary Computation: Recent Developments in Discrete Optimization 2020: 405–442
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
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
Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rizzo, Manuel; Zahn, ArthurMemetic Genetic Algorithms for Time Series Compression by Piecewise Linear ApproximationInternational Conference on Neural Information Processing (ICONIP) 2020: 592–604
2019
Friedrich, Tobias; Krejca, Martin S.; Rothenberger, Ralf; Arndt, Tobias; Hafner, Danijar; Kellermeier, Thomas; Krogmann, Simon; Razmjou, ArminRouting for On-Street Parking Search using Probabilistic DataAI Communications 2019: 113–124
Trubenova, Barbora; Kötzing, Timo; Krejca, Martin S.; Lehre, Per KristianSurfing on the seascape: Adaptation in a changing environmentEvolution: International Journal of Organic Evolution 2019: 1356–1374
Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.Unbiasedness of Estimation-of-Distribution AlgorithmsTheoretical Computer Science 2019: 46–59
Kötzing, Timo; Krejca, Martin S.First-hitting times under driftTheoretical Computer Science 2019: 51–69
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, TobiasMixed 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
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
Doerr, Benjamin; Krejca, Martin S.Significance-based Estimation-of-Distribution AlgorithmsGenetic and Evolutionary Computation Conference (GECCO) 2018: 1483–1490
Kötzing, Timo; Krejca, Martin S.First-Hitting Times for Finite State SpacesParallel Problem Solving From Nature (PPSN) 2018: 79–91
Kötzing, Timo; Krejca, Martin S.First-Hitting Times Under Additive DriftParallel Problem Solving From Nature (PPSN) 2018: 92–104
Bläsius, Thomas; Eube, Jan; Feldtkeller, Thomas; Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rothenberger, Ralf; Severin, Julius; Sommer, Fabian; Trautmann, JustinMemory-restricted Routing With Tiled Map DataSystems, Man, and Cybernetics (SMC) 2018: 3347–3354
2017
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
Krejca, Martin S.; Witt, CarstenLower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMaxFoundations of Genetic Algorithms (FOGA) 2017: 65–79
2016
Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M.Robustness of Ant Colony Optimization to NoiseEvolutionary Computation 2016: 237–254
Arndt, Tobias; Hafner, Danijar; Kellermeier, Thomas; Krogmann, Simon; Razmjou, Armin; Krejca, Martin S.; Rothenberger, Ralf; Friedrich, TobiasProbabilistic Routing for On-Street Parking SearchEuropean Symposium on Algorithms (ESA) 2016: 6:1–6:13
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
Dang, Duc-Cuong; Friedrich, Tobias; Krejca, Martin S.; Kötzing, Timo; Lehre, Per Kristian; Oliveto, Pietro S.; Sudholt, Dirk; Sutton, Andrew MichaelEscaping Local Optima with Diversity Mechanisms and CrossoverGenetic and Evolutionary Computation Conference (GECCO) 2016: 645–652
Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Nallaperuma, Samadhi; Neumann, Frank; Schirneck, MartinFast Building Block Assembly by Majority Vote CrossoverGenetic and Evolutionary Computation Conference (GECCO) 2016: 661–668
Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.EDAs cannot be Balanced and StableGenetic and Evolutionary Computation Conference (GECCO) 2016: 1139–1146
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
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
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)
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