FY2023

• 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 :