Program

October 30, 2024

Venue Aula Magna, Dipartimento di Scienze della Vita e Biologia dei Sistemi, via Accademia Albertina 13, TORINO

Time slots Regular: 25 min (20 min + 5 min for Q&A); Communication: 15 min (10 min + 5 min for Q&A)

September 11th

09:00 – 09:15 Opening ICTCS 2024

09:15 – 10:15 Invited Talk – “String diagrams in computer science”.
Abstract. String diagrams are a diagrammatic notation that originates from category theory. The operations of string diagrams are sequential and parallel composition, and the underlying concept of a monoidal category can be considered as a simple, yet powerful, process algebra. String diagrams have enjoyed many applications in computer science. I will introduce string diagrams and give an overview of some of the applications, including logic, quantum computing, concurrency theory and probability theory.
Pawel Sobocinsky, Tallin University of Technology, Estonia – Chair: L. Roversi

10:15 – 11:00 Coffee Break

11:00 – 12:40 Session n. 1 – COMPUTATIONAL MODELS – Chair: L. Roversi

11:00 – 11:25 Quantum Circuit Based Longest Common Substring and Longest Palindromic Substring, Domenico Cantone, Simone Faro, Arianna Pavone and Caterina Viola
11:25 – 11:50 The Grothendieck computability model, Luis Gambarte and Iosif Petrakis
11:50 – 12:15 Families of Constant-Depth Quantum Circuits for Rotations and Permutations, Simone Faro, Arianna Pavone and Caterina Viola
12:15 – 12:40 Low-space Quantum Algorithms for Estimate-Mark-Amplify Tasks, Debajyoti Bera and Tharrmashastha Sapv

12:40 – 14:00 Lunch

14:00 – 16:05 Session n. 2 – LANGUAGES AND COMPUTATION 1 – Chair: G. Fici

14:00 – 14:25 The Burrows-Wheeler transform of an elastic-degenerate string, Lapo Cioni, Veronica Guerrini and Giovanna Rosone
14:25 – 14:50 On the pseudorandomness of Parry–Bertrand automatic sequences, Pierre Popoli and Manon Stipulanti
14:50 – 15:15 A comparison between similarity measures based on Minimal Absent Words: an experimental approach, Giuseppa Castiglione, Sabrina Mantaci, Salvatore Leonardo Pizzuto and Antonio Restivo
15:15 – 15:40 Novel XBWT-based Distance Measures for Labeled Trees, Danilo G. Dolce, Sabrina Mantaci, Giuseppe Romana, Giovanna Rosone and Marinella Sciortino
15:40 – 16:05 Completing Wheeler Automata, Giuseppa Castiglione and Antonio Restivo

16:05 – 16:35 Coffee Break

16:35 – 18:00 Assembly of the IC of the EATCS – Chair: A. Montanari

September 12th

09:00 – 10:00 Invited Talk – “Reasoning and Rationality in the age of Generative AI”
Abstract. The remarkable achievements of contemporary Generative AI (GAI) systems like Large Language Models (LLMs) have spurred the hypotheses that neural models of computation are intrinsically a better solution (e.g. compared to symbolic approaches) for modelling intelligent phenomena in artificial systems. In addition, their capacity to achieve human, or superhuman, performances across various tasks have been sometimes interpreted as evidence that such models have de facto acquired the underlying human competences required for the manifestation of such intelligent behaviors. In this talk, I will present the notions of rationality developed in the field of cognitive science (i.e. Bounded Rationality (BR) and Resource-Rationality (RR)) and will show to what extent they can be applied to GAI systems. In doing so, I will discuss the two hypotheses above providing evidence of the strengths and limitations of GAI systems (in particular for reasoning tasks) and proposing a different, cognitively-grounded, architectural approach aiming at integrating neural and symbolic models.
Antonio Lieto, University of Salerno, Italy – Chair: U. de’Liguoro

10:00 – 10:30 Coffee Break

10:30 – 12:05 Session n. 3 – APPROXIMATION AND COMPLEXITY – Chair: G. Castiglione

10:30 – 10:55 Generation of skew convex polyominoes, Michela Ascolese, Andrea Frosini and Simone Rinaldi
10:55 – 11:20 The complexity of boolean failure identification, Nicola Galesi and Fariba Ranjbar
11:20 – 11:35 Achieving Envy-Freeness through Items Sale, Vittorio Bilò, Evangelos Markakis and Cosimo Vinci
11:35 – 11:50 On balancing energy consumption in Multi-Interface Networks, Alessandro Aloisio
11:50 – 12:05 Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations, Melissa Antonelli, Arnaud Durand and Juha Kontinen

