Flexing infinite frameworks with applications to braced Penrose tilings

Authors
Dewar, S.; Legerský, J.
Year
2023
Published
Discrete Applied Mathematics. 2023, 324 1-17. ISSN 0166-218X.
Type
Article
Annotation
A planar framework – a graph together with a map of its vertices to the plane – is flexible if it allows a continuous deformation preserving the distances between adjacent vertices. Extending a recent previous result, we prove that a connected graph with a countable vertex set can be realized as a flexible framework if and only if it has a so-called NAC-coloring. The tools developed to prove this result are then applied to frameworks where every 4-cycle is a parallelogram, and countably infinite graphs with n-fold rotational symmetry. With this, we determine a simple combinatorial characterization that determines whether the 1-skeleton of a Penrose rhombus tiling with a given set of braced rhombi will have a flexible motion, and also whether the motion will preserve 5-fold rotational symmetry.

Polynomial kernels for tracking shortest paths

Year
2023
Published
Information Processing Letters. 2023, 179(1), ISSN 1872-6119.
Type
Article
Annotation
Given an undirected graph G = (V , E), vertices s,t ∈ V , and an integer k, Tracking Shortest Paths requires deciding whether there exists a set of k vertices T ⊆ V such that for any two distinct shortest paths between s and t, say P1 and P2, we have T ∩ V (P1) != T ∩ V (P2). In this paper, we give the first polynomial size kernel for the problem. Specifically we show the existence of a kernel with O(k2) vertices and edges in general graphs and a kernel with O(k) vertices and edges in planar graphs for the Tracking Paths in DAG problem. This problem admits a polynomial parameter transformation to Tracking Shortest Paths, and this implies a kernel with O(k4) vertices and edges for Tracking Shortest Paths in general graphs and a kernel with O(k2) vertices and edges in planar graphs. Based on the above we also give a single exponential algorithm for Tracking Shortest Paths in planar graphs.

A Comprehensive Survey on the Non-Invasive Passive Side-Channel Analysis

Year
2022
Published
Sensors. 2022, 22(21), ISSN 1424-8220.
Type
Article
Annotation
Side-channel analysis has become a widely recognized threat to the security of cryptographic implementations. Different side-channel attacks, as well as countermeasures, have been proposed in the literature. Such attacks pose a severe threat to both hardware and software cryptographic implementations, especially in the IoT environment where the attacker may easily gain physical access to a device, leaving it vulnerable to tampering. In this paper, we provide a comprehensive survey regarding the non-invasive passive side-channel analysis. We describe both non-profiled and profiled attacks, related security metrics, countermeasures against such attacks, and leakage-assessment methodologies, as available in the literature of more than twenty years of research.

A Design Space Exploration Framework for Memristor-Based Crossbar Architecture

Authors
Barbareschi, M.; Bosio, A.; O'Connor, I.; Fišer, P.; Traiola, M.
Year
2022
Published
Proceedings of the 2022 25th International Symposium on Design and Diagnostics of Electronic Circuits and Systems (DDECS). Piscataway: IEEE, 2022. p. 38-43. ISSN 2473-2117. ISBN 978-1-6654-9431-1.
Type
Proceedings paper
Annotation
In the literature, there are few studies describing how to implement Boolean logic functions as a memristor-based crossbar architecture and some solutions have been actually proposed targeting back-end synthesis. However, there is a lack of methodologies and tools for the synthesis automation. %More in detail, what is missing is a methodology able to optimize a given Boolean logic function for the memristor-based implementation. The main goal of this paper is to perform a Design Space Exploration (DSE) in order to analyze and compare the impact of the most used optimization algorithms on a memristor-based crossbar architecture. %The synthesized circuits are quantified in terms of area, energy consumption, and performance. The results carried out on 102 circuits lead us to identify the best optimization approach, in terms of area/energy/delay. The presented results can also be considered as a reference (benchmarking) for comparing future work.

A fair experimental evaluation of distance correlation side-channel distinguisher

Year
2022
Published
Proceedings of the 11th Mediterranean Conference on Embedded Computing (MECO 2022). Institute of Electrical and Electronics Engineers, Inc., 2022. p. 110-113. ISSN 2637-9511. ISBN 978-1-6654-6828-2.
Type
Proceedings paper
Annotation
Side-channel attacks pose a severe threat to crypto graphic implementations, allowing the attacker to recover secret information based on physical observations of the cryptographic device. Correlation Power Analysis is considered to be one of the most powerful attacks in the non-profiled scenario. In this paper, we consider the distance/Brownian correlation instead of the traditionally used Pearson coefficient. We give a fair comparison of our novel approach attacking AES on three different FPGA platforms and we discuss the distance correlation potential in the context of side-channel analysis.

