Events Records| KAKENHI Grant-in-Aid for Transformative Research Areas (B)

Jun KAWAHARA (Kyoto U., Group B01) will give a talk in the organized session "Autonomous decision making under complex conditions or situations" of the 4th Asia Pacific Conference of the Prognostics and Health Management Society (PHMAP 2023).

2023.09.13 Wed. 14:00-14:20

Jun Kawahara, Chuta Yamaoka, Takehiro Ito, Akira Suzuki, Daisuke Iioka, Shuhei Sugimura, Seiya Goto, and Takayuki Tanabe

"Algorithmic Study for Power Restoration in Electrical Distribution Networks"

This talk will be based on the joint press release of our research project. The organized session will be held from 13:20 to 16:00, and 7 talks are scheduled. (PHMAP 2023 will be held on September 11-14.)

2023.09.13 Wed. 13:20-16:00

Talk in International conference "PHM Asia Pacific 2023"
Speaker : Title : Sumarry :
As a part of the research project "Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration" (head investigator: Takehiro Ito), we are going to organize a minisymposium on Combinatorial Reconfiguration in the 10th International Congress on Industrial and Applied Mathematics (ICIAM 2023). This minisymposium aims at communicating recent research trends on combinatorial reconfiguration and discussing possible future directions.
Program and Registration
- Program
- Please make your registration for ICIAM 2023.
List of Speakers
- Colin Defant (Massachusetts Institute of Technology, USA) * invited speaker
- Irene Parada (Universitat Politècnica de Catalunya, Spain) * invited speaker
- Nicholas Williams (Lancaster University, UK) * invited speaker
- Takehiro Ito (Tohoku University, Japan)
Talk Titles and Abstracts

[17:40-18:05] Takehiro Ito (Tohoku University, Japan)

Title: Invitation to Combinatorial Reconfiguration

Abstract: Combinatorial Reconfiguration studies reachability and related questions over combinatorial structures. 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. Reconfiguration problems have motivation from a variety of fields such as puzzles, statistical physics and industry, and have been studied intensively in this decade from the algorithmic viewpoints. In this talk, we will give a broad introduction of combinatorial reconfiguration, and show some recent progress on the topic.
[18:05-18:30]  Irene Parada (Universitat Politècnica de Catalunya, Spain) * invited speaker

Title: Geometric Algorithms for Modular Robotics

Abstract: Modular self-reconfigurable robots consist of individual units that can move and connect to one another to form a larger, more complex shape. A central problem that arises is how to efficiently reconfigure these robots from one shape to another while maintaining connectivity.

We will explore the computational complexity of the reconfiguration problem for the most fundamental lattice-based models of modular robots. Specifically, we will examine how the reconfiguration problem differs depending on the lattice and movement capabilities of the units. We will discuss efficient algorithms for universal reconfiguration in some models, while in others the problem is PSPACE-complete, which means that it is computationally intractable. For those cases, we identify simple conditions that allow for efficient reconfiguration.

Overall, this talk will provide insights into the challenges of reconfiguring modular robots and demonstrate how geometric and graph algorithms can help us tackle this problem.

[18:30-18:55]  Colin Defant (Massachusetts Institute of Technology, USA) * invited speaker

Title: Toric Promotion and Permutoric Promotion

Abstract: We introduce toric promotion as a cyclic variant of Schutzenberger's famous promotion operator. Toric promotion acts on the labelings of a graph G; it is defined as the composition of certain toggle operators, listed in a natural cyclic order. We will show that the orbit structure of toric promotion is surprisingly nice when G is a forest. We then consider more general permutoric promotion operators, which are defined as compositions of the same toggle operators, but in permuted orders. When G is a path graph, we provide a complete description of the orbit structures of all permutoric promotion operators, showing that they satisfy the cyclic sieving phenomenon. Our proof is surprisingly involved and relies on the analysis of gliding globs, sliding stones, and colliding coins. The work on permutoric promotion is joint with Rachana Madhukara and Hugh Thomas.

[18:55-19:20]  Nicholas Williams (Lancaster University, UK) * invited speaker

Title: Triangulations of Cyclic Polytopes Through the Lens of Reconfiguration

