Publications

Article

10.1002/jgt.23187

Department of Theoretical Computer Science

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

Department of Theoretical Computer Science

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

Proceedings paper

Department of Information Security

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

Department of Computer Systems

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

Department of Information Security

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

Department of Digital Design

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.

Article

10.1007/s43037-024-00333-1

Department of Applied Mathematics

The main aim of this paper is to provide characterizations of Birkhoff–James orthogonality (BJ-orthogonality in short) in a number of families of Banach spaces in terms of the elements of significant subsets of the unit ball of their dual spaces, which makes the characterizations more applicable. The tool to do so is a fine study of the abstract numerical range and its relation with the BJ-orthogonality. Among other results, we provide a characterization of BJ-orthogonality for spaces of vector-valued bounded functions in terms of the domain set and the dual of the target space, which is applied to get results for spaces of vector-valued continuous functions, uniform algebras, Lipschitz maps, injective tensor products, bounded linear operators with respect to the operator norm and to the numerical radius, multilinear maps, and polynomials. Next, we study possible extensions of the well-known Bhatia–Šemrl theorem on BJ-orthogonality of matrices, showing results in spaces of vector-valued continuous functions, compact linear operators on reflexive spaces, and finite Blaschke products. Finally, we find applications of our results to the study of spear vectors and spear operators. We show that no smooth point of a Banach space can be BJ-orthogonal to a spear vector of Z. As a consequence, if X is a Banach space containing strongly exposed points and Y is a smooth Banach space with dimension at least two, then there are no spear operators from X to Y. Particularizing this result to the identity operator, we show that a smooth Banach space containing strongly exposed points has numerical index strictly smaller than one. These latter results partially solve some open problems.

Article

10.1016/j.dib.2024.110389

Department of Computer Systems

Using a user DNS fingerprint allows one to identify a specific network user regardless of the knowledge of his IP address. This method is proper, for example, when examining the behavior of a monitored network user in more depth. In contrast to other studies, this work introduces a dataset for possible user identification based only on the knowledge of its DNS fingerprint created from the previously sent DNS queries. We created a large dataset from the real network traffic of a metropolitan Internet service provider. The dataset was created from 2.3 billion DNS queries representing 6.2 million different domain names. The data collection took place over three months from 12/2023 to 02/2024. The dataset contains a detailed user activity description in the sense of overall daily activity statistics and detailed 24 h activity statistics. Each dataset record contains a list of 1137 classification attributes. The absolutely unique feature of this data set is the classification of user activity based on categories of content accessed by a user. The new dataset can be used for the creation of machine learning models, allowing the identification of a specific user without direct knowledge of their IP addresses or additional network location information. The dataset can also serve as a reference dataset for the creation of DNS fingerprints of users.

Article

10.1103/PhysRevC.109.014616

Department of Computer Systems

We combine the ab initio symmetry-adapted no-core shell model (SA-NCSM) with the single-particle Green's function approach to construct optical potentials rooted in first principles. Specifically, we show that total cross sections and phase shifts for neutron elastic scattering from a 4He target with projectile energies between 0.5 and 10 MeV closely reproduce the experiment. In addition, we discuss an important new development that resolves a long-standing issue with spurious center-of-mass motion in the Green's function formalism for many-body approaches. The new development opens a path for first-principle predictions of cross sections for elastic scattering of single-nucleon projectiles, nucleon capture, and deuteron breakup reactions, feasible for a broad range of open-shell spherical and deformed nuclei in the SA-NCSM approach.

Article

10.1088/1748-0221/19/08/P08018

Department of Computer Systems

The identification of top quark decays where the top quark has a large momentum transverse to the beam axis, known as top tagging, is a crucial component in many measurements of Standard Model processes and searches for beyond the Standard Model physics at the Large Hadron Collider. Machine learning techniques have improved the performance of top tagging algorithms, but the size of the systematic uncertainties for all proposed algorithms has not been systematically studied. This paper presents the performance of several machine learning based top tagging algorithms on a dataset constructed from simulated proton-proton collision events measured with the ATLAS detector at √s = 13 TeV. The systematic uncertainties associated with these algorithms are estimated through an approximate procedure that is not meant to be used in a physics analysis, but is appropriate for the level of precision required for this study. The most performant algorithms are found to have the largest uncertainties, motivating the development of methods to reduce these uncertainties without compromising performance. To enable such efforts in the wider scientific community, the datasets used in this paper are made publicly available.