A Survey of Guidelines and Best Practices for the Generation, Interlinking, Publication, and Validation of Linguistic Linked Data

Authors
Khan, A.F.; Chiarcos, C.; Declerck, T.; Buono, M.P.; Dojčinovski, M.; Gracia, J.; Oleskeviciene, G.V.; Gifu, D.
Year
2022
Published
Proceedings of LDL 2022. Paris: ELRA, 2022. p. 1-9.
Type
Proceedings paper
Annotation
This article discusses a survey carried out within the NexusLinguarum COST Action which aimed to give an overview of existing guidelines (GLs) and best practices (BPs) in linguistic linked data. In particular it focused on four core tasks in the production/publication of linked data: generation, interlinking, publication, and validation. We discuss the importance of GLs and BPs for LLD before describing the survey and its results in full. Finally we offer a number of directions for future work in order to address the findings of the survey.

Ab initio View of Emergent Symplectic Symmetry and Its Crutial Role in Nuclear Dynamics

Authors
Dytrych, T.; Launey, K.D.; Draayer, J.P.; Langr, D.
Year
2022
Published
Bulgarian Journal of Physics. 2022, 49(1), 37-46. ISSN 1310-0157.
Type
Article
Annotation
Results of large-scale first principle nuclear structure studies using the symmetry-adapted no-core shell model are reported. It is shown that nuclei up through the intermediate-mass region display highly regular and ubiquitous patterns of dominant nuclear shapes that vibrate and rotate. This emergent structure is tied to an approximate symplectic Sp (3, R) symmetry, and it is shown to determine dominant features of low-lying states, even in close-to-spherical nuclear states without any recognizable rotational properties.

Accepted Tutorials at The Web Conference 2022

Authors
Tommasini, R.; Roy, S.B.; Wang, X.; Dojčinovski, M.
Year
2022
Published
Companion Proceedings of the Web Conference 2022. New York: Association for Computing Machinery, 2022. p. 391-399. ISBN 978-1-4503-9130-6.
Type
Proceedings paper
Annotation
This paper summarizes the content of the 20 tutorials that have been given at The Web Conference 2022: 85% of these tutorials are lecture style, and 15% of these are hands on.

Approximate arithmetic for modern neural networks and FPGAs

Year
2022
Published
Proceedings of the 11th Mediterranean Conference on Embedded Computing (MECO 2022). Institute of Electrical and Electronics Engineers, Inc., 2022. p. 357-360. ISSN 2637-9511. ISBN 978-1-6654-6828-2.
Type
Proceedings paper
Annotation
Approximate arithmetic is a very important approach for implementing neural networks in embedded hardware. The requirements of real-time applications with respect to the size of deep neural networks force designers to simplify the neural processing elements. Not only the reduction of precision of model parameters to a few bits, but also the use of approximate arithmetic increases computational power and saves on-chip resources beyond exact computation. Since it was shown that linearly approximated functions are suitable for implementing neural networks in hardware, FPGAs have improved. So we decided to re-implement the processing element on a modern FPGA and to present implementation results regarding speed and resource consumption. A neural processing element based on linearly approximated functions was implemented in Vivado and tested on an xc7 FPGA. The results show that the architecture saves significant resources and a clock frequency above 100 MHz can be achieved in pipelined design.

Automatic Detection and Decryption of AES Using Dynamic Analysis

Authors
Kokeš, J.; Matějka, J.; Lórencz, R.
Year
2022
Published
SN Computer Science. 2022, 2022 ISSN 2662-995X.
Type
Article
Annotation
In this paper we propose a set of algorithms that can automatically detect the use of AES and automatically recover both the encryption key and the plaintext, assuming that we can control the code flow of the encrypting program, e.g., when an application is performing encryption without the user’s permission. The first algorithm makes use of the fact that we can monitor accesses to the AES S-Box and deduce the desired data from these accesses; the approach is suitable to software-based AES implementations, both naïve and optimized. To demonstrate the feasibility of this approach we designed a tool which implements the algorithm for Microsoft Windows running on the Intel x86 architecture. The tool has been successfully tested against a set of applications using different cryptographic libraries and common user applications. We also discuss the options of recovering the same data when hardware-assisted AES implementations on Intel-compatible architectures are used.

Balancing the Spread of Two Opinions in Sparse Social Networks (Student Abstract)

