Dr. Andrew M. Sutton

Associate Professor Department of Computer Science University of Minnesota Duluth 311 Heller Hall 1114 Kirby Drive Duluth, MN 55812 Email: amsutton [at] d.umn.edu Telephone: +1 218.726.7978 Public key: PGP

Research

My research interests include: theory of randomized search heuristics, theory of evolutionary computation, parameterized complexity, randomized algorithms, graph theory.

Activities

Associate Professor with tenure (since August 2023) in the Department of Computer Science at the University of Minnesota Duluth.

Awarded an NSF CAREER grant for research in Algorithmic Models of Adaptation.

Co-organized with Christine Zarges the Autumn 2022 ThRaSH seminar.

Theory track chair for GECCO 2021 and GECCO 2022.

Executive Board Member of ACM SIGEVO (elected 2021).

My student Luke Branson and I authored the paper Focused Jump-and-Repair Constraint Handling for Fixed-Parameter Tractable Graph Problems, which was awarded Best Paper at the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms.

I was previously affiliated with the Algorithm Engineering Group at the Hasso Plattner Institute in Potsdam, Germany. My research there was supported by the SAGE Project, funded by the European Commission FP7 ICT FET Open Scheme. I have also held postdoctoral appointments in the Chair of Theoretical Computer Science Ⅰ at Friedrich-Schiller-Universität in Jena, Germany and in the School of Computer Science at the University of Adelaide in Adelaide, South Australia.

Teaching

• Advanced Algorithms and Data Structures
• Theory of Automata and Formal Languages
• Artificial Intelligence
• Nature-Inspired Algorithms [2017 @Hasso Plattner Institute]
• Heuristic Optimization [2016, 2015 @Hasso Plattner Institute]
• Foundations of Computer Science [2009 @Colorado State University]

Publications

Editorial Work

• P. S. Oliveto and A. M. Sutton. Special Issue on Theory of Evolutionary Computation, Theoretical Computer Science, Volume 832 (2020) Elsevier, 186 pages. [link]
• T. Friedrich, F. Neumann, A. M. Sutton. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) 2016, ACM Press, 1174 pages. [link]
• T. Friedrich, F. Neumann, A. M. Sutton. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) 2016, Companion, ACM Press, 1482 pages.
• P. S. Oliveto and A. M. Sutton. Special Issue on Theory of Evolutionary Algorithms 2014, Evolutionary Computation 23:4 (2015) MIT Press. [link]

Journal Articles