Abstract: We discuss the reconfiguration problem given by taking the set of triangulations of a cyclic polytope as the state space, with the reconfiguration moves given by bistellar flips (the higher-dimensional analogue of flipping a diagonal within a quadrilateral). The state space is connected, and we will outline how this is proven using a certain partial order on the states called the higher Stasheff-Tamari order. We will further consider as many different other aspects of the reconfiguration as time permits, including the significance of triangulations of higher-dimensional cyclic polytopes for reconfigurations of lower-dimensional cyclic polytopes, efficient combinatorial descriptions of triangulations of cyclic polytopes, and the diameter of the state space.
Organizers
- Takehiro Ito (Tohoku University, Japan)
- Yusuke Kobayashi (Kyoto University, Japan)
- Yoshio Okamoto (The University of Electro-Communications, Japan)
2023.08.22 Tue. 17:40-19:20

Minisymposium on Combinatorial Reconfiguration in ICIAM 2023
Speaker : Title : Sumarry :
We will organize the 3rd workshop on Combinatorial Reconfiguration, affiliated with the 50th International Colloquium on Automata, Languages, and Programming (ICALP2023).
- Program and Registration
Program

This workshop will be held as a pure face-to-face event. To attend our workshop, please make a registration for ICALP workshops.
- Aim and Scope
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.

With the success of the workshops affiliated with ICALP 2021 and ICALP 2022, 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. Two invited talks by leading experts are planned as a way to build bridges to closely-related fields. We also plan to report the results of the 2nd Combinatorial Reconfiguration Challenge (CoRe Challenge 2023) during the workshop.
https://core-challenge.github.io/2023/

The workshop is planned to be held in person in Paderborn.

The workshop is held in cooperation with JSPS KAKENHI project "Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration."
https://core.dais.is.tohoku.ac.jp/en/
- Invited Speakers
- Marthe Bonamy (Université de Bordeaux, France)
- Jun Kawahara (Kyoto University, Japan)
- Call for Contributed Talks and Submission Guideline
Authors are invited to submit original work that is related to any aspect or application of Combinatorial Reconfiguration. Any work already or not yet published is welcome. Presentations of ongoing work and open problems, as well as challenges, are encouraged. Short survey talks are also welcome.

The submission must 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. The manuscript must be prepared with the following template as a PDF file.
http://www.dais.is.tohoku.ac.jp/core2023template.zip

Even though there will be no strict formal refereeing process, some contributions might not be accepted at the discretion of the Program Committee. A collection of one-page abstracts will be distributed to the workshop participants only. Submission should be done via EasyChair.
https://easychair.org/conferences/?conf=core2023
- Important Dates
- Submission deadline: ~~April 22, 23:59 AoE~~ (extended to) May 7, 23:59 AoE
- Notification: ~~May 8~~ (extended to) May 12

(- Early registration deadline for ICALP 2023: May 15, 23:59 CET)
- Camera-ready version due: June 19, 23:59 AoE
- Date of workshop: July 10, 2023
- Program Committee
- Nicolas Bousquet, CNRS, Université Lyon 1, France
- Takehiro Ito, Tohoku University, Japan (Chair)
- Naomi Nishimura, University of Waterloo, Canada
- Yoshio Okamoto, The University of Electro-Communications, Japan
- Akira Suzuki, Tohoku University, Japan
- Organizing Committee
- Takehiro Ito, Tohoku University, Japan (Chair)
- Yoshio Okamoto, The University of Electro-Communications, Japan
- Akira Suzuki, Tohoku University, Japan
2023.07.10 Mon.

3rd Workshop on Combinatorial Reconfiguration, affiliated with ICALP 2023
Speaker : Title : Sumarry :
There are many real-world problems that can be formulated as combinatorial optimization problems. They tend to be NP-hard and are hard to solve exactly when the instance sizes are large. As a practical way to solve such problems, heuristic algorithms are often used to find good solutions, though not necessarily optimal, in a reasonable amount of time. Standard basic heuristic strategies include greedy methods and local search algorithms. Such basic strategies are often combined to make more sophisticated methods, called metaheuristics, to find better solutions using more computation time. This talk introduces some of our results on efficient heuristic algorithms based on such strategies.

2023.02.06 Mon. 10:00-12:00