Year
2022
Published
Proceedings of the 36th AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2022. p. 12987-12988. ISSN 2159-5399. ISBN 978-1-57735-876-3.
Type
Proceedings paper
Annotation
We propose a new discrete model for simultaneously spreading two opinions within a social network inspired by the famous Target Set Selection problem. We are given a social network, a seed-set of agents for each opinion, and two thresholds per agent. The first threshold represents the willingness of an agent to adopt an opinion if she has no opinion at all, while the second threshold states the readiness to acquire a second opinion. The goal is to add as few agents as possible to the initial seed-sets such that, once the process started with these seed-set stabilises, each agent has either both opinions or none. We perform an initial study of its computational complexity. It is not surprising that the problem is NP-hard even in quite restricted settings. Therefore, we investigate the complexity of the problem from the parameterized point-of-view with special focus on sparse networks, which appears often in practice. Among other things, we show that the proposed problem is in the FPT complexity class if we parameterize by the vertex cover number of the underlying graph.

BDDC for MHFEM discretization of unsteady two-phase flow in porous media

Authors
Solovský, J.; Fučík, R.; Šístek, J.
Year
2022
Published
Computer Physics Communications. 2022, 271 ISSN 0010-4655.
Type
Article
Annotation
This work deals with the application of the Balancing Domain Decomposition by Constrains (BDDC) method to unsteady two-phase flow problems in porous media. We briefly describe the spatial discretization of the problem which is based on the mixed-hybrid finite element method (MHFEM) and semi-implicit time discretization. Then, we describe the BDDC method, in detail discuss the differences between the symmetric and nonsymmetric cases, and present the necessary modifications of the algorithm for the more complicated nonsymmetric case. We describe the parallel implementation of the method and highlight the critical steps of the algorithm that affect the performance and scalability. The parallel implementation is then tested on benchmark problems in 2D and 3D and its efficiency is investigated on various meshes. The numerical results indicate that the method preserves good computational efficiency for increasing number of processes and, therefore, allows solving problems on very fine meshes. In the case of unsteady problem, additional speed-up is achieved using the information from previous time steps for the solution in the current time step.

Bracing frameworks consisting of parallelograms

Authors
Grasegger, G.; Legerský, J.
Year
2022
Published
The Art of Discrete and Applied Mathematics. 2022, 5(2), 1-21. ISSN 2590-9770.
Type
Article
Annotation
A rectangle in the plane can be continuously deformed preserving its edge lengths, but adding a diagonal brace prevents such a deformation. Bolker and Crapo characterized combinatorially which choices of braces make a grid of squares infinitesimally rigid using a bracing graph: a bipartite graph whose vertices are the columns and rows of the grid, and a row and column are adjacent if and only if they meet at a braced square. Duarte and Francis generalized the notion of the bracing graph to rhombic carpets, proved that the connectivity of the bracing graph implies rigidity and stated the other implication without proof. Nagy Kem gives the equivalence in the infinitesimal setting. We consider continuous deformations of braced frameworks consisting of a graph from a more general class and its placement in the plane such that every 4-cycle forms a parallelogram. We show that rigidity of such a braced framework is equivalent to the non-existence of a special edge coloring, which is in turn equivalent to the corresponding bracing graph being connected.

Classification of network traffic

Year
2022
Published
Proceedings of the 10th Prague Embedded Systems Workshop. Praha: CTU. Faculty of Information Technology, 2022. p. 52-58. ISBN 978-80-01-07015-4.
Type
Proceedings paper
Annotation
This paper describes the context of existing approaches to real-time net- work flow classification and focuses on the contributions of bachelor and master thesis of the author. The paper also proposes several research questions that are planned for the future Ph.D. study.

CONCEPTS OF OPERATING SYSTEMS COURSES

Year
2022
Published
Informatika 2022 - Sborník příspěvků. Jihlava: Vysoká škola polytechnická Jihlava, 2022. p. 1-62.
Type
Proceedings paper
Annotation
In this article we discuss concepts of FIT CTU in Prague. Courses covering area of operating systems (OS). We present objectives of individual courses, synopses, syllabuses of lectures and tutorials, content relations between courses. Other courses having content interference with desribed courses are discussed. We propose new courses with content not currently covered by existing OS courses.

Controlling the Spread of Two Secrets in Diverse Social Networks (Student Abstract)