• L. Branson and A. M. Sutton. Focused Jump-and-Repair Constraint Handling for Fixed-Parameter Tractable Graph Problems Closed Under Induced Subgraphs. Theoretical Computer Science, 951 (2023). [link]
• P. Sankineni and A. M. Sutton. Symmetry Breaking for Voting Mechanisms. Evolutionary Computation Journal, (2023). [link]
• A. M. Sutton. Fixed-Parameter Tractability of Crossover: Steady-State GAs on the Closest String Problem. Algorithmica, 83 (2021) pp. 1138-1163. [link]
• A. M. Sutton and C. Witt. Lower Bounds on the Runtime of Crossover-Based Algorithms via Decoupling and Family Graphs. Algorithmica, (2020). [link]
• D.-C. Dang, T. Friedrich, T. Kötzing, M. S. Krejca, P. K. Lehre, P. S. Oliveto, D. Sudholt, and A. M. Sutton. Escaping Local Optima Using Crossover with Emergent Diversity. IEEE Transactions on Evolutionary Computation, 22:3 (2018) pp. 484-497. [link] [arXiv]
• T. Friedrich, T. Kötzing, M. S. Krejca, and A. M. Sutton. The Compact Genetic Algorithm is Efficient under Extreme Gaussian Noise. IEEE Transactions in Evolutionary Computation, 21:3 (2017), pp. 477-490. [link]
• B. Doerr, F. Neumann, and A. M. Sutton. Time Complexity Analysis of Evolutionary Algorithms on Random Satisfiable k-CNF Formulas. Algorithmica, 78:2 (2017), pp. 561-586. [link]
• A. M. Sutton. Superpolynomial Lower Bounds for the (1+1) EA on Some Easy Combinatorial Problems, Algorithmica, 75:3 (2016), pp. 507-528. [link]
• T. Paixão, G. Badkobeh, N. H. Barton, D. Çörüş, D.-C. Dang, T. Friedrich, P. K. Lehre, D. Sudholt, A. M. Sutton, B. Trubenová. Toward a unifying framework for evolutionary processes. Journal of Theoretical Biology 383 (2015), pp. 28-43. [link]
• A. Q. Nguyen, A. M. Sutton, and F. Neumann. Population size matters: Rigorous runtime results for maximizing the hypervolume indicator. Theoretical Computer Science 561 (2015), pp. 24-36. [link]
• F. Chicano, A. M. Sutton, L. D. Whitley, and E. Alba. Fitness Probability Distribution of Bit-Flip Mutation. Evolutionary Computation 23:2 (2015), pp. 217-248. [link]
• A. M. Sutton, F. Neumann, and S. Nallaperuma. Parameterized Runtime Analyses of Evolutionary Algorithms for the Planar Euclidean Traveling Salesperson Problem, Evolutionary Computation 22:4 (2014), pp. 595-628. [link]
• T. Kötzing, A. M. Sutton, F. Neumann, and U.-M. O'Reilly. The Max Problem Revisited: The Importance of Mutation in Genetic Programming, Theoretical Computer Science 545 (2014), pp. 94-107. [link]
• A. M. Sutton, F. Chicano, and L. D. Whitley, Fitness Function Distributions over Generalized Search Neighborhoods in the q-ary Hypercube, Evolutionary Computation 21:4 (2013), pp. 561-590. [link]
• A. M. Sutton, L. D. Whitley, and A. E. Howe, Computing the moments of k-bounded pseudo-Boolean functions over Hamming spheres of arbitrary radius in polynomial time, Theoretical Computer Science 425 (2012), pp. 58-74. [link]

Refereed Conference Proceedings

• J. Kearney, F. Neumann, and A. M. Sutton. Fixed-Parameter Tractability of the (1+1) Evolutionary Algorithm on Random Planted Vertex Covers. In Proceedings of the Seventeenth ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA XVII), Potsdam, Germany, August 2023.
• L. Branson, A. M. Sutton, and Xiankun Yan. Finding Antimagic Labelings of Trees by Evolutionary Search. In Proceedings of the Seventeenth ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA XVII), Potsdam, Germany, August 2023.
• P. K. Lehre and A. M. Sutton. Runtime Analysis with Variable Cost. In Proceedings of the 2023 Genetic and Evolutionary Computation Conference (GECCO 2023), Lisbon, Portugal, July 2023.
• B. Aboutaib and A. M. Sutton. Runtime analysis of unbalanced block-parallel evolutionary algorithms. In Proceedings of the Seventeenth International Conference on Parallel Problem Solving from Nature (PPSN 2022), Dortmund, Germany, September 2022.
• B. Aboutaib and A. M. Sutton. The Influence of Noise on Multi-Parent Crossover for an Island Model GA. In Proceedings of the 2022 Genetic and Evolutionary Computation Conference (GECCO 2022), Boston, USA, July 2022. [Best Paper Nomination]
• L. Branson and A. M. Sutton. Evolving Labelings of Graceful Graphs. In Proceedings of the 2022 Genetic and Evolutionary Computation Conference (GECCO 2022), Boston, USA, July 2022.
• L. Branson and A. M. Sutton. Focused Jump-and-Repair Constraint Handling for Fixed-Parameter Tractable Graph Problems. In Proceedings of the 16th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA 2021), Dornbirn, Austria, September 2021. [link] [Best Paper Award]
• T. Friedrich, F. Neumann, R. Rothenberger, and A. M. Sutton. Solving Non-Uniform Planted and Filtered Random SAT Formulas Greedily. In Proceedings of the Twenty-Fourth International Conference on Theory and Applications of Satisfiability Testing (SAT-2021), Lecture Notes in Computer Science, vol 12831, Virtual Event, July 2021. [link]
• Y. Xie, A. Neumann, F. Neumann, and A. M. Sutton. Runtime Analysis of RLS and the (1+1) EA for the Chance-constrained Knapsack Problem with Correlated Uniform Weights. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-21), Virtual Event, June 2021. [link]
• P. Sankineni and A. M. Sutton. Symmetry Breaking for Voting Mechanisms. In Proceedings of the Twenty-First European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP-21), Lecture Notes in Computer Science, vol 12692, Virtual Event, April 2021. [link] [Best Paper Nomination]
• B. Doerr, C, Doerr, A. Neumann, F. Neumann, and A. M. Sutton. Optimization of Chance-Constrained Submodular Functions. In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI-20), New York, NY, February 2020. [CoRR abs/1911.11451] [link]
• A. M. Sutton and D. Whitley. Approximation Speed-Up by Quadratization on LeadingOnes. In Proceedings of the Sixteenth International Conference on Parallel Problem Solving from Nature (PPSN2020), Leiden, Netherlands, September 2020. [link]
• D. Whitley, H. Aguirre and A. M. Sutton. Understanding Transforms of Pseudo-Boolean Functions. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-20), Cancun, Mexico, July 2020. [link]
  [Best Paper Award - GA Track]
