Publications

Article

10.1007/s11139-024-01005-2

We consider Shanks’ simplest cubic fields K for which the index [O_K : Z[rho]] of a root rho of the defining parametric polynomial is 3. For them, we study the additive indecomposables of K and provide a complete list of them. Moreover, we use the knowledge of the indecomposables to prove some interesting consequences on the arithmetic of K. Mainly, we obtain good bounds on the ranks of universal quadratic forms over K and prove that the Pythagoras number of O_K is 6.

Proceedings paper

10.1007/978-981-96-0576-7_2

Organisations today heavily rely on complex software systems integrated through multiple layers of middleware. This complexity leads to substantial generation of operational data of structured and semi-structured formats which is recorded in log files. The workload of the system fluctuates according to specific periods of the day which impacts the amount and quality of data generated in log files. In this paper, we propose a new log anomaly detection approach that leverages a collection of smaller models designed to capture workload fluctuations over specific time intervals. We demonstrate its effectiveness in detecting anomalies within log streams. Our evaluation uses log data from servers in a production environment, handling a complex back-end system that processes hundreds of requests per second. We show that our method outperforms traditional and widely used anomaly detection methods in data streams in the context of dynamic and time-sensitive workload scenarios.

Article

10.1016/j.jnt.2024.12.001

We study a new connection between multidimensional continued fractions, such as Jacobi-Perron algorithm, and additively indecomposable integers in totally real cubic number fields. First, we find the indecomposables of all signatures in Ennola's family of cubic fields, and use them to determine the Pythagoras numbers. Second, we compute a number of periodic JPA expansions, also in Shanks' family of simplest cubic fields. Finally, we compare these expansions with indecomposables to formulate our conclusions.

Proceedings paper

10.1609/aaai.v39i13.33503

In the recently introduced model of fair partitioning of friends, there is a set of agents located on the vertices of an underlying graph that indicates the friendships between the agents. The task is to partition the graph into k balanced-sized groups, keeping in mind that the value of an agent for a group is equal to the number of edges they have in that group. The goal is to construct partitions that are "fair", i.e., no agent would like to replace an agent in a different group. We generalize the standard model by considering utilities for the agents that are beyond binary and additive. Having this as our foundation, our contribution is threefold: (a) we adapt several fairness notions that have been developed in the fair division literature to our setting; (b) we give several existence guarantees supported by polynomial-time algorithms; (c) we initiate the study of the computational (and parameterized) complexity of the model and provide an almost complete landscape of the (in)tractability frontier for our fairness concepts.

Article

10.1038/s41597-025-04603-x

Anomaly detection in network traffic is crucial for maintaining the security of computer networks and identifying malicious activities. Most approaches to anomaly detection use methods based on forecasting. Extensive real-world network datasets for forecasting and anomaly detection techniques are missing, potentially causing overestimation of anomaly detection algorithm performance and fabricating the illusion of progress. This manuscript tackles this issue by introducing a comprehensive dataset derived from 40 weeks of traffic transmitted by 275,000 active IP addresses in the CESNET3 network—an ISP network serving approximately half a million customers daily. It captures the behavior of diverse network entities, reflecting the variability typical of an ISP environment. This variability provides a realistic and challenging environment for developing forecasting and anomaly detection models, enabling evaluations that are closer to real-world deployment scenarios. It provides valuable insights into the practical deployment of forecast-based anomaly detection approaches.

Article

10.1016/j.cola.2024.101300

This paper explores how to reconstruct UML diagrams from dynamically typed languages such as Smalltalk, which do not use explicit type information. This lack of information makes traditional methods for extracting associations difficult. It addresses the need for automated techniques, particularly in legacy software systems, to facilitate their transformation into modern technologies, focusing on Smalltalk as a case study due to its extensive industrial legacy and modern adaptations like Pharo. We propose a way to create UML diagrams from Smalltalk code, focusing on using type inference to determine UML associations. For optimal outcomes for large-scale software systems, we recommend combining different type inference methods in an automatic or semi-automatic way.

Article

10.1002/jgt.23187

We study a counting version of Cycle Double Cover Conjecture. We discuss why it is more interesting to count circuits (i.e., graphs isomorphic to C_k for some k) instead of cycles (graphs with all degrees even). We give an almost-exponential lower bound for graphs with a surface embedding of representativity at least 4. We also prove an exponential lower bound for planar graphs. We conjecture that any bridgeless cubic graph has at least 2^(n/2 - 1) circuit double covers and we show an infinite class of graphs for which this bound is tight.

Proceedings paper

10.1007/978-3-031-85703-4_16

An efficient algorithm for enumerating representations of the unitary group U(3) that occur in a representation of the unitary group U(N) is introduced. The algorithm is applicable to U(N) representations associated with a system of nucleons distributed among the degenerate eigenstates of the selected three-dimensional harmonic oscillator level, where each eigenstate can be occupied by up to 4 particles with different combinations of spin and isospin quantum numbers. A C++ implementation of the proposed algorithm is provided, and its performance evaluation is reported.

Proceedings paper

