https://www.dagstuhl.de/21101

March 7 – 12 , 2021, Dagstuhl Seminar 21101

CANCELLED Pushing the Limits of Computational Combinatorial Constructions

Due to the Covid-19 pandemic, this seminar was cancelled.

Organizers

Lucia Moura (University of Ottawa, CA)
Anamari Nakic (University of Zagreb, HR)
Patric Östergård (Aalto University, FI)
Alfred Wassermann (Universität Bayreuth, DE)

For support, please contact

Dagstuhl Service Team

Motivation

In discrete mathematics, construction and classification of structures are core problems. Computational methods have been essential in settling important mathematical questions, such as the proof of the four color theorem (Apel and Haken, 1976) and the nonexistence of projective planes of order 10 (Lam et al., 1989). Isomorph-free exhaustive searches are quite challenging with the number of nonequivalent objects often growing exponentially with the input size. For example, the classification of Steiner triple systems of order 19 (Kaski and Östergård, 2004) involved producing a list of more than 11 billion such objects. Vast exhaustive searches are also used to establish negative results, as in the non-existence of 16-clue Sudoku puzzles (McGuire et al., 2012), celebrated by the media due to its connection with the famous puzzle. Many of the central problems, even subproblems, are (NP-)hard, but with improved algorithms and general approaches, it is still possible to handle instances with not too small parameters.

In this Dagstuhl Seminar, we will focus on computational methods for challenging problems in combinatorial construction. This includes algorithms for construction of combinatorial objects with prescribed symmetry, for isomorph-free exhaustive generation, and for combinatorial search. Examples of specific algorithmic techniques are tactical decomposition, the Kramer-Mesner method, algebraic methods, graph isomorphism software, isomorph-free generation, clique-finding methods, heuristic search, and combinatorial optimization. There will be an emphasis on problems involving graph, designs and codes, also including topics in related fields such as finite geometry, graph decomposition, Hadamard matrices, Latin squares, and q-analogs of designs and codes. Examples of specific cases to consider are the existence problems for q-analogs of the Fano plane and projective planes with an order that is not a prime power.

This seminar will bring together researchers with different expertise: those with a deep understanding of combinatorial objects and experts in algorithm design and high-performance computing. Participants will discuss and improve on state-of-the-art methods for challenging problems in constructing combinatorial objects and highlight important open problems to attack. Additionally, the seminar aims to bring together experts on combinatorial algorithms and representatives from different scientific communities developing practical techniques for attacking general hard problems, for example, in the framework of satisfiability, integer linear programming, and optimization. The contribution of scholars working in high-performance computing and experts on relevant computer architectures (such as GPUs) will also be valuable.

The goal of this seminar is to provide a creative impulse towards new research in the topic. All participants will get the chance to report on their experience, either in plenary short talks or in working group panels. Dealing with finite discrete problems, which can always be solved in finite time, success is about algorithms and computational resources. This venue will give opportunity to the researchers also to discuss the challenges found when they did not succeed, and it could be catalytic for advances in the field. A short-term goal of the seminar is to exchange information and initiate new collaborative research on the themes of the seminar. We hope the seminar will generate new ideas, new problems, new collaborations and new breakthroughs, with significant impact in the upcoming years.

Motivation text license
  Creative Commons BY 3.0 DE
  Lucia Moura, Anamari Nakic, Patric Östergård, and Alfred Wassermann

Classification

  • Data Structures And Algorithms
  • Discrete Mathematics
  • Mathematical Software

Keywords

  • Combinatorial algorithms
  • Subspace designs
  • Finite geometries
  • Automorphism groups

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.