35th CoRe Seminar
Speaker :YAGIURA, Mutsunori (Nagoya U., invited talk) Title :Practical algorithms for combinatorial optimization problems Sumarry :
An amidakuji (i.e., ladder lotteries, or Ghost Legs) consists of n vertical lines (lines for short) and some horizontal bars (bars for short), where lines have their labels, and each bar connects two lines. By regarding each bar as the exchange of the labels of a pair of lines, an amidakuji (i.e., the network of the lines and bars) represents a permutation. Amidakuji's also correspond to sorting networks, in which bars are regarded as comparators. An amidakuji corresponds to a primitive sorting network if every bar connects two consecutive lines. A rhombus tiling is a tiling of rhombuses of unit edge length without gap or overlap. In this talk, we begin with the relation between Amidakujis and rhombus tilings. Then, we move to the enumeration by the reverse search and ZDDs (Zero-Suppressed Binary Decision Diagrams).

2023.01.16 Mon. 10:00-12:00

34th CoRe Seminar
Speaker :HORIYAMA, Takashi (Hokkaido U., invited talk) Title :Enumeration of amidakujis and rhombus tilings Sumarry :

As a part of the research project "Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration" (head investigator: Takehiro Ito), we are going to organize Workshop "Combinatorial Reconfiguration and Fixed-Parameter Tractability" via Zoom on December 12, 2022 (based on European Timezone).

The objective is to learn recent developments of fixed-parameter (in)tractability and their relations with combinatorial reconfiguration. In her influential survey paper "Introduction to Combinatorial Reconfiguration" (Algorithms 2018), Naomi Nishimura dedicated one section to applications of the parameterized complexity methodology to problems on combinatorial reconfiguration. Indeed, several papers have been presented along this line of research. Furthermore, the research activity on fixed-parameter (in)tractability has been quite active, and there are a lot of recently introduced methods that are waiting for being applied to combinatorial reconfiguration. In this workshop, we will learn recent research trends of fixed-parameter tractability and combinatorial reconfiguration, and will discuss a new connection between these two fields of theoretical computer science.

This workshop aims at the broad audience of discrete mathematics and theoretical computer science, who wish to learn and work on these active research areas.

The program will be exclusively composed of invited talks. Each talk is planned to span one hour, including discussion.

List of Confirmed Invited Speakers

Hans L. Bodlaender (Utrecht University, the Netherlands)
Bart M. P. Jansen (Eindhoven University of Technology, the Netherlands)
Eun Jung Kim (Paris-Dauphine University, France)
Moritz Mühlenthaler (Université Grenoble Alpes, France)
Saket Saurabh (The Institute of Mathematical Sciences, India)

Registration

Registration is free of charge, but please make your registration in advance.

Program

2022.12.12 Mon. CET (JST)

08:55-09:00 (16:55-17:00)	Welcome address
09:00-10:00 (17:00-18:00)	Eun Jung Kim (Paris-Dauphine University, France) Twin-Width and Its Implications
10:15-11:15 (18:15-19:15)	Moritz Mühlenthaler (Université Grenoble Alpes, France) Constraint Satisfaction Reconfiguration
11:15-13:00 (19:15-21:00)	Lunch/Dinner Break
13:00-14:00 (21:00-22:00)	Saket Saurabh (The Institute of Mathematical Sciences, India) FPT Approximation Schemes for the Maximum Coverage and MAX-SAT Problem
14:15-15:15 (22:15-23:15)	Bart M. P. Jansen (Eindhoven University of Technology, the Netherlands) Search Space Reduction Beyond Kernelization
15:30-16:30 (23:30-24:30)	Hans L. Bodlaender (Utrecht University, the Netherlands) Parameterized Complexity of Reconfiguration of Small Independent Sets and Dominating Sets

Talk Titles and Abstracts

09:00-10:00 (17:00-18:00)

Eun Jung Kim (Paris-Dauphine University, France)

Title: Twin-Width and Its Implications

Abstract: First Order Logic (FO logic) expresses many classic computational problems such as k-Independent Set problem with variables and logical connectives. First Order model checking is known to be fixed-parameter tractable on important classes such as nowhere dense classes, bounded rank-width graphs, unit interval graphs as well as strict hereditary classes of permutations. A notion called twin-width, introduced by Bonnet, Kim, Thomassé, Watrigant (FOCS 2020), elegantly captures vast swathes of such classes, and provides a new perspective to explain why so many computational problems are fixed-parameter tractable on graph classes seemlying so different. We will briefly sketch the new notion, and its rapidly developing impact in theoretical computer science with an emphasis on algorithm designs.