• F. Neumann and A. M. Sutton. Runtime Analysis of the (1+1) Evolutionary Algorithm for the Chance-Constrained Knapsack Problem. In Proceedings of the 15th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA-XV), Potsdam, Germany, August 2019. [link]
• A. M. Sutton and Carsten Witt. Lower Bounds on the Runtime of Crossover-Based Algorithms via Decoupling and Family Graphs. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-19), Prague, Czech Republic, July 2019. [link]
• B. Doerr and A. M. Sutton. When Resampling to Cope With Noise, Use Median, Not Mean. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-19), Prague, Czech Republic, July 2019. [link]
• F. Neumann and A. M. Sutton. Evolving Solutions to Community-Structured Satisfiability Formulas. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19), Honolulu, HI, USA, January 2019. [link]
• A. M. Sutton. Crossover Can Simulate Bounded Tree Search on a Fixed-Parameter Tractable Optimization Problem. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-18), Kyoto, Japan, July 2018. [link]
• V. Hasenöhrl and A. M. Sutton. On the Runtime Dynamics of the Compact Genetic Algorithm on Jump Functions. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-18), Kyoto, Japan, July 2018. [link]
• T. Friedrich, T. Kötzing, F. Quinzan and A. M. Sutton. Improving the Run Time of the (1+1) Evolutionary Algorithm with Luby Sequences. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-18), Kyoto, Japan, July 2018. [link]
• F. Neumann and A. M. Sutton. Runtime Analysis of Evolutionary Algorithms for the Knapsack Problem with Favorably Correlated Weights. Proceedings of the Fifteenth International Conference on Parallel Problem Solving from Nature (PPSN XV), Coimbra, Portugal, September, 2018. [link]
• T. Friedrich, A. Krohmer, R. Rothenberger, T. Sauerwald, A. M. Sutton. Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT. European Symposium on Algorithms (ESA 2017) [link]
• T. Friedrich, A. Krohmer, R. Rothenberger, A. M. Sutton. Phase Transitions for Scale-Free SAT Formulas. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI 2017), San Francisco, CA, USA, February 2017. [link]
• T. Friedrich, T. Kötzing, F. Quinzan, and A. M. Sutton. Resampling vs Recombination: a Statistical Run Time Estimation. In Proceedings of the Fourteenth ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA), Copenhagen, Denmark, January 2017. [link]
• T. Friedrich, T. Kötzing, and A. M. Sutton. On the Robustness of Evolving Populations. In Proceedings of the 14th International Conference on Parallel Problem Solving from Nature (PPSN2016), Edinburgh, Scotland, September 2016. [link]
• T. Friedrich, T. Kötzing, M. S. Krejca, and A. M. Sutton. Graceful Scaling on Uniform versus Steep-Tailed Noise. In Proceedings of the 14th International Conference on Parallel Problem Solving from Nature (PPSN2016), Edinburgh, Scotland, September 2016. [link]
• D.-C. Dang, T. Friedrich, T. Kötzing, M. S. Krejca, P. K. Lehre, P. S. Oliveto, D. Sudholt, and A. M. Sutton. Emergence of Diversity and its Benefits for Crossover in Genetic Algorithms. In Proceedings of the 14th International Conference on Parallel Problem Solving from Nature (PPSN2016), Edinburgh, Scotland, September 2016. [link]
• D.-C. Dang, T. Friedrich, T. Kötzing, M. S. Krejca, P. K. Lehre, P. S. Oliveto, D. Sudholt, and A. M. Sutton. Escaping Local Optima with Diversity Mechanisms and Crossover. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-16), Denver, CO, USA, July 2016. [link]
• T. Friedrich, T. Kötzing, M. S. Krejca, and A. M. Sutton. The Benefit of Recombination in Noisy Evolutionary Search. In Proceedings of the Twenty-Sixth International Symposium on Algorithms and Computation (ISAAC 2015), Nagoya, Japan, December 2015. [link]
• B. Doerr, F. Neumann, and A. M. Sutton. Improved Runtime Bounds for the (1+1) EA on Random 3-CNF Formulas Based on Fitness-Distance Correlation. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-15), Madrid, Spain, July 2015. [link]
  [Best Paper Award - Theory Track]