Proceedings paper

10.5220/0012385600003636

Department of Applied Mathematics

This paper addresses exact approaches to multi-agent collective construction problem which tasks a group of cooperative agents to build a given structure in a blocksworld under the gravity constraint. We propose a generalization of the existing exact model based on mixed integer linear programming by accommodating varying agent action durations. We refer to the model as a fraction-time model. The introduction of action durations enables one to create a more realistic model for various domains. It provides a significant reduction of plan execution duration at the cost of increased computational time, which rises steeply the closer the model gets to the exact real-world action duration. We also propose a makespan estimation function for the fraction-time model. This can be used to estimate the construction time reduction size for cost-benefit analysis. The fraction-time model and the makespan estimation function have been evaluated in a series of experiments using a set of benchmark st ructures. The results show a significant reduction of plan execution duration for non-constant duration actions due to decreasing synchronization overhead at the end of each action. According to the results, the makespan estimation function provides a reasonably accurate estimate of the makespan.

Proceedings paper

10.1109/DDECS60919.2024.10508927

Department of Digital Design

Neural networks with quantized activation functions cannot adapt the quantization at the input of their first layer. Preprocessing is therefore required to adapt the range of input data to the quantization range. Such preprocessing usually includes an activation-wise linear transformation and is steered by the properties of the training set. We suggest to include the linear transform into the training process. We document that it improves accuracy, requires the same resources as standard preprocessing, plays a role in network pruning, and is reasonably stable with respect to initialization.

Proceedings paper

10.24963/ijcai.2024/304

Department of Theoretical Computer Science

We develop a general, formal model of social choice in which voters have continuous preferences over a one-dimensional space. Our model is parameterized by different restrictions that we introduce regarding the way voter preferences change in time as well as the optimization criteria (that correspond to a normative continuum of fairness definitions) desired from an aggregation method—that outputs a continuous, one-dimensional curve—given such inputs. We discuss the applicability of the model to different real-world situations and, as a first step towards an analysis of the different model realizations, we concentrate on identifying those cases that are computationally feasible to compute.

Proceedings paper

10.1109/NOMS59830.2024.10575630

Department of Digital Design

This study investigates the evolving landscape of network traffic monitoring, which is crucial for maintaining computer network services and security. Traditional methods like Deep Packet Inspection (DPI) face challenges due to increased privacy protection through encryption, prompting a shift towards statistical-based detection using Machine Learning (ML). On the other hand, ML struggles with long-term evaluation due to various distribution changes. This study focuses on the CESNET-TLS-Year22 dataset, derived from one year of TLS network traffic on the CESNET2 backbone. Described research explores the behavior of modern protocols in real-world scenarios and their impact on dataset quality. The main result of our analysis is the identification of the Weekend phenomenon in network traffic classification that is generally overlooked during ML model training.

Proceedings paper

Department of Digital Design

This study investigates the evolving landscape of network traffic monitoring, which is crucial for maintaining computer network services and security. Traditional methods like Deep Packet Inspection (DPI) face challenges due to increased privacy protection through encryption, prompting a shift towards statistical-based detection using Machine Learning (ML). On the other hand, ML struggles with long-term evaluation due to various distribution changes. This study focuses on the CESNET-TLS-Year22 dataset, derived from one year of TLS network traffic on the CESNET2 backbone. Described research explores the behavior of modern protocols in real-world scenarios and their impact on dataset quality. The main result of our analysis is the identification of the Weekend phenomenon in network traffic classification that is generally overlooked during ML model training.

Article

10.1038/s41598-024-63549-z

Department of Applied Mathematics

