# Colloquium of Faculty of Informatics

The Informatics Colloquium takes place on Tuesday at 14:30 during the term time. The aim of the colloquia is to introduce state of the art research from all areas of computer science to the wide audience of the Faculty of Informatics.

#### Time and place

Tuesday 14:30–15:30, lecture hall A217, Faculty of Informatics Building

(speaker avaiable for informal discussion since around 14:00)

## Fall 2022 - schedule overview

On Tuesdays November 1 and November 15, there will be a series of talks given by our PhD students.

#### Maria Lujan Ganuza (Universidad Nacional del Sur, Argentina)

Lossless Multidimensional Visualization: an introductory talk

##### Tuesday 20 September 2022, 14:30, lecture hall A217

Visualization of multidimensional (n-D) datasets is a major challenge, as visualization methods must overcome the problem of mapping complex high-dimensional data into representations suitable for visualization. One way to approach this problem is to represent the data in a low-dimensional space. Thus, visualization techniques must provide low-dimensional representations but, at the same time, they must preserve certain properties of the structure of the dataset as faithfully as possible. In this talk, Dr. María Luján Ganuza will present her recent research lines related to this topic, including the exploration and implementation of General Lines Coordinates and the design of a novel visualization technique for analyzing eye movement data during the reading of micro-stories.

#### Daniel Ricardo Echeverri Giraldo (MUNI, CR)

Tangible Narratives: The Intersection of Performance, Interactivity, and Narrative

##### Tuesday 27 September 2022, 14:30, lecture hall A217

This presentation will look at two cases of Research through Design where design and computer science meet. It will briefly introduce Letters to José and The Non-Myth of the Noble Red, both tangible narratives. From the first case, the presentation will introduce a narrative architecture and a typology that frames the qualities of tangible artefacts with narrative meaning. Later, the presentation will introduce The Non-myth of the Noble Red, another design case which expands upon the learnings gained from the design of Letters to José. However, this second case also considers concepts and practices borrowed from the study of performative arts, in particular the work of Bertolt Brech. The true purpose of this presentation is to exemplify alternative approaches to enquiry where a designerly, creative, artistic, and experimental processes to research place the making of design artefacts at the ontological centre of the research. At the same time, the learning and insights stem not for the making of artefacts but FROM their making.

#### Tomáš Bureš (Charles University)

Towards ML-based architectural specification of collective adaptive systems

##### Tuesday 4 October 2022, 14:30, lecture hall A217

Collective adaptive systems is a class of systems composed of autonomic components or agents which collaborate and adapt towards a individual and group-level goals. The key property of these systems is that they are dynamic – i.e. their architecture undergoes constant change – and they are subject to uncertainty. This talk will show how the dynamic architecture of these systems can be described using the concepts of autonomic components and ensembles and how machine learning can be used to simplify the specification of these systems (especially with respect to uncertainty).

#### Jakub Šimko (Kempelen Institute of Intelligent Technologies, Slovakia)

Automatic Audits of Disinformation Spreading by Social Media Recommenders

##### Tuesday 18 October 2022, 14:30, lecture hall A217

The complex issue of disinformation spreading has its technological aspect. The recommender systems play an important (and unfortunately negative) role in this, as they overtake the information gatekeeping role of traditional media. Due to social media business models, recommender systems often prefer poor information quality or outright false content. In order to address this issue, we need to reliably quantify this phenomenon. However, this must not be done by social media themselves (e.g. as part of self-regulation), as they are the part of the problem. Instead, we need independent procedures and tools for real-world recommender systems assessment. In this talk, we will introduce the concept of automated audits of recommender systems, along with a case study done over YouTube's recommender system.

#### László Végh (London School of Economics, Great Britain)

Approximating Nash Social Welfare for Submodular Valuations

##### Tuesday 25 October 2022, 14:30, lecture hall A217

The Nash social welfare (NSW) problem asks for an allocation of indivisible items to agents in order to maximize the geometric mean of agents’ valuations. This is a common objective for fair division, representing a balanced tradeoff between the often conflicting requirements of fairness and efficiency. The problem is NP-complete already for additive valuation functions. We present a 22-approximation algorithm for the Nash Social Welfare problem under the general class submodular valuation functions. The previous best approximation factor for this setting was linear in the number of agents. We also consider the asymmetric variant of the problem where the objective is to maximize the weighted geometric mean of agents’ valuations, and give a 21+α approximation, where α is the ratio between largest weight and the average weight. This is joint work with Jugal Garg, Edin Husić, Wenzheng Li, and Jan Vondrák. It significantly improves and simplifies two previous papers (Garg, Husić, Végh, STOC 2021, and Li, Vondrák, FOCS 2021).

#### Zdeněk Matěj (MUNI, CR)

Development of digital technology and algorithms for measurements in particle accelerators and experimental nuclear reactors

##### Tuesday 8 November 2022, 14:30, lecture hall A217

With the development of digital technologies, there are many possibilities for their application in many fields. The combination of fast algorithms together with sufficiently powerful HW based mainly on programmable gate arrays (FPGA) expands the existing detection possibilities also in the field of nuclear experiments. This lecture will describe the development of digital devices for measuring neutrons and software for processing measured data, in which a team from the Faculty of Informatics of the MU participates. The device is mainly used in the field of nuclear experiments and is also used, for example, for research in the IV area. Generating nuclear reactors and improving nuclear data libraries.

#### Michal Pilipczuk (Warsaw University, Poland)

Structural graph theory through the lense of First Order logic