• T. Friedrich, T. Kötzing, M. S. Krejca, and A. M. Sutton. Robustness of ACO against Gaussian Noise, In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-15), Madrid, Spain, July 2015. [link]
  [Best Paper Award - ACO/SI Track]
• A. M. Sutton. Superpolynomial Lower Bounds for the (1+1) EA on Some Easy Combinatorial Problems, In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-14), Vancouver, Canada, July 2014. [link]
• F. Chicano, D. Whitley, and A. M. Sutton. Efficient Identification of Improving Moves in a Ball for Pseudo-Boolean Problems, In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-14), Vancouver, Canada, July 2014.[link]
• A. M. Sutton and F. Neumann. Runtime Analysis of Evolutionary Algorithms on Randomly Constructed High-Density Satisfiable 3-CNF Formulas, In Proceedings of the Thirteenth International Conference on Parallel Problem Solving from Nature (PPSN XIII), Ljubljana, Slovenia, September 2014. Published in Lecture Notes in Computer Science Vol. 8672, (2014) pp. 942-951. [link]
• A. Q. Nguyen, A. M. Sutton, and F. Neumann. Population Size Matters: Rigorous Runtime Results for Maximizing the Hypervolume Indicator, In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-13), Amsterdam, The Netherlands, July 2013. [link]
• S. Nallaperuma, A. M. Sutton, and F. Neumann. Fixed-parameter evolutionary algorithms for the Euclidean traveling salesperson problem, In Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2013), Cancún, México, June 2013. [link]
• S. Nallaperuma, A. M. Sutton, and F. Neumann. Parameterized complexity analysis and more effective construction methods for ACO algorithms and the Euclidean traveling salesperson problem, In Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2013), Cancún, México, June 2013. [link]
• A. M. Sutton and F. Neumann. A Parameterized Runtime Analysis of Simple Evolutionary Algorithms for Makespan Scheduling, In Proceedings of the Twelfth International Conference on Parallel Problem Solving from Nature (PPSN XII), Taormina, Italy, September 2012. Published in Lecture Notes in Computer Science Vol. 7491, (2012) pp. 52-61. [link]
• A. M. Sutton and F. Neumann. A Parameterized Runtime Analysis of Evolutionary Algorithms for the Euclidean Traveling Salesperson Problem, In Proceedings of the Twenty-Sixth Conference on Artificial Intelligence (AAAI-12), Toronto, ON, Canada, July 2012. [CoRR abs/1207.0578]
• A. M. Sutton, J. Day, and F. Neumann. A Parameterized Runtime Analysis of Evolutionary Algorithms for MAX-2-SAT, In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-12), Philadelphia, PA, July 2012. [link]
• T. Kötzing, A. M. Sutton, F. Neumann, and U.-M. O'Reilly. The Max Problem Revisited: The Importance of Mutation in Genetic Programming, In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-12), Philadelphia, PA, July 2012. [link]
• A. M. Sutton, L. D. Whitley, and A. E. Howe. Mutation Rates of the (1+1)-EA on Pseudo-Boolean Functions of Bounded Epistasis, In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-11), Dublin, Ireland, July 2011. [link]
• A. M. Sutton, L. D. Whitley, and A. E. Howe. Approximating the Distribution of Fitness over Hamming Regions, In Proceedings of the Foundations of Genetic Algorithms (FOGA XI), Schwarzenberg, Austria, January 2011. [link]
• A. M. Sutton, A. E. Howe, and L. D. Whitley. Directed Plateau Search for MAX-k-SAT, In Proceedings of the Third Annual Symposium on Combinatorial Search, Atlanta, GA, July 2010. [link]
• A. M. Sutton, A. E. Howe, and L. D. Whitley. A Theoretical Analysis of the k-Satisfiability Search Space, In Proceedings of SLS 2009, Brussels, Belgium, September 2009. Published in Lecture Notes in Computer Science Vol. 5752, (2009) pp. 46-60. [link]
  [Second runner-up for Best Paper Award]