10:15-11:15 (18:15-19:15)

Moritz Mühlenthaler (Université Grenoble Alpes, France)

Title: Constraint Satisfaction Reconfiguration

Abstract: The constraint satisfaction problem (CSP) asks for an assignment of values to variables such that given constraints are satisfied. Special cases of the CSP are for example graph coloring and Boolean satisfiability. We consider the following reconfiguration variant of the CSP: given two feasible solutions of a CSP instance, can we transform one solution into the other by changing the value of a single variable at a time, such that in each step the constraints are satisfied? We give an overview of what is known about the complexity of this question and highlight the techniques behind recent algorithmic results.

13:00-14:00 (21:00-22:00)

Saket Saurabh (The Institute of Mathematical Sciences, India)

Title: FPT Approximation Schemes for the Maximum Coverage and MAX-SAT Problem

Abstract: Vertex Cover is a classical NP-hard problem. Partial Vertex Cover is a variant of the Vertex Cover problem where the goal is to maximize the number of edges covered, given a fixed number of vertices that can be used. Partial Vertex Cover is a W[1]-hard problem. There are FPT approximation schemes for Partial Vertex Cover parameterized by the solution size, i.e., there are $(1-\epsilon)$-factor approximation algorithms running in time $f(k,\epsilon) n^{O(1)}$ for all $0<\epsilon<1$. In this talk, we consider the Partial Vertex Cover problem and SAT problems in hypergraphs where there is no bound on the size of the hyperedges. We design an FPT approximation scheme for these problems on hypergraphs that satisfies the Kij-free property, i.e., no $i$ vertices are contained in $j$ common hyperedges.

14:15-15:15 (22:15-23:15)

Bart M. P. Jansen (Eindhoven University of Technology, the Netherlands)

Title: Search Space Reduction Beyond Kernelization

Abstract: The framework of kernelization gives a mathematical model for the rigorous analysis of preprocessing, aimed at showing that any instance with parameter k can efficiently be reduced to an equivalent one whose size depends only on k. Kernelization serves as a useful tool to obtain FPT algorithms, since any brute-force algorithm solves the reduced instance in time depending only on k. However, from the definition of kernelization it is not clear why kernelization would lead to significant speed-ups when the reduced instance is not solved by brute force, but by a fixed-parameter tractable algorithm whose running time is governed by the value of the parameter. To speed up such algorithms, it is the parameter controlling the size of the search space which should decrease, rather than the encoding size of the input. The discrepancy between reducing the instance size versus decreasing the search space is the focus of this talk. The quest for preprocessing algorithms that reduce the search space leads to a new type of algorithmic and graph-theoretical questions. The talk gives an introduction to this budding line of inquiry by presenting examples from recent work on the search for essential vertices and antler structures in graphs.
Based on joint work with Benjamin M. Bumpus, Huib Donkers, and Jari J.H. de Kroon.

15:30-16:30 (23:30-24:30)

Hans L. Bodlaender (Utrecht University, the Netherlands)

Title: Parameterized Complexity of Reconfiguration of Small Independent Sets and Dominating Sets

Abstract: In this talk, we look at the complexity of reconfiguring independent or dominating sets, where we assume that the size of the sets is a small parameter k, under different rules of moving the "tokens". It appears that the parameterized complexity depends on the assumption of how the number of moves that can be made is specified, but less on the type of moves.
Some related literature is also reviewed.

Organizers

Takehiro Ito (Tohoku University, Japan)
Yoshio Okamoto (The University of Electro-Communications, Japan)
Yota Otachi (Nagoya University, Japan)

2022.12.12 Mon.

Workshop "Combinatorial Reconfiguration and Fixed-Parameter Tractability"
Speaker : Title : Sumarry :

I will introduce the theoretical field of distributed computing to you in this talk by explaining recent results on two problems in the field. Specifically, I will talk about
(i) the leader election problem in the population protocol model, and
(ii) Byzantine gathering problem by mobile agents.

The population protocol model represents a network consisting of tiny sensors that moves passibly (i.e., they constantly move, but cannot control their own move). This model was proposed by Angluin et al. in 2004 and has been intensively studied since then. In particular, the leader election problem and the majority problem are well studied. In this talk, I will discuss the former, that is, the leader election problem.