Men with writing proficiency enjoyed a privileged position in ancient Egyptian society in the third millennium BC. Research focusing on these officials of elevated social status ("scribes") usually concentrates on their titles, scribal statues, iconography, etc., but the individuals themselves, and their skeletal remains, have been neglected. The aim of this study is to reveal whether repetitive tasks and maintained postures related to scribal activity can manifest in skeletal changes and identify possible occupational risk factors. A total of 1767 items including entheseal changes, non-metric traits, and degenerative changes were recorded from the human remains of 69 adult males of well-defined social status categories from the necropolis at Abusir (2700-2180 BC). Statistically significant differences between the scribes and the reference group attested a higher incidence of changes in scribes and manifested themselves especially in the occurrence of osteoarthritis of the joints. Our research reveals that remaining in a cross-legged sitting or kneeling position for extended periods, and the repetitive tasks related to writing and the adjusting of the rush pens during scribal activity, caused the extreme overloading of the jaw, neck and shoulder regions.

Article

10.1007/s00236-023-00451-7

Department of Theoretical Computer Science

We present a new FPTAS for the SUBSET SUM RATIO problem, which, given a set of integers, asks for two disjoint subsets such that the ratio of their sums is as close to 1 as possible. Our scheme makes use of exact and approximate algorithms for PARTITION, and clearly showcases the close relationship between the two algorithmic problems. Depending on the relationship between the size of the input set n and the error margin \espilon, we improve upon the best currently known algorithm of Melissinos and Pagourtzis [COCOON 2018] of complexity O(n^4/\espilon). In particular, the exponent of n in our proposed scheme may decrease down to 2, depending on the PARTITION algorithm used.

Article

10.1016/j.jfa.2024.110655

Department of Applied Mathematics

Let A and B be C⁎-algebras with A separable, let I be an ideal in B, and let ψ:A→B/I be a completely positive contractive linear map. We show that there is a continuous family Θt:A→B, for t∈[1,∞), of lifts of ψ that are asymptotically linear, asymptotically completely positive and asymptotically contractive. If ψ is of order zero, then Θt can be chosen to have this property asymptotically. If A and B carry continuous actions of a second countable locally compact group G such that I is G-invariant and ψ is equivariant, we show that the family Θt can be chosen to be asymptotically equivariant. If a linear completely positive lift for ψ exists, we can arrange that Θt is linear and completely positive for all t∈[1,∞). In the equivariant setting, if A, B and ψ are unital, we show that asymptotically linear unital lifts are only guaranteed to exist if G is amenable. This leads to a new characterization of amenability in terms of the existence of asymptotically equivariant unital sections for quotient maps.

Article

10.1007/JHEP05(2024)106

Department of Computer Systems

A summary of the constraints from searches performed by the ATLAS collaboration for the electroweak production of charginos and neutralinos is presented. Results from eight separate ATLAS searches are considered, each using 140 fb(-1) of proton-proton data at a centre-of-mass energy of root s = 13TeV collected at the Large Hadron Collider during its second data-taking run. The results are interpreted in the context of the 19-parameter phenomenological minimal supersymmetric standard model, where R-parity conservation is assumed and the lightest supersymmetric particle is assumed to be the lightest neutralino. Constraints from previous electroweak, flavour and dark matter related measurements are also considered. The results are presented in terms of constraints on supersymmetric particle masses and are compared with limits from simplified models. Also shown is the impact of ATLAS searches on parameters such as the dark matter relic density and the spin-dependent and spin-independent scattering cross-sections targeted by direct dark matter detection experiments. The Higgs boson and Z boson 'funnel regions', where a low-mass neutralino would not oversaturate the dark matter relic abundance, are almost completely excluded by the considered constraints. Example spectra for non-excluded supersymmetric models with light charginos and neutralinos are also presented.

Article

10.1016/j.physrep.2024.09.002

Department of Computer Systems

This report reviews the published results of searches for possible additional scalar particles and exotic decays of the Higgs boson performed by the ATLAS Collaboration using up to 140 fb−1 of 13 TeV proton–proton collision data collected during Run 2 of the Large Hadron Collider. Key results are examined, and observed excesses, while never statistically compelling, are noted. Constraints are placed on parameters of several models which extend the Standard Model, for example by adding one or more singlet or doublet fields, or offering exotic Higgs boson decay channels. Summaries of new searches as well as extensions of previous searches are discussed. These new results have a wider reach or attain stronger exclusion limits. New experimental techniques that were developed for these searches are highlighted. Search channels which have not yet been examined are also listed, as these provide insight into possible future areas of exploration.