• A. M. Sutton, A. E. Howe, and L. D. Whitley. Estimating Bounds on Expected Plateau Size in MAXSAT Problems, In Proceedings of SLS 2009, Brussels, Belgium, September 2009. Published in Lecture Notes in Computer Science Vol. 5752, (2009) pp. 31-45. [link]
• A. M. Sutton, L. D. Whitley, and A. E. Howe. A Polynomial Time Computation of the Exact Correlation Structure of k-Satisfiability Landscapes, In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-09), Montreal, Canada, July 2009. [link] [slides]
• L. D. Whitley and A. M. Sutton. Partial Neighborhoods of Elementary Landscapes, In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-09), Montreal, Canada, July 2009. [link]
• M. Lunacek, D. Whitley, and A. Sutton. The Impact of Global Structure on Search, In Proceedings of the 10th Conference on Parallel Problem Solving from Nature (PPSN-08), Dortmund, Germany, September 2008. [link]
  [Awarded Best Student Paper]
• L. D. Whitley, A. M. Sutton, and A. E. Howe. Understanding Elementary Landscapes, In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-08), Atlanta, GA. [link]
• A. M. Sutton, A. E. Howe, and L. D. Whitley. Using Adaptive Priority Weighting to Direct Search in Probabilistic Scheduling, In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS-07), Providence, RI. [link]
• A. M. Sutton, M. Lunacek, and L. D. Whitley. Differential Evolution and Non-separability: Using selective pressure to focus search, In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-07), London, England. [link]
• J. Smith, L. D. Briceno, A. A. Maciejewski, H. J. Siegel, D. Janovy, T. Renner, J. Ladd, A. Sutton, S. Govindasamy, A. Alqudah, R. Dewri, P. Prakash, V. Shestak. Measuring the Robustness of Resource Allocations in a Stochastic Dynamic Environment, In Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS 2007), Long Beach, CA. [link]
• A. M. Sutton, L. D. Whitley, M. Lunacek, and A. Howe. PSO and Multifunnel Landscapes: How cooperation might limit exploration, In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-06), Seattle, WA. [link]
  [Nominated for Best Paper]
• A. M. Sutton, A. Howe, and L. D. Whitley, Spacetrack: Trading-off Quality and Utilization in Oversubscribed Schedules, In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS-06, short paper), English Lake District, UK. [link]

Miscellaneous

Tutorials

• Parameterized complexity analysis of evolutionary algorithms tutorial at GECCO 2015 (with Frank Neumann). [link]
• Parameterized complexity analysis of evolutionary algorithms tutorial at GECCO 2014 (with Frank Neumann). [link]
• Elementary Landscapes: Theory and Applications tutorial at GECCO 2013 (with Darrell Whitley). [link]
• Elementary Landscapes: Theory and Applications tutorial at GECCO 2012 (with Darrell Whitley). [link]
• Elementary Landscape Analysis for TSP, Graph Coloring, Graph Partitioning, and MAXSAT tutorial at GECCO 2009 (with Darrell Whitley). [link]