Mobile agents are mobile entity that moves autonomously on a computer network. The gathering problem is a well-studied fundamental problem, which requires all agents to gather at a single node. In this talk, we will discuss a variant of this problem, i.e., the gathering problem with the assumption that some agents take arbitrary adversarial actions.

2022.12.05 Mon. 10:00-12:00

33rd CoRe Seminar
Speaker :SUDO, Yuichi (Hosei U., invited talk) Title :The theoretical field of distributed computing Sumarry :
I am a researcher in the field of electric power and energy. I am researching mechanisms to maximize the introduction of renewable energy sources on the premise of ensuring safety, stable supply, economic efficiency, and environmental conservation. One of the issues in increasing the introduction of renewable energy sources is the degradation of power quality, which adversely affects social life. In this presentation, the mechanism and countermeasures for power quality degradation caused by renewable energy source will be described, and research to expand the amount of renewable energy sources that can be introduced will be introduced.

2022.11.28 Mon. 10:00-12:00

32nd CoRe Seminar
Speaker :IIOKA, Daisuke (Chubu U., Group B01) Title :Development of electric power system based mainly on renewable energy sources Sumarry :
Dynamical Systems is a field that studies the collective behavior of objects that update their states according to some rules. Discrete-Time Boolean Finite Dynamical System (DT-BFDS) is a subfield where the systems have some finite number of objects whose states are Boolean values, and the state updates occur in discrete time. In the subfield of DT-BFDS, researchers aim to (i) design models for capturing real-world phenomena and using the models to make predictions and (ii) develop simulation techniques for acquiring insights about the systems' behavior. Useful for both aims is understanding the system dynamics mathematically before executing the systems. Obtaining a mathematical understanding of BFDS is quite challenging, even for simple systems, because the state space of a system grows exponentially in the number of objects. Researchers have used computational complexity to circumvent the challenge. The complexity theoretic research in DT-BFDS has successfully produced complete characterizations for many dynamical problems.

The DT-BFDS studies have mainly dealt with deterministic models, where the update at each time step is deterministic, so the system dynamics are completely determinable from the initial setting. However, natural systems have uncertainty. Models having uncertainty may lead to far-better understandings of nature. Although a few attempts have explored DT-BFDS with uncertainty, including stochastic initialization and tie-breaking, they have scratched only a tiny surface of models with uncertainty. The introduction of uncertainty can be through two schemes. One is the introduction of alternate update functions. The other is the introduction of alternate update schedules. In this talk, I present a set of new DT-BFDS models with uncertainty and present some initial results.

2022.11.14 Mon. 10:00-12:00

31st CoRe Seminar
Speaker :OGIHARA, Mitsunori (U. Miami, invited talk) Title :A theory for discrete-time Boolean finite dynamical systems with uncertainty Sumarry :
In the k-recoloring problem, we are given two (vertex-)colorings of a graph using k colors, and asked to transform one into the other by recoloring only one vertex at a time, while at all times maintaining a proper k-coloring. In this talk, we consider a (directed) recolorability constraint on the k colors, which forbids some pairs of colors to be recolored directly. The recolorability constraint is given in terms of a digraph, whose vertices correspond to the colors and whose arcs represent the pairs of colors that can be recolored directly. We provide algorithms for the problem based on the structure of the digraph, showing that the problem is solvable in linear time when the digraph is a directed cycle or is in a class of multitrees. This talk is based on joint work with Soichiro Fujii, Yuni Iwamasa, and Akira Suzuki.

2022.10.31 Mon. 10:00-12:00

30th CoRe Seminar
Speaker :KIMURA, Kei (Kyushu U., invited talk) Title :Algorithms for coloring reconfiguration under recolorability digraphs Sumarry :
The online bipartite matching problem is the problem of finding a maximum-size matching when vertices on one side arrive one by one. The problem has practical applications such as online advertisement, ride-sharing, and crowd sourcing. This talk proposes a variant of the problem motivated by such applications, and presents online algorithms with constant competitive ratio. This talk is based on joint work with Hanna Sumita, Shinji Ito, Kei Takemura, Daisuke Hatano, Takuro Fukunaga, Ken-ichi Kawarabayashi.