Year
2022
Published
Proceedings of the 36th AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2022. p. 12919-12920. ISSN 2159-5399. ISBN 978-1-57735-876-3.
Type
Proceedings paper
Annotation
nformation diffusion in social networks is a well-studied concept in social choice theory. We propose the study of the diffusion of two secrets in a heterogeneous environment from the complexity perspective, that is, there are two different networks with the same set of agents (e.g., the structure of the set of followers might be different in two distinct social networks). Formally, our model combines two group identification processes for which we do have independent desiderata---either constructive, where we would like a given group of agents to be exposed to a secret, or destructive, where a given group of agents should not be exposed to a secret. To be able to reach these targets, we can either delete an agent or introduce a previously latent agent. Our results are mostly negative---all of the problems are NP-hard. Therefore, we propose a parameterized study with respect to the natural parameters, the number of influenced agents, the size of the required/protected agent sets, and the duration of the diffusion process. Most of the studied problems remain W[1]-hard even for a combination of these parameters. We complement these results with nearly optimal XP algorithms.

Correlation Power Analysis of SipHash

Authors
Olekšák, M.; Miškovský, V.
Year
2022
Published
Proceedings of the 2022 25th International Symposium on Design and Diagnostics of Electronic Circuits and Systems (DDECS). Piscataway: IEEE, 2022. p. 84-87. ISSN 2473-2117. ISBN 978-1-6654-9431-1.
Type
Proceedings paper
Annotation
SipHash is ARX-based pseudorandom function optimized for short inputs. It was developed as a hash table lookup function, but it is also used for MAC generation. At the time of writing, there was no side-channel attack on SipHash known to us. This work is about application of CPA attack on SipHash. Attack was performed on ChipWhisperer CW308 UFO Board with STM32F0 target. Approximately 800 power traces were needed for succesful attack. Leakage information from XOR was used to attack cipher key. The main contribution of this work is power model of binary addition including carry propagation.

CPP11sort: A parallel quicksort based on C++ threading

Authors
Langr, D.; Schovánková, K.
Year
2022
Published
Concurrency and Computation: Practice and Experience. 2022, 34(4), 1-11. ISSN 1532-0626.
Type
Article
Annotation
A new efficient implementation of the multi-threaded quicksort algorithm called CPP11sort is presented. This implementation is built exclusively upon the threading primitives of the C++ programming language itself. The performance of CPP11sort is evaluated and compared with its mainstream competitors provided by GNU, Intel, and Microsoft. It is shown that out of the considered implementations, CPP11sort mostly yields the shortest sorting times and is the only one that is portable to any conforming C++ implementation without a need of external libraries or non-standard compiler extensions. The experimental evaluation with various input data distributions resulted in parallel speedup between 16.1 and 44.2 on a 56-core server and between 6.8 and 14.5 on a 10-core workstation with enabled hyper-threading.

Cultural Diversity and Its Impact on Governance

Authors
Evan, T.; Holý, V.
Year
2022
Published
International Journal of Intercultural Relations. 2022, ISSN 0147-1767.
Type
Article
Annotation
Hofstede’s six cultural dimensions make it possible to measure the culture of countries but are criticized for assuming the homogeneity of each country. In this paper, we propose two measures based on Hofstede’s cultural dimensions which take into account the heterogeneous structure of citizens with respect to their countries of origin. Using these improved measures, we study the influence of heterogeneous culture and cultural diversity on the quality of institutions measured by the six worldwide governance indicators. We use a linear regression model allowing for dependence in spatial and temporal dimensions as well as the high correlation between the governance indicators. Our results show that the effect of cultural diversity improves some of the governance indicators while worsening others depending on the individual Hofstede cultural dimension.

DCSO: Towards an Ontology for Machine-Actionable Data Management Plans

Authors
Cardoso, J.; Castro, L.J.; Ekaputra, F.J.; Jacquemot, M.C.; Suchánek, M.; Miksa, T.; Borbinha, J.
Year
2022
Published
Journal of Biomedical Semantics. 2022, 13(1), ISSN 2041-1480.
Type
Article
Annotation
The concept of Data Management Plan (DMP) has emerged as a fundamental tool to help researchers through the systematical management of data. The Research Data Alliance DMP Common Standard (DCS) working group developed a set of universal concepts characterising a DMP so it can be represented as a machine-actionable artefact, i.e., machine-actionable Data Management Plan (maDMP). The technology-agnostic approach of the current maDMP specification: (i) does not explicitly link to related data models or ontologies, (ii) has no standardised way to describe controlled vocabularies, and (iii) is extensible but has no clear mechanism to distinguish between the core specification and its extensions.This paper reports on a community effort to create the DMP Common Standard Ontology (DCSO) as a serialisation of the DCS core concepts, with a particular focus on a detailed description of the components of the ontology. Our initial result shows that the proposed DCSO can become a suitable candidate for a reference serialisation of the DMP Common Standard.
Next

Filter

The person responsible for the content of this page: doc. Ing. Štěpán Starosta, Ph.D.