##### Tuesday 22 November 2022, 14:30, lecture hall A217

Structural graph theory provides a wealth of tools for describing structure in graphs that are helpful in designing efficient algorithms for graph problems. For instance, the graph minors theory of Robertson and Seymour gives an understanding of what it means to embed one graph in another "topologically", and therefore can be used to solve problems of topological nature. In this talk, we will be interested in problems that can be described in First Order logic on graphs. The goal will be to give a brief overview of recent attempts at constructing a new branch of structural graph theory which would be tailored to this kind of problems; this involves borrowing many concepts and techniques from model theory.

#### Jakub Lokoč (Charles University, CR)

Interactive search in image and video databases

##### Tuesday 29 November 2022, 14:30, lecture hall A217

We live in multimedia age, where visual information can be easily captured and shared by ordinary users. While image and video databases are booming in such age, search engines require more and more effective models enabling access to information stored in contents of the stored data. Although there have been many search models proposed so far, there still exist scenarios where users cannot solve their search needs. In cases a single retrieval model cannot help, there is an option to allow users to interact with the system to reach their goals. In the talk, several state-of-the-art models combining ranking and interactive feedback will be discussed. Several recent experiments will be presented as well, showing potential of these approaches and revealing future challenges in this area. The talk will end with a presentation of the Video Browser Showdown, a respected interactive video search competition.

## Presentations by local PhD students

#### Deniz Agaoglu

Automorphisms of Marked Cliques of an Interval Graph in FPT

##### Tuesday 1 November 2022, 14:30, lecture hall A217

We consider the following problem closely related to graph isomorphism. In a simplified version, the task is to compute the automorphism group of a given set family (or a hypergraph), that is, the group of all automorphisms of the given sets which are compatible with some permutation of their elements. In a general setting, the set family in question is a collection of cliques (called marked cliques) of a given interval graph, and the task is to compute the group of all permutations of the cliques which result from some automorphism of the underlying interval graph. This problem is obviously at least as hard as the graph isomorphism (GI-hard) already in the simplified version - consider the set family of edges of a graph, and we give an FPT-time algorithm parameterized by the maximum number of sets in the family which are incomparable by inclusion (its antichain size).

To our best knowledge the general version of the problem has not been formulated in the literature so far. The problem has been inspired by the
research of special cases of the isomorphism problem of chordal graphs; namely, the simplified set-family version is the core of our FPT algorithm for the
isomorphism of so-called S_{d}-graphs [MFCS 2020], and the general version extends and improves a cumbersome technical step in our FPT algorithm for the
isomorphism of chordal graphs of bounded leafage [WALCOM 2022]. The new algorithm combines two classical tools – PQ-trees of interval graphs and Babai’s tower-of-groups, in a nontrivial way.

#### David Klaška

Efficient Synthesis of Finite-Memory Strategies in Patrolling Games

##### Tuesday 1 November 2022, 15:00, lecture hall A217

Patrolling games, a subclass of security games, are played by two players, called the Defender and the Attacker. While the Defender moves inside a given graph, the Attacker chooses a vertex and initiates an attack there (e.g., starts cracking a safe), and the goal of the Defender is to discover the ongoing attack before it is completed. These games have found many applications, ranging from ticket inspection in Los Angeles to wildlife protection in Uganda. We investigate the strength of finite-memory strategies and propose an algorithm for their synthesis based on gradient descent. We also examine possible extensions of the presented model.

#### Pavol Ulbrich

3D is not enough: challenges in molecular visualization

##### Tuesday 15 November 2022, 14:30, lecture hall A217

In scientific visualization, the principle component for displaying molecular structures was the three-dimensional representation. However, for the purposes of modern observation, exploration, and analysis of molecular bodies, we need to go beyond the traditional approaches and experiment with innovative, abstract representations. In my talk, I will illustrate the alternative visualization methods for cases such as big molecular datasets, machine learning processing of molecular data, and long molecular dynamics.

#### David Wiesner

Efficient Synthesis of Microscopy Images for Medical Diagnosis

##### Tuesday 15 November 2022, 15:00, lecture hall A217

Artificial intelligence techniques have an increasing presence in healthcare. In particular, deep learning methods are capable of providing solutions to oncology-relevant tasks that are too time-consuming or even unsolvable using human effort and thus save time, money and, most importantly, lives. However, they are often inherently data-driven and therefore require a considerable amount of data samples to be trained and to produce outputs with reasonable accuracy. Suitable data sets are usually not freely available due to licensing restrictions or patient confidentiality. In our work, we focus on developing state-of-the-art methods capable of producing visually-plausible synthetic microscopy images in order to address the lack of available data sets. We begin with a simple generative model and explore further improvements to arrive at a computationally efficient solution capable of producing 3D microscopy image sequences in high spatial and temporal resolutions. We also explore the importance of evaluating the produced images in both a qualitative and quantitative manner.## Past colloquia

*Spring 2022*

*Autumn 2021*

*Spring 2021*

*Autumn 2020*

*Spring 2020*

*Autumn 2019*

*Spring 2019*

*Autumn 2018*

*Spring 2018*

*Autumn 2017*

*Spring 2017*

*Autumn 2016*

*Spring 2016*

*Autumn 2015*

*Spring 2015*

*Autumn 2014*

*Spring 2014*

*Autumn 2013*

*Spring 2013*

*Autumn 2012*

*Spring 2012*

*Autumn 2011*

*Spring 2011*

*Autumn 2010*

*Spring 2010*

*Autumn 2009*