A picture of me.


LIX, CNRS, Ecole Polytechnique, Institut Polytechnique de Paris
1 rue Honoré d’Estienne d’Orves
91120 Palaiseau, France
Office 2139, Alan Turing building

About Me

Hi 😃! I’m a theoretical computer scientist and an assistant professor in the team for algorithms and complexity in the computer science department (LIX) of Ecole Polytechnique, which is part of Institut Polytechnique de Paris (IP Paris).

My research is driven by my desire to get to the core of things and to fully understand a problem. I’m especially intrigued by random processes where seemingly random choices accumulate in a certain, almost deter­mi­nistic trend.

A prime example for such processes are randomized search heuristics (RSHs), which act as a means for finding good solutions to optimization problems that are so badly understood that they acts as a black box to the user. RSHs typically follow a simple iterative pattern but still yield strong results for a wide range of real-world optimization problems. My aim is to provide theoretical performance guarantees for the various operations of RSHs and to thus understand which of them are useful in certain situations. In the best case, such insights lead to improved algorithms. I especially like to analyze RSHs that evolve a probabilistic model of the problem space, so called estimation-of-distribution algorithms.

Rather recently, I also gained an interest in analyzing stochastic infection processes, which model the spread of an infection in a network, in which each participant is in one of multiple states, such as being susceptible or infection. My aim is to understand for which infection rates an infection survives for a long period of time in a network and for which rates it dies out quickly.

I am also involved in a line of research that analyzes models motivated by statistical physics known as Gibbs distributions. These distributions model how likely the interaction of various particles in some space leads to certain arrangements. The aim is to efficiently sample from Gibbs distributions as well as to approximate their normalizing factor, called the partition function.

Short CV

Assistant professor at LIX, France
Postdoc at the group for Algorithm Engineering at the Hasso Plattner Institute, Germany

PhD student at the group for Algorithm Engineering at the Hasso Plattner Institute, Germany

M. Sc. student of computer science at the Friedrich Schiller University Jena, Germany
B. Sc. student of computer science at the Friedrich Schiller University Jena, Germany



I collaborated with students on various projects in cooperation with industry partners. Many of these projects involved applying heuristic algorithms to the given problem.


A list with all of my publications is on my old website. Please also refer to DBLP.

My Name

My last name gives people typically (and understandably) some trouble. Since I am usually just called Martin, this is not an issue in conversations. However, if you are interested in the pronunciation (and some background) of the name Krejca, then read on.

Origin. The name originates from Czech, where—to the best of my knowledge—it is spelled Krejča and is derived from the diminutive of the Czech word for taylor. The Czech pronunciation is 'krɛjt͡ʃa. However, my name is actually Polish, as one of my Czech ancestors apparently went to Poland. Since Polish does not have the letter č, it was changed to a simple c, which entailed that the pronunciation changed.

Actual pronunciation. In Polish, the name is pronounced 'krɛjt͡sa, with a rolled R, stressing the first syllable. Basically, it is simply pronounced the way it is spelled (if you know Polish 😉).

Adjusted pronunciations. Since not everyone has an easy time to pronounce the name properly (no shame, I am incapable to do so myself, as I cannot pronounce the rolled R!), I usually adjust the pronunciation to the target language. For English, I pronounce the first syllable (krej) like cray in crazy. I pronounce the second syllable (ca) like tsuh in what’s up. Arguably, this only mispronounces the letter R.

Fun facts. I got the name from my father, who is Polish.

In German, if one reads the name as it is spelled, there would be a decent chance of actually getting very close to the Polish pronunciation (up to the pronunciation of the R, which depends on the region). The only problem is that the letter c has two possible pronunciations, one of which is like ts, which is correct for the name, and the other one is like k, which is incorrect. Assuming that the choice is made roughly uniformly at random, this gives a chance of about 50 % of pronouncing the name correctly. However, since the spelling of the name makes it obvious that it isn’t German and since Germans tend to pronounce foreign words closely to their original pronunciation, people typically get (very) creative in how to pronounce the name. Funny enough, a fair amount of people actually ends up with the original Czech pronunciation!

In French, the name is consistently mispronounced, since the pronunciation of the letters leaves no room for interpretation, although the order of the letters is very much not French.