
ETH Zürich
Dr. Johannes Lengler
Inst. f. Theoretische Informatik
CAB G 37.1
Universitätstrasse 6
8092 Zürich
Phone: +41 44 632 70 53
Fax: +41 44 632 13 99
EMail:
johannes.lengler@inf.ethz.ch

Research Interests
To specialize on a very
specific scientific area is the common approach for a young scientist.
However, this potentially misses great opportunities. During my PhD I
discovered that two different mathematical communities had been working on the
same problem for more than a decade without knowing of each other. I thus
believe that it is necessary for different scientific communities to talk to
each other, and to understand the others' research and goals. My general aim
as a scientist is to help bridging the gap between different fields of
science.
During my PhD at University of Saarland with Prof. ErnstUlrich
Gekeler I worked in the intersection between number theory, algebra and
probability theory:

The CohenLenstra Heuristic for Finite Abelian Groups
PhD Thesis.

The Global CohenLenstra Heuristic
J. of Algebra, Volume 357, 247269, 2012.

Random Matrices (preprint)
(joint work with
Bernd Mehnert)
Advances in Mathematics Research.
15, 273300, 2011.

The CohenLenstra Heuristic: Methodology and Results
J. Algebra, 323(10), 2010, 29602976.

A combinatorial interpretation of the probabilities
of pgroups in the CohenLenstra measure
J. Number Theory
128, Issue 7, 20702084, 2008.
I have since then turned to several more applied areas, including
computer science and neuroscience. My greatest challenge so far was to gather
enough biological background to contribute to the neuroscience
community:

Voltage dependence of synaptic plasticity is essential for rate based learning with short stimuli
(joint work with Felix Weissenberger, Marcelo Matheus Gauy, Florian Meier, Angelika Steger)
Nature Scientific Reports, 8(1), 4609, 2018

Long synfire chains emerge by spiketiming dependent plasticity modulated by population activity (preprint)
(joint work with Felix Weissenberger, Florian Meier, Hafsteinn Einarsson, Angelika Steger)
International Journal of Neural Systems, 27(8):120, 2017

A Model of Fast Hebbian Spike Latency Normalization
(joint work with Hafsteinn Einarsson, Marcelo Matheus Gauy, Angelika Steger)
Frontiers in Computational Neuroscience, 2017

Note on the coefficient of variations of neuronal spike trains (preprint)
(joint work with Angelika Steger)
Biological Cybernetics, 2017

Randomness as a Building Block for Reproducibility
in Local Cortical Networks
In Reproducibility: Principles, Practices, Problems, eds. H. Atmanspacher and S. Maasen, Wiley, New York, 2016

A highcapacity model for one shot association learning in the brain
(joint work with Hafsteinn Einarsson, Angelika Steger)
Frontiers in Computational Neuroscience, 2014.

Reliable neuronal systems: the importance of heterogeneity
(joint work with Florian Jug, Angelika Steger)
PLoS ONE, 2013.
I also enjoy working on evolutionary (bioinspired) algorithms for discrete optimzation:

A General Dichotomy of Evolutionary Algorithms on Monotone Functions (preprint)
Parallel Problem Solving from Nature (PPSN '18), to appear

Destructiveness of Lexicographic Parsimony Pressure and Alleviation by a Concatenation Crossover in Genetic Programming (preprint)
(joint work with Timo Kötzing, Gregor Lagodzinski, Anna Melnichenko)
Parallel Problem Solving from Nature (PPSN '18), to appear

Drift Analysis and Evolutionary Algorithms Revisited (preprint)
(joint work with Angelika Steger)
Combinatorics, Probability, and Computing, to appear

Medium Step Sizes are Harmful for the Compact Genetic Algorithm
(joint work with Dirk Sudholt, Carsten Witt)
Genetic and Evolutionary Computation Conference (GECCO '18), to appear

The linear hidden subset problem for the (1+1) EA with scheduled and adaptive mutation rates
(joint work with Hafsteinn Einarsson, Marcelo Matheus Gauy, Florian Meier, Asier Mujika, Angelika Steger, Felix Weissenberger)
Genetic and Evolutionary Computation Conference (GECCO '18), to appear

Sorting by Swaps with Noisy Comparisons (preprint)
(joint work with Tomáš Gavenčiak, Barbara Geissmann)
Proceedings of the 2017 conference on Genetic and Evolutionary Computation (GECCO '17), pages 13751382, 2017

Bounding Bloat in Genetic Programming (preprint)
(joint work with Benjamin Doerr, Timo Kötzing, Gregor Lagodzinski)
Proceedings of the 2017 conference on Genetic and Evolutionary Computation (GECCO '17), pages 921928, 2017

The (1+1) Elitist BlackBox Complexity of LeadingOnes
(joint work with Carola Doerr)
Algorithmica, 2017, Volume 77(4), 125,

Introducing Elitist BlackBox Models: When Does Elitist Behavior Weaken the Performance of Evolutionary Algorithms?
(joint work with Carola Doerr)
Journal of Evolutionary Computation, 2016

The (1+1) Elitist BlackBox Complexity of LeadingOnes is Theta(n^2)
(joint work with Carola Doerr, best paper award)
Proceedings of the 2016 conference on Genetic and Evolutionary Computation (GECCO '16), 2016, 11311138

OneMax in BlackBox Models with Several Restrictions
(joint work with Carola Doerr)
Algorithmica, 2016, 131

Fixed Budget Performance of the (1+1)EA on Linear Functions
(preprint)
(joint work with Nick Spooner)
Proceedings
of Foundations of Genetic Algorithms (FOGA) XIII, 2015, 5261

OneMax in BlackBox Models With Several
Restrictions (preprint)
(joint work with Carola Doerr)
Proceedings of the 2015 conference on Genetic and Evolutionary Computation
(GECCO '15), 2015, 14311438

Elitist BlackBox Models: Analyzing the Impact of Elitist
Selection on the Performance of Evolutionary Algorithms
(preprint)
(joint work with Carola Doerr)
Proceedings
of the 2015 conference on Genetic and Evolutionary Computation (GECCO '15),
2015, 839846

Evolutionary Algorithms for Quantum Computers
(joint work with Daniel Johannsen, Piyush P Kurur)
Algorithmica,
2013, Volume 68(1), pages 152189.

BlackBox
Complexities of Combinatorial Problems (preprint of journal
version)
(joint work with Benjamin Doerr, Timo Kötzing, Carola
Winzen)
Theoretical Computer Science, 2013, Volume 471, Pages 84
106.

BlackBox Complexities of Combinatorial
Problems
(joint work with Benjamin Doerr, Timo Kötzing, Carola
Winzen)
Proc. of Genetic and Evolutionary Computation Conference (GECCO
2011), 981988, ACM, 2011.

Can Quantum Search Accelerate Evolutionary
Algorithms?
(joint work with with Daniel Johannsen, Piyush P
Kurur)
Proc. of Genetic and Evolutionary Computation Conference (GECCO 2010), 1433
1440, ACM, 2010.
Recently I started working on random graph models for large realworld networks:

Sampling Geometric Inhomogeneous Random Graphs in Linear Time
(joint work with Karl Bringmann, Ralph Keusch)
European Symposium on Algorithms (ESA 2017), pages 20:120:15, 2017.

Greedy Routing and the Algorithmic SmallWorld Phenomenom (preprint)
(joint work with Karl Bringmann, Ralph Keusch, Yannic Maus, Anisur Molla)
Principles of Distributed Computing (PODC 2017), pages 371380, 2017.

Bootstrap percolation on geometric inhomogeneous random graphs (preprint)
(joint work with Christoph Koch)
Automata, Languages, and Programming  43rd International Colloquium (ICALP 2016), 55,127:1127:15, LIPIcs, 2016.

Normalization Phenomena in Asynchronous Networks (preprint)
(joint work with Amin Karbasi, Angelika Steger)
Proc. of International Colloquium on Automata, Languages, and Programming (ICALP 2015), 2015, 688700
I have also worked on
various other topics in computer science and mathematics:

Tight Analysis for the 3Majority Consensus Dynamics (preprint)
(joint work with Mohsen Ghaffari)
Principles of Distributed Computing (PODC 2018), to appear.

Random Sampling with Removal (preprint)
(joint work with Bernd Gärtner, May Szedlak
32nd International Symposium on Computational Geometry (SoCG 2016), 51, 40:140:16, LIPIcs, 2016.

Connectivity Thresholds for Bounded Size Rules
(joint work with Hafsteinn Einarsson, Frank Mousset, Konstantinos Panagiotou, Angelika Steger)
Annals of Applied Probability, 2016, 26 (5), 32063250

The Interval Liar Game
(joint work with Benjamin Doerr, David Steurer)
Electronic Notes in Discrete Mathematics28: 425432 (2007).

The Interval Liar Game
(joint work with Benjamin Doerr, David Steurer)
International Symposium on Algorithms and Computing (ISAAC 2006), in: Lecture Notes in Computer Science 4288, 2006, 318327.

Eisensteinreihen aus arithmetischer Sicht
Diploma Thesis.

On Konsevich's Formality Theorem.
Master Thesis.
Currently I work on
 learning in cortical networks;
 bootstrap percolation (the spread of activity in social or neural networks);
 geometric inhomogeneous random graphs (to model social, technological, and neural networks).
The following papers are available as preprint and/or under review: