Publications

A First Runtime Analysis of Parallel Tempering in Quadratic Optimization

T. Paixão, J. Pérez Heredia, D. Sudholt and A. M. Sutton, "A First Runtime Analysis of Parallel Tempering in Quadratic Optimization" in Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence , Calvanese, Diego, Eds. California: International Joint Conferences on Artificial Intelligence Organization, 2026. pp. 6343-6351.

DOI: 10.24963/IJCAI.2026/706

Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima

J. Jorritsma, J. Lengler and D. Sudholt, "Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima" , Algorithmica , vol. 87, no. 12, pp. 1804-1863, 2026.

DOI: 10.1007/s00453-025-01330-y

Many-objective problems where crossover is provably essential

A. Opris, "Many-objective problems where crossover is provably essential" , Artificial Intelligence , vol. 350, pp. 104453, 2026.

DOI: 10.1016/J.ARTINT.2025.104453

On the Impact of Crossover in Many-Objective Optimization: A Runtime Analysis of NSGA-III

A. Opris, "On the Impact of Crossover in Many-Objective Optimization: A Runtime Analysis of NSGA-III" in Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence , Calvanese, Diego, Eds. California: International Joint Conferences on Artificial Intelligence Organization, 2026. pp. 6334-6342.

DOI: 10.24963/IJCAI.2026/705

Parent Selection Mechanisms in Elitist Crossover-Based Algorithms

A. Opris and D. Antipov, "Parent Selection Mechanisms in Elitist Crossover-Based Algorithms" in Proceedings of the Genetic and Evolutionary Computation Conference , Association for Computing Machinery, 2026.

DOI: 10.1145/3795095.3805131

Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions

D. Dang, R. Kalkreuth and A. Opris, "Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions" in Parallel Problem Solving from Nature - PPSN XIX , Iacca, Giovanni and Nadizar, Giorgia and Yaman, Anil and Bucur, Doina and Della Cioppa, Antonio and Hu, Ting and Medvet, Eric and Thomson, Sarah L., Eds. Cham: Springer Nature Switzerland, 2026, pp. 163-179.

DOI: 10.1007/978-3-032-36214-8_11

Runtime Analysis of Cartesian Genetic Programming on MAX: A Proven Exponential Speedup

D. Dang, R. Kalkreuth and A. Opris, "Runtime Analysis of Cartesian Genetic Programming on MAX: A Proven Exponential Speedup" in Proceedings of Advances in Neural Information Processing Systems (NeurIPS 2026) , 2026, pp. 382-399.

DOI: 10.1007/978-3-032-36223-0_24

Runtime Analysis of Functions where Widely Used Evolutionary Multi-Objective Algorithms Beat Simple Ones

D. Dang, A. Opris and D. Sudholt, "Runtime Analysis of Functions where Widely Used Evolutionary Multi-Objective Algorithms Beat Simple Ones" , ACM Transactions on Evolutionary Learning and Optimization , vol. 6, no. 2, pp. 1-33, 2026.

DOI: 10.1145/3732793

The SLO Hierarchy of Pseudo-Boolean Functions and Runtime of Evolutionary Algorithms

D. Dang and P. K. Lehre, "The SLO Hierarchy of Pseudo-Boolean Functions and Runtime of Evolutionary Algorithms" , Algorithmica , vol. 88, no. 2, pp. 32, 2026.

DOI: 10.1007/S00453-025-01359-Z

Theory and Practice of Population Diversity in Evolutionary Computation

D. Sudholt and G. Squillero, "Theory and Practice of Population Diversity in Evolutionary Computation" in Proceedings of the Genetic and Evolutionary Computation Conference Companion , Trujillo, Leonardo and Hu, Ting, Eds. New York, NY, USA: ACM, 2026. pp. 978-997.

DOI: 10.1145/3795101.3807759

Tight Runtime Bounds for Evolutionary Algorithms on Sorting and Crossing Minimisation for Layered Graph Drawings

J. Baumann, I. Rutter and D. Sudholt, "Tight Runtime Bounds for Evolutionary Algorithms on Sorting and Crossing Minimisation for Layered Graph Drawings" , Algorithmica , vol. 88, no. 3, 2026.

DOI: 10.1007/S00453-025-01361-5

Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds

A. Opris, "Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds" , Proceedings of the AAAI Conference on Artificial Intelligence , vol. 40, no. 43, pp. 37125-37133, 2026.

DOI: 10.1609/AAAI.V40I43.41042

A First Runtime Analysis of NSGA-III on a Many-Objective Multimodal Problem: Provable Exponential Speedup via Stochastic Population Update

A. Opris, "A First Runtime Analysis of NSGA-III on a Many-Objective Multimodal Problem: Provable Exponential Speedup via Stochastic Population Update" in Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence , Kwok, James and Zilberstein, Shlomo, Eds. California: International Joint Conferences on Artificial Intelligence Organization, 2025. pp. 8903-8911.

DOI: 10.24963/ijcai.2025/990

ISBN: 978-1-956792-06-5

A First Runtime Analysis of the PAES-25: An Enhanced Variant of the Pareto Archived Evolution Strategy

A. Opris, "A First Runtime Analysis of the PAES-25: An Enhanced Variant of the Pareto Archived Evolution Strategy" in Proceedings of the Foundations of Genetic Algorithms XVIII on ZZZ , Filipic, Bogdan and Ochoa, Gabriela, Eds. New York, NY, USA: ACM, 2025. pp. 202-213.

DOI: 10.1145/3729878.3746618

ISBN: 9798400718595

A Many-Objective Problem Where Crossover is Provably Indispensable

A. Opris, "A Many-Objective Problem Where Crossover is Provably Indispensable" in Proceedings of the Genetic and Evolutionary Computation Conference Companion , Filipič, Bogdan and Ochoa, Gabriela, Eds. New York, NY, USA: ACM, 2025. pp. 49-50.

DOI: 10.1145/3712255.3734223

ISBN: 9798400714641

A Many-Objective Problem Where Crossover Is Provably Indispensable

A. Opris, "A Many-Objective Problem Where Crossover Is Provably Indispensable" , Proceedings of the AAAI Conference on Artificial Intelligence , vol. 39, no. 25, pp. 27108-27116, 2025. ACM.

DOI: 10.1609/aaai.v39i25.34918

ISBN: 9798400714641

A Royal Road Function for Permutation Spaces: an Example Where Order Crossover is Provably Essential

A. Opris, S. Sonntag and D. Sudholt, "A Royal Road Function for Permutation Spaces: an Example Where Order Crossover is Provably Essential" in Proceedings of the Genetic and Evolutionary Computation Conference , Filipic, Bogdan and Ochoa, Gabriela, Eds. New York, NY, USA: ACM, 2025. pp. 1631-1640.

DOI: 10.1145/3712256.3726403

ISBN: 9798400714658

Achieving Tight Runtime Bounds on Jumpk by Proving that Genetic Algorithms Evolve Near-Maximal Population Diversity

A. Opris, J. Lengler and D. Sudholt, "Achieving Tight Runtime Bounds on Jumpk by Proving that Genetic Algorithms Evolve Near-Maximal Population Diversity" , Algorithmica , no. 11, pp. 1564-1619, 2025. ACM.

DOI: 10.1007/s00453-025-01323-x

ISBN: 9798400718595

Analysing the Effectiveness of Mutation Operators for One-Sided Bipartite Crossing Minimisation

J. Baumann, I. Rutter and D. Sudholt, "Analysing the Effectiveness of Mutation Operators for One-Sided Bipartite Crossing Minimisation" in Proceedings of the Genetic and Evolutionary Computation Conference , Filipic, Bogdan and Ochoa, Gabriela, Eds. New York, NY, USA: ACM, 2025. pp. 872-880.

DOI: 10.1145/3712256.3726407

ISBN: 9798400714658

Empirical Linkage Learning Provably Builds Truthful Models on Concatenated Traps and H-IFF

M. Schmidbauer and D. Sudholt, "Empirical Linkage Learning Provably Builds Truthful Models on Concatenated Traps and H-IFF" in Proceedings of the Genetic and Evolutionary Computation Conference , Filipic, Bogdan and Ochoa, Gabriela, Eds. New York, NY, USA: ACM, 2025. pp. 827-835.

DOI: 10.1145/3712256.3726417

ISBN: 9798400714658

Runtime Analysis of Functions Where Widely-Used Evolutionary Multi-Objective Algorithms Beat Simple Ones

D. Dang, A. Opris and D. Sudholt, "Runtime Analysis of Functions Where Widely-Used Evolutionary Multi-Objective Algorithms Beat Simple Ones" , ACM Transactions on Evolutionary Learning and Optimization , pp. 1604-1612, 2025. ACM.

DOI: 10.1145/3732793

ISBN: 9798400714658

The Compact Genetic Algorithm Struggles on Cliff Functions

F. Neumann, D. Sudholt and C. Witt, "The Compact Genetic Algorithm Struggles on Cliff Functions" , Algorithmica , vol. 87, no. 4, pp. 507-536, 2025.

DOI: 10.1007/S00453-024-01281-W

Theoretical Analysis of Evolutionary Algorithms with Quality Diversity for a Classical Path Planning Problem

D. Dang, A. Neumann, F. Neumann, A. Opris and D. Sudholt, "Theoretical Analysis of Evolutionary Algorithms with Quality Diversity for a Classical Path Planning Problem" in Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence , Kwok, James and Zilberstein, Shlomo, Eds. California: International Joint Conferences on Artificial Intelligence Organization, 2025. pp. 8858-8866.

DOI: 10.24963/ijcai.2025/985

ISBN: 978-1-956792-06-5

Theory and Practice of Population Diversity in Evolutionary Computation

D. Sudholt and G. Squillero, "Theory and Practice of Population Diversity in Evolutionary Computation" in Proceedings of the Genetic and Evolutionary Computation Conference Companion , Filipič, Bogdan and Ochoa, Gabriela, Eds. New York, NY, USA: ACM, 2025. pp. 1643-1662.

DOI: 10.1145/3712255.3716510

Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm

B. Doerr, M. S. Krejca and A. Opris, "Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm" in Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence , Kwok, James and Zilberstein, Shlomo, Eds. California: International Joint Conferences on Artificial Intelligence Organization, 2025. pp. 8876-8884.

DOI: 10.24963/ijcai.2025/987

ISBN: 978-1-956792-06-5