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 (Kopie 1)

2023 [ to top ]

- Bläsius, Thomas; Friedrich, Tobias; Krejca, Martin S.; Molitor, Louise
**The Impact of Geometry on Monochrome Regions in the Flip Schelling Process**Computational Geometry (CGTA) 2023: 101902 - Böther, Maximilian; Schiller, Leon; Fischbeck, Philipp; Molitor, Louise; Krejca, Martin S.; Friedrich, Tobias
**Evolutionary Minimization of Traffic Congestion**IEEE Transactions on Evolutionary Computation 2023 - Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, Marcus
**Polymer Dynamics via Cliques: New Conditions for Approximations**Theoretical Computer Science 2023: 230–252 - Doerr, Benjamin; Krejca, Martin S.
**Bivariate estimation-of-distribution algorithms can find an exponential number of optima**Theoretical Computer Science 2023: 114074.1–114074.16 - Ben Jedidia, Firas; Doerr, Benjamin; Krejca, Martin S.
**Estimation-of-Distribution Algorithms for Multi-Valued Decision Variables**Genetic and Evolutionary Computation Conference (GECCO) 2023: 230–238 - Cohen, Sarel; Fischbeck, Philipp; Friedrich, Tobias; Krejca, Martin S.
**The Common-Neighbors Metric is Noise-Robust and Reveals Substructures of Real-World Networks**Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD) 2023: 67–79

2022 [ to top ]

- Doerr, Carola; Krejca, Martin S.
**Run Time Analysis for Random Local Search on Generalized Majority Functions**IEEE Transactions on Evolutionary Computation 2022 - Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, Marcus
**A Spectral Independence View on Hard Spheres via Block Dynamics**SIAM 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 discretization**International Computing and Combinatorics Conference (COCOON) 2022: 242–254 - Biedenkapp, André; Dang, Nguyên; Krejca, Martin S.; Hutter, Frank; Doerr, Carola
**Theory-inspired Parameter Control Benchmarks for Dynamic Algorithm Configuration**Genetic and Evolutionary Computation Conference (GECCO) 2022: 766–775Best-Paper Award (GECH Track) - Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Rajabi, Amirhossein
**Escaping Local Optima With Local Search: A Theory-Driven Discussion**Parallel Problem Solving from Nature (PPSN) 2022: 442–455Best Paper Award and Best Poster Award - Cohen, Sarel; Fischbeck, Philipp; Friedrich, Tobias; Krejca, Martin S.; Sauerwald, Thomas
**Accelerated Information Dissemination on Networks with Local and Global Edges**Structural Information and Communication Complexity (SIROCCO) 2022: 79–97

2021 [ to top ]

- Doerr, Benjamin; Krejca, Martin S.
**A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes**Theoretical Computer Science 2021: 121–128 - Böther, Maximilian; Schiller, Leon; Fischbeck, Philipp; Molitor, Louise; Krejca, Martin S.; Friedrich, Tobias
**Evolutionary Minimization of Traffic Congestion**Genetic and Evolutionary Computation Conference (GECCO) 2021: 937–945Best-Paper Award (RWA Track) - Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, Marcus
**A spectral independence view on hard spheres via block dynamics**International Colloquium on Automata, Languages and Programming (ICALP) 2021: 66:1–66:15 - Bläsius, Thomas; Friedrich, Tobias; Krejca, Martin S.; Molitor, Louise
**The Impact of Geometry on Monochrome Regions in the Flip Schelling Process**International Symposium on Algorithms and Computation, (ISAAC) 2021 2021: 29:1–29:17

2020 [ to top ]

- Doerr, Benjamin; Krejca, Martin S.
**Significance-based Estimation-of-Distribution Algorithms**IEEE Transactions on Evolutionary Computation 2020: 1025–1034 - Krejca, Martin S.; Witt, Carsten
**Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax**Theoretical Computer Science 2020: 143–165 - Krejca, Martin S.; Witt, Carsten
**Theory of Estimation-of-Distribution Algorithms**Theory 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 Epistasis**Evolutionary Computation in Combinatorial Optimisation (EvoCOP) 2020: 51–66Best-Paper Award - Doerr, Benjamin; Krejca, Martin S.
**Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of Optima**Genetic and Evolutionary Computation Conference (GECCO) 2020: 796–804 - Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rizzo, Manuel; Zahn, Arthur
**Memetic Genetic Algorithms for Time Series Compression by Piecewise Linear Approximation**International Conference on Neural Information Processing (ICONIP) 2020: 592–604

2019 [ to top ]

