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.

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.

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

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.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

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.

Article

10.1016/j.camwa.2024.12.017

We present efficient MATLAB implementations of the lowest-order primal hybrid finite element method (FEM) for linear second-order elliptic and parabolic problems with mixed boundary conditions in two spatial dimensions. We employ backward Euler and the Crank-Nicolson finite difference scheme for the complete discrete setup of the parabolic problem. All the codes presented are fully vectorized using matrix-wise array operations. Numerical experiments are conducted to show the performance of the software.

Proceedings paper

10.5220/0013314100003899

The security primitives, such as True-Random-Number-Generator (TRNG) or Physically-Unclonable-Function (PUF), are widely used in many cryptographic devices. Properties of these primitives affect the security, reliability, and longevity of the whole device. In this work, we evaluate the influence of the total ionizing X-ray dose on hardware structures underlying conventional SRAM-based security primitives – PUF and TRNG. In contrast with other works, we aim with conventional CMOS circuits, we employ lower total ionizing dose (TID) levels, and we also take annealing into account. We quantify the induced changes in SRAM cell entropy, provide a quality analysis of related physical effects, summarize potential effects on both security primitives. Besides analyzing the experimental data, we explain experimental data by comparison to the electrical-level (SPICE) model of SRAM cells taking X-ray-induced effects – flicker noise and threshold shift – into account. Our comparative analysis poin ts to inconsistencies and deficiencies in related literature and provides a view into effects affecting observed entropy. The novelty of our work is in the comparative analysis of experimental data combined with low-level electrical model, which is the enabler of the qualitative analysis. Our results form the basis for future work.

Proceedings paper

Implementing cryptographic standards is a critical process for the cryptographic ecosystem. Cryptographic standards aim to support developers and engineers in implementing cryptographic primitives and protocols. However, past security incidents suggest that implementing cryptographic standards can be challenging and might jeopardize software and hardware security. We need to understand and mitigate the pain points of those implementing cryptographic standards to support them better. To shed light on the challenges and obstacles of implementing cryptographic standards, we conducted 20 semi-structured interviews with experienced cryptographers and cryptographic software engineers. We identify common practices when implementing standards, including the criticality of reference and third-party implementations, test vectors to verify implementations, and the open standard community as central support for questions and reviews of implementations. Based on our findings, we recommend transparent standardization processes, strong (ideally formal) verification, improved support for comparing implementations, and covering updates and error handling in the standardization process.

Proceedings paper

10.1109/ACIT62333.2024.10712488

In this paper, we present a software architecture for mathematical modeling based on the analysis of interval data using cloud technologies. The key features of the proposed architecture include the integration of an interval modeling subsystem for static systems into a cloud-based service-oriented architecture, optimization of computational schemes using the Google Cloud Run platform, the use of the MapReduce distributed computing model, free software-interpreted tools, and the application of RESTful APIs at all stages of mathematical modeling.

Article

10.1007/s11416-024-00519-z

Machine learning has proven to be a valuable tool for automated malware detection, but machine learning systems have also been shown to be subject to adversarial attacks. This paper summarizes and compares related work on generating adversarial malware samples, specifically malicious Windows Portable Executable files. In contrast with previous research, we not only compare generators of adversarial malware examples theoretically, but we also provide an experimental comparison and evaluation for practical usability. We use gradient-based, evolutionary-based, and reinforcement-based approaches to create adversarial samples, which we test against selected antivirus products. The results show that applying optimized modifications to previously detected malware can lead to incorrect classification of the file as benign. Moreover, generated malicious samples can be effectively employed against detection models other than those used to produce them, and combinations of methods can construct new instances that avoid detection. Based on our findings, the Gym-malware generator, which uses reinforcement learning, has the greatest practical potential. This generator has the fastest average sample production time of 5.73 s and the highest average evasion rate of 44.11%. Using the Gym-malware generator in combination with itself further improved the evasion rate to 58.35%. However, other tested methods scored significantly lower in our experiments than reported in the original publications, highlighting the importance of a standardized evaluation environment.

Proceedings paper

10.1109/DDECS60919.2024.10508902

Small quantized neural networks with strong requirements on throughput and latency can be translated into combinational logic circuits and synthesized by logic design tools. To capture the function of the network (or a part of it) as a logic function, two approaches have been taken. The first one observes the inputs and outputs, while the network predicts a training set, and uses them directly as specification. The response to activation values that have not occurred in the training set remain unspecified. The other approach uses a complete set of activation values at the input of the examined part. Our study aims to quantify the inaccuracy of the first method, the influence of logic minimization used on accuracy, and the impact on the final synthesized circuit. We also document the quantitative changes in quantized networks.