Invited Talk:
IKEGAMI, Atsuko (Seikei U.)
Diversity and similarity of solutions in nurse scheduling

We will organize a mini-symposium on combinatorial reconfiguration in Japanese Conference on Combinatorics and its Applications 2021 (JCCA-2021).

 

Invitation to Combinatorial Reconfiguration

Reconfiguring Directed Trees in a Digraph

Reconfiguration of Unit Disks -- Combinatorial Reconfiguration in Continuous Spaces

On the Combinatorial Diameter of Convex Lattice Polytopes

Topology, one of the speaker's main research interests, is the study of the properties of "shapes" and "spaces." Ideas and methods of solving problems coming from topology are becoming more and more influential to all other branches of mathematics. More recently, the word "topological" has also starting to appear outside the mathematical world. One of the advantages of topological methods is that they provide a tool to turn some geometric data into some algebraic ones such as groups. In this talk, the speaker would like to give the audience some ideas on how one might think as a topologist through concrete examples. The speaker will also mention some related topics motivated by a current project on combinatorial reconfiguration.
 

We will organize a workshop on Combinatorial Reconfiguration, affiliated with the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021).

 

 

Combinatorial Reconfiguration studies reachability and related questions over combinatorial structures. These types of questions arise in many areas of mathematics, computer science, and related fields. A typical example asks  if the solution space of a Boolean formula is connected with respect to the Boolean cube topology, formed by flipping one bit at the time. Another example of a well-studied application is sampling from a very large configuration space by simulating a Markov chain involving local reconfigurations.

 

Although there is now a wealth of publications on many aspects of Combinatorial Reconfiguration, including a general framework, many questions remain open. The study of Combinatorial Reconfiguration brings together problems and techniques from a variety of fields in mathematics and computer science, such as combinatorial game theory, graph and hypergraph theory, enumeration, probability theory, random sampling via Markov Chain Monte Carlo methods, bioinformatics, complexity theory, discrete geometry, statistical physics, and many others.

 

This workshop aims at strengthening relations among researchers in various fields of theoretical computer science and mathematics, and broadening interest in Combinatorial Reconfiguration to a wider audience. Four invited talks by leading experts are planned as a way to build bridges to closely-related fields.

 

The workshop is held in cooperation with JSPS KAKENHI project "Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration."

 

- Nicolas Bousquet, CNRS, Université Lyon 1, France
- Anna Lubiw, University of Waterloo, Canada
- Torsten Mütze, University of Warwick, United Kingdom
- Akira Suzuki, Tohoku University, Japan

 

Authors are invited to submit original work that is related to any aspect or application of Combinatorial Reconfiguration. Presentations of on-going work and open problems, as well as challenges, are encouraged. Short survey talks are also welcome. 

 

The submission should be formatted in one page that contains the title of the work, the list of all authors, an email address of the corresponding author, and a brief summary of the presentation. There will be no formal refereeing process, and the work is expected to appear later in a refereed conference or a refereed journal.

 

Submission should be done via EasyChair (https://easychair.org/conferences/?conf=core2021) and the manuscript should be prepared as a PDF. The template for one-page abstracts can be found below:
http://www.dais.is.tohoku.ac.jp/core2021template.zip

 

A collection of one-page abstracts will be distributed to the workshop participants only.

 

- Submission deadline: May 20, 2021, 23:59 AoE

- Notification: June 4, 2021

- Camera-ready version due: June 30, 2021, 23:59 AoE

 

- Jan van den Heuvel, The London School of Economics and Political Science, United Kingdom
- Takehiro Ito, Tohoku University, Japan (Chair)
- Jun Kawahara, Kyoto University, Japan
- Naomi Nishimura, University of Waterloo, Canada
- Yoshio Okamoto, The University of Electro-Communications, Japan

 

- Takehiro Ito, Tohoku University, Japan (Chair)
- Jun Kawahara, Kyoto University, Japan
- Yoshio Okamoto, The University of Electro-Communications, Japan

 

Propositional satisfiability testing (SAT) problems and SAT solvers have been studied for over 50 years. In particular, since 2000, the performance of SAT solvers has improved dramatically, and SAT technology is attracting attention as a fundamental technology for inference. In this presentation, we will explain SAT solvers in the following order: its recent topics, its improvements in performance, its utilization techniques, and SAT-based constraint programming systems. 

CONN-SAT is the problem of deciding whether a subgraph of a Hamming cube is connected or not, where the subgraph is induced by a set of satisfying assignments of Boolean formulas. As the complexity of SAT varies according to types of formulas (Horn SAT, XOR SAT, 2SAT, 3SAT etc.), the complexity of CONN-SAT is classified by such types. In this talk, I will give an overview on the classification of the complexity of CONN-SAT. I also mention an exponential time algorithm for CONN-SAT where formulas are k-CNFs (the problem is PSPACE-complete). This is a joint work with Kazuhisa Makino and Masaki Yamamoto.

The constraint satisfaction problem (CSP) is the problem of determining if there exists an assignment of values to variables so that all given constraints are satisfied. While the CSP is NP-complete in general, a restriction on relations appearing in constraints can ensure the polynomial-time solvability. In 1998, Feder and Vardi conjectured that a problem obtained from such a restriction is either in P or NP-complete, which is called the dichotomy conjecture. This was settled affirmatively by Bulatov and by Zhuk in 2017. In this talk, I will give a brief overview of an algebraic approach to CSPs that plays an important role in the proofs of the dichotomy conjecture.

Sorting is one of the most fundamental tasks in computer science. A majority of existing sorting algorithms are so-called "comparison-based sorting", whose basic operation is a comparison of two input elements.Its time-complexity is evaluated by the number of comparisons executed during the computation.Although researches on identifying the minimum number of comparisons have been performed more than 50 years, the optimal number of comparisons even for sorting 16 elements is still open.In this talk, I will give a brief survey on the research on this line.I will also describe algorithms which nearly match a theoretical lower bound asymptotically.