- 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 Data**AI Communications 2019: 113–124 - Trubenova, Barbora; Kötzing, Timo; Krejca, Martin S.; Lehre, Per Kristian
**Surfing on the seascape: Adaptation in a changing environment**Evolution: International Journal of Organic Evolution 2019: 1356–1374 - Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.
**Unbiasedness of Estimation-of-Distribution Algorithms**Theoretical Computer Science 2019: 46–59 - Kötzing, Timo; Krejca, Martin S.
**First-hitting times under drift**Theoretical 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, Tobias
**Mixed Integer Programming versus Evolutionary Computation for Optimizing a Hard Real-World Staff Assignment Problem**International Conference on Automated Planning and Scheduling (ICAPS) 2019: 541–554

2018 [ to top ]

- 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 Diversity**IEEE Transactions on Evolutionary Computation 2018: 484–497 - Doerr, Benjamin; Krejca, Martin S.
**Significance-based Estimation-of-Distribution Algorithms**Genetic and Evolutionary Computation Conference (GECCO) 2018: 1483–1490 - Kötzing, Timo; Krejca, Martin S.
**First-Hitting Times for Finite State Spaces**Parallel Problem Solving From Nature (PPSN) 2018: 79–91 - Kötzing, Timo; Krejca, Martin S.
**First-Hitting Times Under Additive Drift**Parallel 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, Justin
**Memory-restricted Routing With Tiled Map Data**Systems, Man, and Cybernetics (SMC) 2018: 3347–3354

2017 [ to top ]

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

2016 [ to top ]

- Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M.
**Robustness of Ant Colony Optimization to Noise**Evolutionary Computation 2016: 237–254 - Arndt, Tobias; Hafner, Danijar; Kellermeier, Thomas; Krogmann, Simon; Razmjou, Armin; Krejca, Martin S.; Rothenberger, Ralf; Friedrich, Tobias
**Probabilistic Routing for On-Street Parking Search**European 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 Search**Genetic 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 Michael
**Escaping Local Optima with Diversity Mechanisms and Crossover**Genetic and Evolutionary Computation Conference (GECCO) 2016: 645–652 - Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Nallaperuma, Samadhi; Neumann, Frank; Schirneck, Martin
**Fast Building Block Assembly by Majority Vote Crossover**Genetic and Evolutionary Computation Conference (GECCO) 2016: 661–668 - Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.
**EDAs cannot be Balanced and Stable**Genetic 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 Noise**Parallel 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 Algorithms**Parallel Problem Solving From Nature (PPSN) 2016: 890–900

2015 [ to top ]

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

# Publications

2023 [ to top ]

- Bläsius, Thomas; Friedrich, Tobias; Krejca, Martin S.; Molitor, Louise
**The Impact of Geometry on Monochrome Regions in the Flip Schelling Process**Computational Geometry (CGTA) 2023: 101902 - Böther, Maximilian; Schiller, Leon; Fischbeck, Philipp; Molitor, Louise; Krejca, Martin S.; Friedrich, Tobias
**Evolutionary Minimization of Traffic Congestion**IEEE Transactions on Evolutionary Computation 2023 - Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, Marcus
**Polymer Dynamics via Cliques: New Conditions for Approximations**Theoretical Computer Science 2023: 230–252 - Doerr, Benjamin; Krejca, Martin S.
**Bivariate estimation-of-distribution algorithms can find an exponential number of optima**Theoretical Computer Science 2023: 114074.1–114074.16 - Ben Jedidia, Firas; Doerr, Benjamin; Krejca, Martin S.
**Estimation-of-Distribution Algorithms for Multi-Valued Decision Variables**Genetic and Evolutionary Computation Conference (GECCO) 2023: 230–238 - Cohen, Sarel; Fischbeck, Philipp; Friedrich, Tobias; Krejca, Martin S.
**The Common-Neighbors Metric is Noise-Robust and Reveals Substructures of Real-World Networks**Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD) 2023: 67–79

2022 [ to top ]

- Doerr, Carola; Krejca, Martin S.
**Run Time Analysis for Random Local Search on Generalized Majority Functions**IEEE Transactions on Evolutionary Computation 2022 - Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, Marcus
**A Spectral Independence View on Hard Spheres via Block Dynamics**SIAM 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 discretization**International Computing and Combinatorics Conference (COCOON) 2022: 242–254 - Biedenkapp, André; Dang, Nguyên; Krejca, Martin S.; Hutter, Frank; Doerr, Carola
**Theory-inspired Parameter Control Benchmarks for Dynamic Algorithm Configuration**Genetic and Evolutionary Computation Conference (GECCO) 2022: 766–775Best-Paper Award (GECH Track) - Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Rajabi, Amirhossein
**Escaping Local Optima With Local Search: A Theory-Driven Discussion**Parallel Problem Solving from Nature (PPSN) 2022: 442–455Best Paper Award and Best Poster Award - Cohen, Sarel; Fischbeck, Philipp; Friedrich, Tobias; Krejca, Martin S.; Sauerwald, Thomas
**Accelerated Information Dissemination on Networks with Local and Global Edges**Structural Information and Communication Complexity (SIROCCO) 2022: 79–97

