TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 21101

Pushing the Limits of Computational Combinatorial Constructions Cancelled

( Mar 07 – Mar 12, 2021 )

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/21101

Replacement
Dagstuhl Seminar 23161: Pushing the Limits of Computational Combinatorial Constructions (2023-04-16 - 2023-04-21) (Details)

Organizers

Contact

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.

Copyright Lucia Moura, Anamari Nakic, Patric Östergård, and Alfred Wassermann

Participants
  • Alfred Wassermann (Universität Bayreuth, DE) [dblp]

Classification
  • Data Structures and Algorithms
  • Discrete Mathematics
  • Mathematical Software

Keywords
  • combinatorial algorithms
  • subspace designs
  • finite geometries
  • automorphism groups