2022.10.17 Mon. 10:00-12:00

29th CoRe Seminar
Speaker :KAKIMURA, Naonori (Keio U., Group C01) Title :Constrained online bipartite matching Sumarry :
2022.09.02 Fri.

Workshop "Polytope Diameter and Related Topics"
Speaker : Title : Sumarry :
We will organize a mini-symposium on combinatorial reconfiguration in Japanese Conference on Combinatorics and its Applications 2022 (JCCA-2022).

10:50--11:20
Hiroshi Eto (Tohoku U.), Takehiro Ito (Tohoku U.), Yasuaki Kobayashi (Hokkaido U.), Shun-ichi Maezawa (Tokyo U. Science), Yota Otachi (Nagoya U.), and Kunihiro Wasa (Hosei U.)
"Induced Matching Reconfiguration on Trees"

11:20--11:50
Tatsuya Gima (Nagoya U.), Takehiro Ito (Tohoku U.), Yasuaki Kobayashi (Hokkaido U.), and Yota Otachi (Nagoya U.)
"Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited"

14:00--14:30
Kento Nakada (Okayama U.)
"Combinatorial game theory ---Extension from Nim and Sato's game to INSET game---"

14:30--15:00
Takehiro Ito (Tohoku U.), Jun Kawahara (Kyoto U.), Shin-ichi Minato (Kyoto U.), Yota Otachi (Nagoya U.), Toshiki Saitoh (Kyushu Institute of Technology), Akira Suzuki (Tohoku U.), Ryuhei Uehara (JAIST), Takeaki Uno (NII), Katsuhisa Yamanaka (Iwate U.), and Ryo Yoshinaka (Tohoku U.)
"Computational Complexity of Ball/Water Sort Puzzles"

2022.08.17 Wed. 10:50-15:00

JCCA-2022 Mini-Symposium
Speaker : Title : Sumarry :
In this talk, we introduce a Python library for solving combinatorial reconfiguration problems, which is under development in our project. The library is based on graphillion, a subgraph enumeration library. It can solve combinatorial reconfiguration problems for families of sets that can be represented by graphillion. We also introduce the algorithm used in the library.

2022.07.25 Mon. 15:00-17:00

28th CoRe Seminar
Speaker :KAWAHARA, Jun (Kyoto U., Group B01) Title :Reconfillion: a combinatorial reconfiguration solver Sumarry :
Navigation for a team of agents is a challenging but interesting problem with a variety of applications, including fleet operations in warehouses, video games, and drone shows. In this talk, I provide an overview of techniques for controlling multiple moving agents. The talk includes multi-agent pathfinding (MAPF) which aims at finding a set of collision-free paths on graphs, planning in continuous spaces, and robust execution policies for real robots.

2022.07.11 Mon. 15:00-17:00

27th CoRe Seminar
Speaker :OKUMURA, Keisuke (Tokyo Institute of Technology, invited talk) Title :Navigation for a team of agents Sumarry :
We will organize the 2nd workshop on Combinatorial Reconfiguration, affiliated with the 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022).
- Program and Registration
Program

Registration for Zoom

If you will attend our workshop virtually, you don't need to make an ICALP registration for our workshop: our workshop is free of charge for virtual participants.

For on-site participants, it is not obligatory to register for the Zoom meeting. Nevertheless, we kindly recommend you to register. The collection of abstracts is planned to be shared through the Zoom meeting, and the compilation of the list of participants will be easier for the organizers if you register.
- Aim and Scope
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 a 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.

With the success of the 1st workshop affiliated with ICALP 2021, 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. Two invited talks by leading experts are planned as a way to build bridges to closely-related fields. We also plan to have the award ceremony for the 1st Combinatorial Reconfiguration Challenge (CoRe Challenge 2022) during the workshop.
https://core-challenge.github.io/2022/

The workshop is planned to be held in person in Paris, but participants have the option to join online. However, because of the future uncertainty, we may opt for a fully online workshop, even if ICALP itself is held in person.