2021 [ to top ]

- Doerr, Benjamin; Krejca, Martin S.
**A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes**Theoretical Computer Science 2021: 121–128 - Böther, Maximilian; Schiller, Leon; Fischbeck, Philipp; Molitor, Louise; Krejca, Martin S.; Friedrich, Tobias
**Evolutionary Minimization of Traffic Congestion**Genetic and Evolutionary Computation Conference (GECCO) 2021: 937–945Best-Paper Award (RWA Track) - Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, Marcus
**A spectral independence view on hard spheres via block dynamics**International Colloquium on Automata, Languages and Programming (ICALP) 2021: 66:1–66:15 - Bläsius, Thomas; Friedrich, Tobias; Krejca, Martin S.; Molitor, Louise
**The Impact of Geometry on Monochrome Regions in the Flip Schelling Process**International Symposium on Algorithms and Computation, (ISAAC) 2021 2021: 29:1–29:17

2020 [ to top ]

- Doerr, Benjamin; Krejca, Martin S.
**Significance-based Estimation-of-Distribution Algorithms**IEEE Transactions on Evolutionary Computation 2020: 1025–1034 - Krejca, Martin S.; Witt, Carsten
**Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax**Theoretical Computer Science 2020: 143–165 - Krejca, Martin S.; Witt, Carsten
**Theory of Estimation-of-Distribution Algorithms**Theory 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 Epistasis**Evolutionary Computation in Combinatorial Optimisation (EvoCOP) 2020: 51–66Best-Paper Award - Doerr, Benjamin; Krejca, Martin S.
**Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of Optima**Genetic and Evolutionary Computation Conference (GECCO) 2020: 796–804 - Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rizzo, Manuel; Zahn, Arthur
**Memetic Genetic Algorithms for Time Series Compression by Piecewise Linear Approximation**International Conference on Neural Information Processing (ICONIP) 2020: 592–604

2019 [ to top ]

- 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 Data**AI Communications 2019: 113–124 - Trubenova, Barbora; Kötzing, Timo; Krejca, Martin S.; Lehre, Per Kristian
**Surfing on the seascape: Adaptation in a changing environment**Evolution: International Journal of Organic Evolution 2019: 1356–1374 - Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.
**Unbiasedness of Estimation-of-Distribution Algorithms**Theoretical Computer Science 2019: 46–59 - Kötzing, Timo; Krejca, Martin S.
**First-hitting times under drift**Theoretical 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, Tobias
**Mixed Integer Programming versus Evolutionary Computation for Optimizing a Hard Real-World Staff Assignment Problem**International Conference on Automated Planning and Scheduling (ICAPS) 2019: 541–554

2018 [ to top ]

- 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 Diversity**IEEE Transactions on Evolutionary Computation 2018: 484–497 - Doerr, Benjamin; Krejca, Martin S.
**Significance-based Estimation-of-Distribution Algorithms**Genetic and Evolutionary Computation Conference (GECCO) 2018: 1483–1490 - Kötzing, Timo; Krejca, Martin S.
**First-Hitting Times for Finite State Spaces**Parallel Problem Solving From Nature (PPSN) 2018: 79–91 - Kötzing, Timo; Krejca, Martin S.
**First-Hitting Times Under Additive Drift**Parallel 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, Justin
**Memory-restricted Routing With Tiled Map Data**Systems, Man, and Cybernetics (SMC) 2018: 3347–3354

2017 [ to top ]

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

2016 [ to top ]

- Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Sutton, Andrew M.
**Robustness of Ant Colony Optimization to Noise**Evolutionary Computation 2016: 237–254 - Arndt, Tobias; Hafner, Danijar; Kellermeier, Thomas; Krogmann, Simon; Razmjou, Armin; Krejca, Martin S.; Rothenberger, Ralf; Friedrich, Tobias
**Probabilistic Routing for On-Street Parking Search**European 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 Search**Genetic 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 Michael
**Escaping Local Optima with Diversity Mechanisms and Crossover**Genetic and Evolutionary Computation Conference (GECCO) 2016: 645–652 - Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Nallaperuma, Samadhi; Neumann, Frank; Schirneck, Martin
**Fast Building Block Assembly by Majority Vote Crossover**Genetic and Evolutionary Computation Conference (GECCO) 2016: 661–668 - Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.
**EDAs cannot be Balanced and Stable**Genetic 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 Noise**Parallel 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 Algorithms**Parallel Problem Solving From Nature (PPSN) 2016: 890–900

2015 [ to top ]

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