Imagine we want to split a group of agents into teams in the most efficient way, considering that each agent has their own preferences about their teammates. This scenario is modeled by the extensively studied Coalition Formation problem. Here, we study a version of this problem where each team must additionally be of bounded size. We conduct a systematic algorithmic study, providing several intractability results as well as multiple exact algorithms that scale well as the input grows (FPT), which could prove useful in practice. Our main contribution is an algorithm that deals efficiently with tree-like structures (bounded treewidth) for "small" teams. We complement this result by proving that our algorithm is asymptotically optimal. Particularly, there can be no algorithm that vastly outperforms the one we present, under reasonable theoretical assumptions, even when considering star-like structures (bounded vertex cover number).

Article

n/a

Article

10.1016/j.eswa.2024.126187

The triplet-based odd-one-out problem, which involves trials where human subjects are asked to select the most different concept among three, is a well-studied task in cognitive sciences. With the release of a large triplet-based dataset, THINGS, there has been a recent surge in the popularity of machine learning models aimed at learning mathematical representations of object concepts, such as SPoSE, VICE, and CARE. The first two models learn representations by maximizing the similarity between the two most similar objects, while the latter diverges by directly learning the odd-one-out, making its embedding more distant. No prior attempts have integrated both paradigms, which are important for understanding object representation in cognitive science. In this paper, we propose MASTER, a multitask learning method for the triplet problem that encapsulates both paradigms. Our results demonstrate that our method not only better predicts the odd-one-out object but also provides insightful representations for studying these concepts. Furthermore, we studied the conditions under which each model performs better, offering valuable insights for future research on how these paradigms affect human understanding of object concepts.

Article

10.1002/jgt.23200

A graph is called odd (respectively, even) if every vertex has odd (respectively, even) degree. Gallai proved that every graph can be partitioned into two even induced subgraphs, or into an odd and an even induced subgraph. We refer to a partition into odd subgraphs as an odd colouring of G $G$. Scott proved that a connected graph admits an odd colouring if and only if it has an even number of vertices. We say that a graph G $G$ is k $k$-odd colourable if it can be partitioned into at most k $k$ odd induced subgraphs. The odd chromatic number of G $G$, denoted by chi odd( G ) ${\chi }_{\text{odd}}(G)$, is the minimum integer k $k$ for which G $G$ is k $k$-odd colourable. We initiate the systematic study of odd colouring and odd chromatic number of graph classes. We first consider a question due to Scott, which states that every graph G $G$ of even order n $n$ has chi odd( G ) <= c n ${\chi }_{\text{odd}}(G)\le c\sqrt{n}$, for some positive constant c $c$, by proving that this is indeed the case if G $G$ is restricted to having girth at least seven. We also show that any graph G $G$ whose all components have even order satisfies chi odd( G ) <= 2 Delta - 1 ${\chi }_{\text{odd}}(G)\le 2{\rm{\Delta }}-1$, where Delta ${\rm{\Delta }}$ is the maximum degree of G $G$. Next, we show that certain interesting classes have bounded odd chromatic number. Our main results in this direction are that interval graphs, graphs of bounded modular-width all have bounded odd chromatic number. In particular, every even interval graph is 6-odd colourable, and every even graph is 3 m w $3mw$-odd colourable, where m w $mw$ is the modular width of a graph.

Article

10.1090/proc/17019

The normed spaces of molecules constructed by Arens and Eells allow us to define two natural equivalence relations on the class of complete metric spaces. We say that two complete metric spaces M and N are M at- equivalent if their normed spaces of molecules are isomorphic and we say that they are .F- equivalent if the corresponding completions - the Lipschitz-free Banach spaces .F ( M ) and .F ( N ) - are isomorphic. In this note, we compare these and some other relevant equivalences of metric spaces. Clearly, M at-equivalent spaces are .F-equivalent. Our main result states that M at-equivalent spaces must have the same covering dimension. In combination with the work of Godard, this implies that M at-equivalence is indeed strictly stronger than .F-equivalence. However, M at-equivalent spaces need not be homeomorphic, as we demonstrate through a general construction. We also observe that M at-equivalence does not preserve the Assouad dimension. We introduce a natural notion of a free basis to simplify the notation.

Article

10.3390/heritage8010009

This paper presents a comprehensive study of the application of AI-driven in painting techniques to the restoration of historical photographs of the Czech city Most, with a focus on restoration and reconstructing the lost architectural heritage. The project combines state-of-the-art methods, including generative adversarial networks (GANs), patch-based inpainting, and manual retouching, to restore and enhance severely degraded images. The reconstructed/restored photographs of the city Most offer an invaluable visual representation of a city that was largely destroyed for industrial purposes in the 20th century. Through a series of blind and informed user tests, we assess the subjective quality of the restored images and examine how knowledge of edited areas influences user perception. Additionally, this study addresses the technical challenges of inpainting, including computational demands, interpretability, and bias in AI models. Ethical considerations, particularly regarding historical authenticity and speculative reconstruction, are also discussed. The findings demonstrate that AI techniques can significantly contribute to the preservation of cultural heritage, but must be applied with careful oversight to maintain transparency and cultural integrity. Future work will focus on improving the interpretability and efficiency of these methods, while ensuring that reconstructions remain historically and culturally sensitive.

Article

10.1088/1361-6382/adaabb

T-duality and its generalizations are widely recognized either as symmetries or solution-generating techniques in string theory. Recently introduced Jacobi-Lie T-plurality is based on Leibniz algebras whose structure constants f_{ab}^c, f_c^{ab}, Z_a, Z^a satisfy further conditions. Low dimensional Jacobi-Lie bialgebras were classified a few years ago. We study four- and six-dimensional algebras with structure constants f_b^{ba} = Z^a = 0 and show that there are several classes consisting of mutually isomorphic algebras. Using isomorphisms between Jacobi-Lie bialgebras we investigate three- and four-dimensional sigma models related by Jacobi-Lie T-plurality with and without spectators. In the Double Field Theory formulation constant generalized fluxes F_A are used in the literature to transform dilaton field. We extend the procedure to non-constant fluxes and verify that obtained backgrounds and dilatons solve Supergravity Equations. Most of the resulting backgrounds have vanishing curvature scalars and, as can be seen by finding Brinkmann coordinates, represent plane-parallel waves.

Proceedings paper

10.1007/978-3-031-85697-6_10

This paper presents PPQSort (Pattern Parallel Quicksort), a new parallel quicksort algorithm that provides high performance and ease of use. PPQSort uses C++ threads for parallelization, achieving efficient sorting without external libraries and allowing seamless inte- gration across different computing environments. This paper describes novel quicksort optimizations, including branchless partitioning and their efficient parallel implementation. PPQSort is compared with existing parallel quicksort algorithms on different machines and with different input data. Experimental evaluation results demonstrate that PPQSort is fast and robust, consistently outperforming the fastest available par- allel quicksort implementations for almost all inputs.

Proceedings paper

A divisible budget must be allocated to several projects, and agents are asked for their opinion on how much they would give to each project. We consider that an agent is satisfied by a division of the budget if, for at least a certain predefined number τ of projects, the part of the budget actually allocated to each project is at least as large as the amount the agent requested. The objective is to find a budget division that ``best satisfies'' the agents. In this context, different problems can be stated and we address the following ones. We study (i) the largest proportion of agents that can be satisfied for any instance, (ii) classes of instances admitting a budget division that satisfies all agents, (iii) the complexity of deciding if, for a given instance, every agent can be satisfied, and finally (iv) the question of finding, for a given instance, the smallest total budget to satisfy all agents. We provide answers to these complementary questions for several natural values of the parameter τ, capturing scenarios where we seek to satisfy for each agent all; almost all; half; or at least one of her requests.

Proceedings paper

The Mutliagent Path Finding (MAPF) problem consists of identifying the trajectories that a set of agents should follow inside a given network in order to reach their desired destinations as soon as possible, but without colliding with each other. We aim to minimize the maximum time any agent takes to reach their goal, ensuring optimal path length. In this work, we complement a recent thread of results that aim to systematically study the algorithmic behavior of this problem, through the parameterized complexity point of view. First, we show that MAPF is NP-hard when the given network has a star-like topology (bounded vertex cover number) or is a tree with 11 leaves. Both of these results fill important gaps in our understanding of the tractability of this problem that were left untreated in the recent work of [Fioravantes et al. Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology. AAAI'24]. Nevertheless, our main contribution is an exact algorithm that scales well as the input grows (FPT) when the topology of the given network is highly centralized (bounded distance to clique). This parameter is significant as it mirrors real-world networks. In such environments, a bunch of central hubs (e.g., processing areas) are connected to only few peripheral nodes.

Article

10.1515/itit-2024-0071

Two-level logic minimization is a well-established process that efficiently minimizes functions described in the Sum-of-Products (SOP) form. Current two-level SOP minimizes, like Espresso and Boom, produce optimum or near-optimum results regarding the SOP size. However, in this article we show that an SOP minimization conducted in the standard, multi-output way, significantly worsens the result of the subsequent multi-level synthesis, especially for sparsely-specified functions, regardless of the optimization process and the tool used. In conclusion, we propose using a single-output two-level SOP minimization for sparsely specified functions. In this way, the obtained circuits are sometimes multiple times smaller, while no significant deterioration has been observed for any other functions.

Book chapter

10.1002/9781394351930.ch5

This chapter presents and discusses the design and evaluation of Random number generators (RNGs) and the characteristics of the generated numbers required depending on their applications in cryptography - as cipher keys in block and stream ciphers, as prime numbers and asymmetric keys in public key cryptography, as nonces in Elliptic curve cryptography, and as random errors in post-quantum schemes. The cryptographic system is basically a deterministic system that implements algorithmic cryptographic primitives and protocols. In cryptography, designers look for sources of randomness that can be exploited in cryptographic systems. The security of the True RNG (TRNG) is also guaranteed by simple and fast online statistical tests that continuously or periodically test if the generator is operating correctly. The chapter practically illustrates the workflow of the TRNG design on a widely spread TRNG principle: generators that exploit the jitter of multiple free-running oscillators, for example, ring oscillators. © ISTE Ltd 2025. All rights reserved.