12:05 – 14:00 Lunch

14:00 – 15:50 Session n. 4 – GRAPHS, GAMES AND AUTOMATA – Chair: A. Frosini

14:00 – 14:25 Toward Grünbaum’s Conjecture Bounding Vertices of Degree 4, Christian Ortlieb
14:25 – 14:50 (t,r)-Broadcast Domination in Networks, Gennaro Cordasco, Luisa Gargano and Adele Rescigno
14:50 – 15:05 Strategy Repair for Reachability Games, Pierre Gaillard, Fabio Patrizi and Giuseppe Perelli
15:05 – 15:20 Generalized Distance Polymatrix Games, Alessandro Aloisio, Michele Flammini and Cosimo Vinci
15:20 – 15:35 A two player asynchronous game with privacy constraints on Petri nets, Federica Adobbati, Luca Bernardinello and Lucia Pomello
15:35 – 15:50 Communication On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets, Davide Bilò, Giordano Colli, Luca Forlizzi and Stefano Leucci

15:50 – 16:20 Coffee Break

16:20 – 17:50 PANEL “The future of theoretical research in Computer sciance, between AI and quantum computing” – Panelists: A. Lieto, P. Sobocinsky – Chair: U. Dal Lago

20:00 – 22:00 CONFERENCE DINNER at Antico Ristorante Porto di Savona ( GMap)

September 13th

09:00 – 09:15 EATCS Prize Ceremony

09:15 – 10:15 Best Young Researcher – “No-Regret Learning in Bilateral Trade via Global Budget Balance”.
Abstract. Bilateral trade models the problem of intermediating between two rational agents – a seller and a buyer – both characterized by a private valuation for an item they want to trade. I will present a series of results on the online learning version of the problem, in which at each time step, a new seller and buyer arrive and the learner has to set prices for them without any knowledge about their (adversarially generated) valuations. The talk will focus on the impact of budget balance on learnability, detailing which notions of budget balance are needed to achieve sublinear regret for various types of data generation models.
Federico Fusco, Università “La Sapienza”, Roma – Chair: A. Montanari

10:00 – 10:30 Coffee Break

10:30 – 10:50 Best PhD Dissertation

10:50 – 13:00 Session n. 5 – LOGIC AND FORMAL METHODS – Chair: U. de’Liguoro

10:50 – 11:15 Proving the Existence of Stable Assignments in Democratic Forking Using Isabelle/HOL, Jan-Georg Smaus
11:15 – 11:40 ModalFP-Growth: Efficient Extraction of Modal Association Rules from Non-Tabular Data, Mauro Milella, Giovanni Pagliarini, Guido Sciavicco and Ionel Eduard Stan
11:40 – 12:05 Host-Core Calculi for non classical computations: a first insight, Matteo Palazzo, Luca Paolini, Luca Roversi and Margherita Zorzi
12:05 – 12:30 A process algebraic framework for multi-agent dynamic epistemic systems, Alessandro Aldini
12:30 – 12:45 Global Types for Agent Interaction Protocols, Federico Bergenti, Leonardo Galliera, Paola Giannini, Stefania Monica and Riccardo Nazzari
12:45 – 13:00 Simpson’s proof systems for process verification: A fine-tuning, Cosimo Perini Brogi, Rocco De Nicola and Omar Inverso

13:00 – 14:30 Lunch

14:30 – 16:00 Session n. 6 – LANGUAGES AND COMPUTATION 2 – Chair: A. Montanari

14:30 – 14:55 Improving Sampled Matching through Character Context Sampling, Simone Faro, Thierry Lecroq, Francesco Pio Marino, Arianna Pavone and Stefano Scafiti
14:55 – 15:20 A New Directly Accessible Compression Scheme, Simone Faro and Domenico Cantone
15:20 – 15:45 Some properties of the rate functions of large deviations for symbol statistics, Massimiliano Goldwurm and Marco Vignati
15:45 – 16:00 Maximum Letter-Duplicated Subsequence, Riccardo Dondi, Mohammad Mehdi Hosseinzadeh and Alexandru Popa

16:00 – 16:05 Closing ICTCS 2024

16:05 – 16:35 Coffee Break

16:45 – 18:45 City Guided Tour