The workshop is held in cooperation with JSPS KAKENHI project "Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration."
https://core.dais.is.tohoku.ac.jp/en/
- Invited Speakers
- Catherine Greenhill (UNSW Sydney, Australia)
- Amer E. Mouawad (American University of Beirut, Lebanon)
- Call for Contributed Talks and Submission Guideline
Authors are invited to submit original work that is related to any aspect or application of Combinatorial Reconfiguration. Any work already or not yet published is welcome. Presentations of ongoing work and open problems, as well as challenges, are encouraged. Short survey talks are also welcome.

The submission must 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. The manuscript must be prepared with the following template as a PDF file.
http://www.dais.is.tohoku.ac.jp/core2022template.zip

There will be no formal refereeing process. A collection of one-page abstracts will be distributed to the workshop participants only. Submission should be done via EasyChair.

https://easychair.org/conferences/?conf=core2022
- Important Dates
- Submission deadline: May 11, 23:59 AoE
- Notification: May 25
- Camera-ready version due: June 13, 23:59 AoE
- Date of workshop: July 4, 2022
- Program Committee
- Nicolas Bousquet, CNRS, Universite Lyon 1, France
- 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
- Akira Suzuki, Tohoku University, Japan
- Organizing Committee
- Takehiro Ito, Tohoku University, Japan (Chair)
- Jun Kawahara, Kyoto University, Japan
- Clément Legrand-Duchesne, Université de Bordeaux, France
- Yoshio Okamoto, The University of Electro-Communications, Japan
- Akira Suzuki, Tohoku University, Japan
2022.07.04 Mon.

2nd Workshop on Combinatorial Reconfiguration, affiliated with ICALP 2022
Speaker : Title : Sumarry :
To evaluate the fittings of statistical models on finite discrete spaces, we consider Monte Carlo simulation methods using Markov chain. To construct a connected Markov chain on a given space, we consider a Markov basis, which is characterized algebraically and is calculated by the theory of Groebner basis of the polynomial rings. In this talk, I give some primers on statistics and algebra to understand this topic, with some related works.

2022.06.13 Mon. 15:00-17:00

26th CoRe Seminar
Speaker :AOKI, Satoshi (Kobe U., invited talk) Title :Computational algebra for Markov chain Monte Carlo sampling Sumarry :
Enumerating subgraphs of a given graph is a fundamental task in computer science. Since the number of subgraphs can be exponentially larger than the input graph size, it is not practical to list all subgraphs one by one. To overcome the difficulty, we focus on implicit enumeration algorithms. Such an algorithm constructs a decision diagram (DD) representing the set of subgraphs instead of explicitly enumerating the subgraphs. In this talk, we introduce recent studies on implicit subgraph enumeration using DDs.

2022.05.30 Mon. 15:00-17:00

25th CoRe Seminar
Speaker :NAKAHATA, Yu (NAIST, Group C01) Title :Implicit subgraph enumeration using decision diagrams Sumarry :
A distributed system is a system of autonomous computing entities, that communicate and cooperate with each other. Each computing entity does not know the global system configuration, and locally performs computation and communication in parallel. This talk first presents a short survey on recent results on distributed reconfiguration problems on a communication graph of a distributed system, for example, independent sets [ICALP2019], vertex colorings [DISC2018], and spanning trees [SSS 2021]. These papers consider different difficulties in distributed computing. Then, the talk proceeds to reconfiguration in distributed systems of autonomous mobile computing entities, such as mobile robots and agents. Reconfiguration in such distributed systems have been considered for geometric positions of computing entities and called the pattern formation problem and distributed reconfiguration. The speaker recently works on solving problem such as search and evacuation by combinations of reconfiguration sequences. The talk addresses pattern formation by mobile robots and search and evacuation by a metamorphic robotic system.

2022.05.16 Mon. 15:00-17:00

24th CoRe Seminar
Speaker :YAMAUCHI, Yukiko (Kyushu U., Group A01) Title :Distributed computation and reconfiguration problems Sumarry :
In this talk, I consider a matching in a bipartite graph in which each vertex has a preference over the edges incident to it. Especially, I focus on a Pareto stable matching, which is a matching satisfying stability and Pareto efficiency. In talk, I give a survey of a Pareto stable matching including my recent result. I also talk about the relationship between Pareto stable matchings and combinatorial reconfiguration.

2022.4.25 Mon. 15:00-17:00

23rd CoRe Seminar
Speaker :KAMIYAMA, Naoyuki (Kyushu U., Group C01) Title :Pareto stable matchings Sumarry :