Publications

Article

10.1016/j.artint.2021.103561

Department of Theoretical Computer Science

Integer Linear Programming (ILP) has a broad range of applications in various areas of artificial intelligence. Yet in spite of recent advances, we still lack a thorough understanding of which structural restrictions make ILP tractable. Here we study ILP instances consisting of a small number of "global" variables and/or constraints such that the remaining part of the instance consists of small and otherwise independent components; this is captured in terms of a structural measure we call fracture backdoors which generalizes, for instance, the well-studied class of N-fold ILP instances.

Article

10.1016/j.ipl.2021.106118

Department of Theoretical Computer Science

Inspired by recent results for the so-called fair and local linear problems, we define two problems, LOCAL LINEAR SET and LOCAL LINEAR VERTEX COVER. Here the task is to find a set of vertices X subset of V (which is a vertex cover) of the input graph (V, E) such that the local linear constraints l(v) <= vertical bar X boolean AND N(v)vertical bar <= u(v) hold for all v is an element of V; here, l(v) and u( v) are on the input. We prove that both problems are in FPT for the parameter twin cover number (using integer linear programming).

Article

10.1016/j.orl.2021.11.005

Department of Theoretical Computer Science

Configuration integer programs (IP) have been key in the design of algorithms for NP-hard high-multiplicity problems. First, we develop fast exact (exponential-time) algorithms for Configuration IP and matching hardness results. Second, we showcase the implications of these results to bin-packing and facility-location-like problems.

Article

10.1137/19M1299001

Department of Theoretical Computer Science

We obtain new polynomial kernels and compression algorithms for Path Cover and Cycle Cover, the well-known generalizations of the classical Hamiltonian Path and Hamiltonian Cycle problems. Our choice of parameterization is strongly influenced by the work of Biró, Hujter, and Tuza, who in 1992 introduced H-graphs, intersection graphs of connected subgraphs of a subdivision of a fixed (multi-)graph H. In this work, we turn to proper H-graphs, where the containment relationship between the representations of the vertices is forbidden. As the treewidth of a graph measures how similar the graph is to a tree, the size of graph H is the parameter measuring the closeness of the graph to a proper interval graph. We prove the following results. Path Cover admits a kernel of size O(||H||^8), where ||H|| is the size of graph H. In other words, we design an algorithm that for an n-vertex graph G and integer k >= 1, in time polynomial in n and ||H||, outputs a graph G' of size O(||H||^8) and k' <= |V(G')| such that the vertex set of G is coverable by k vertex-disjoint paths if and only if the vertex set of G' is coverable by k' vertex-disjoint paths. Hamiltonian Cycle admits a kernel of size O(||H||^8). Cycle Cover admits a polynomial kernel. We prove it by providing a compression of size O(||H||^10) into another NP-complete problem, namely, Prize Collecting Cycle Cover, that is, we design an algorithm that, in time polynomial in n and ||H||, outputs an equivalent instance of Prize Collecting Cycle Cover of size O(||H||^10). In all our algorithms we assume that a proper H-decomposition is given as a part of the input.

Article

10.1016/j.tcs.2021.01.027

Department of Theoretical Computer Science

The complexity of graph isomorphism (GRAPHISO) is a famous problem in computer science. For graphs G and H, it asks whether they are the same up to a relabeling of vertices. In 1981, Lubiw proved that list restricted graph isomorphism (LISTISO ) is NP -complete: for each u∈V(G), we are given a list L(u)⊆V(H) of possible images of u. After 35 years, we revive the study of this problem and consider which results for GRAPHISO can be modified to solve LISTISO. We prove: 1) Under certain conditions, GI -completeness of a class of graphs implies NP -completeness of LISTISO. 2) Several combinatorial algorithms for GRAPHISO can be modified to solve LISTISO: for trees, planar graphs, interval graphs, circle graphs, permutation graphs, and bounded treewidth graphs. 3) LISTISO is NP -complete for cubic colored graphs with sizes of color classes bounded by 8 with all lists of size at most 3.

Proceedings paper

10.5555/3463952.3463988

Department of Theoretical Computer Science

The envy-free, Pareto-efficient allocation of indivisible goods leads to computationally hard problems. There is a big variety of modeling issues, such as agent-specific utility functions or (high numbers of) different types of goods. In recent work, Bredereck et al. [ACM EC~2019] addressed this topic by showing (theoretical) fixed-parameter tractability results for "high-multiplicity fair allocation", exploiting parameters such as the number of agents or maximum absolute utility values. To this end, they used a number of tools from (theoretical) integer linear programming. We "engineer" their work towards practical usefulness, thereby being able to solve all real-world instances from the state-of-art online platform "spliddit.org for provably fair solutions". Besides providing the foundations for a fast tool for fair allocations, we also offer a flexible framework with the possibility to relax fairness or efficiency demands so to, e.g., allow tradeoffs between fairness and social welfare. Moreover, our framework provides ways to interpret and explain "solution paths" which makes it possible to perform further explorations in cases when no envy-free and efficient allocations exist.

Proceedings paper

10.1007/978-3-030-92702-8_2

Department of Theoretical Computer Science

Consider a vertex-weighted graph G with a source s and a target t. Tracking Paths requires finding a minimum weight set of vertices (trackers) such that the sequence of trackers in each path from s to t is unique. In this work, we derive a factor 66-approximation algorithm for Tracking Paths in weighted graphs and a factor 4-approximation algorithm if the input is unweighted. This is the first constant factor approximation for this problem. While doing so, we also study approximation of the closely related r -Fault Tolerant Feedback Vertex Set problem. There, for a fixed integer r and a given vertex-weighted graph G, the task is to find a minimum weight set of vertices intersecting every cycle of G in at least r+1 vertices. We give a factor O(r^2) approximation algorithm for r -Fault Tolerant Feedback Vertex Set if r is a constant.

Proceedings paper

10.24963/ijcai.2020/10

Department of Theoretical Computer Science

Given a set of individuals qualifying or disqualifying each other, group identification is the task of identifying a socially qualified subgroup of individuals. Social qualification depends on the specific rule used to aggregate individual qualifications. The bribery problem in this context asks how many agents need to change their qualifications in order to change the outcome. Complementing previous results showing polynomial-time solvability or NP-hardness of bribery for various social rules in the constructive (aiming at making specific individuals socially qualified) or destructive (aiming at making specific individuals socially disqualified) setting, we provide a comprehensive picture of the parameterized computational complexity landscape. Conceptually, we also consider a more fine-grained concept of bribery cost, where we ask how many single qualifications need to be changed, and a more general bribery goal that combines the constructive and destructive setting.

Proceedings paper

Department of Theoretical Computer Science

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.

Article

10.1016/j.disc.2020.112234

Department of Theoretical Computer Science

Consider a hypergraph n^d where the vertices are points of the d-dimensional cube [n]^d and the edges are all sets of n points such that they are in one line. We study the structure of the group of automorphisms of n^d, i.e., permutations of points of [n]^d preserving the edges. In this paper we provide a complete characterization. Moreover, we consider the Colored Cube Isomorphism problem of deciding whether for two colorings of the vertices of n^d there exists an automorphism of n^d preserving the colors. We show that this problem is GI-complete.

Article

10.1007/s00224-021-10045-w

Department of Theoretical Computer Science

We study the NP-hard graph problem Collapsed k-Core where, given an undirected graph G and integers b, x, and k, we are asked to remove b vertices such that the k-core of remaining graph, that is, the (uniquely determined) largest induced subgraph with minimum degree k, has size at most x. Collapsed k-Core was introduced by Zhang et al. (2017) and it is motivated by the study of engagement behavior of users in a social network and measuring the resilience of a network against user drop outs. Collapsed k-Core is a generalization of r-Degenerate Vertex Deletion (which is known to be NP-hard for all r >= 0) where, given an undirected graph G and integers b and r, we are asked to remove b vertices such that the remaining graph is r-degenerate, that is, every its subgraph has minimum degree at most r. We investigate the parameterized complexity of Collapsed k-Core with respect to the parameters b, x, and k, and several structural parameters of the input graph. We reveal a dichotomy in the computational complexity of Collapsed k-Core for k <= 2 and k >= 3. For the latter case it is known that for all x >= 0 Collapsed k-Core is W[P]-hard when parameterized by b. For k <= 2 we show that Collapsed k-Core is W[1]-hard when parameterized by b and in FPT when parameterized by (b + x). Furthermore, we outline that Collapsed k-Core is in FPT when parameterized by the treewidth of the input graph and presumably does not admit a polynomial kernel when parameterized by the vertex cover number of the input graph.

Proceedings paper

10.1007/978-3-030-79987-8_31

Department of Theoretical Computer Science

The Minimum Eccentricity Shortest Path Problem consists in finding a shortest path with minimum eccentricity in a given undirected graph. The problem is known to be NP-complete and W[2]-hard with respect to the desired eccentricity. We present fpt algorithms for the problem parameterized by the modular width, distance to cluster graph, the combination of distance to disjoint paths with the desired eccentricity, and maximum leaf number.

Proceedings paper

10.4230/LIPIcs.MFCS.2022.29

Department of Theoretical Computer Science

In this paper we study the kernelization of the d-Path Vertex Cover (d-PVC) problem. Given a graph G, the problem requires finding whether there exists a set of at most k vertices whose removal from G results in a graph that does not contain a path (not necessarily induced) with d vertices. It is known that d-PVC is NP-complete for d≥ 2. Since the problem generalizes to d-Hitting Set, it is known to admit a kernel with O(dk^d) edges. We improve on this by giving better kernels. Specifically, we give kernels with O(k^2) vertices and edges for the cases when d = 4 and d = 5. Further, we give a kernel with O(k^4d^{2d+9}) vertices and edges for general d.

Proceedings paper

Department of Theoretical Computer Science

We compare labeled ordered trees based on unit cost 1-degree edit distance that uses operations vertex relabeling, leaf insertion, and leaf deletion. Given an input tree T and a tree pattern P, we find all subtrees in T that match P with up to k errors. We show that this problem can be solved by finite automaton when T and P are represented in linear, prefix bar, notation. First, we solve this problem by a pushdown automaton. Then, we show that it can be transformed into a nondeterministic finite automaton due to its restricted use of the pushdown store. We also show a simulation of the nondeterministic finite automaton by dynamic programming.

Proceedings paper

10.1007/978-3-031-00123-9_40

Department of Theoretical Computer Science

Bitmap indices are widely used in commercial databases for processing complex queries, due to their efficient use of bit-wise operations. Bitmap indices apply natively to relational and linear datasets, with distinct separation of the columns or attributes, but do not perform well on multidimensional array scientific data. We propose a new method for multidimensional array indexing that considers the spatial component of multidimensional arrays. The hierarchical indexing method is based on sparse n-dimensional trees for dimension partitioning, and bitmap indexing with adaptive binning for attribute partitioning. This indexing performs well on range queries involving both dimension and attribute constraints, as it prunes the search space early. Moreover, the indexing is easily extensible to membership queries. The indexing method was implemented on top of a state of the art bitmap indexing library Fastbit, using tables partitioned along any subset of the data dimensions. We show that the hierarchical bitmap index outperforms conventional bitmap indexing, where an auxiliary attribute is required for each dimension. Furthermore, the adaptive binning significantly reduces the amount of bins and therefore memory requirements.

Proceedings paper

Department of Theoretical Computer Science

Recently, the concept of Elastic Degenerate Strings (EDS) was introduced as a way of representing a sequenced population of the same species. Several on-line Elastic Degenerate String Matching (EDSM) algorithms were presented so far. Some of them provide practical implementation. We propose a new on-line EDSM algorithm BNDM-EDS. Our algorithm combines two traditional algorithms BNDM and the Shift-And that were adapted to the specifics needed by Elastic Degenerate Strings. BNDM-EDS is running in O (Nmd m w e) worst-case time. This implies O (Nm) time for small patterns, where m is the length of the searched pattern, N is the size of EDS, and w is the size of the computer word. The algorithm uses O (N + n) space, where n is the length of EDS. BNDM-EDS requires a simple preprocessing step with time and space O (m). Experimental results on real genomic data show superiority of BNDM-EDS over state-of-the-art algorithms.

Article

10.1145/3445967

Department of Theoretical Computer Science

The analysis of biological sequencing data has been one of the biggest applications of string algorithms. The approaches used in many such applications are based on the analysis of k-mers, which are short fixed-length strings present in a dataset. While these approaches are rather diverse, storing and querying a k-mer set has emerged as a shared underlying component. A set of k-mers has unique features and applications that, over the past 10 years, have resulted in many specialized approaches for its representation. In this survey, we give a unified presentation and comparison of the data structures that have been proposed to store and query a k-mer set. We hope this survey will serve as a resource for researchers in the field as well as make the area more accessible to researchers outside the field.

Proceedings paper

10.1137/1.9781611976472.5

Department of Theoretical Computer Science

Prefix-free parsing (PFP) was introduced by Boucher et al. (2019) as a preprocessing step to ease the computation of Burrows-Wheeler Transforms (BWTs) of genomic databases. Given a string S, it produces a dictionary D and a parse P of overlapping phrases such that BWT(S) can be computed from D and P in time and workspace bounded in terms of their combined size |PFP(S)|. In practice D and P are significantly smaller than S and computing BWT(S) from them is more efficient than computing it from S directly, at least when S is the concatenation of many genomes. In this paper, we consider PFP(S) as a data structure and show how it can be augmented to sup- port full suffix tree functionality, still built and fitting within O(|PFP(S)|) space. This entails the efficient computation of various primitives to simulate the suffix tree: computing a longest common extension (LCE) of two positions in S; reading any cell of its suffix array (SA), of its inverse (ISA), of its BWT, and of its longest common prefix array (LCP); and computing minima over ranges and next/previous smaller value queries over the LCP. Our experimental results show that the PFP suffix tree can be efficiently constructed for very large repetitive datasets and that its operations perform competitively with other compressed suffix trees that can only handle much smaller datasets.

Proceedings paper

Department of Theoretical Computer Science

Regular tree languages can be accepted and described by finite tree automata and regular tree expressions, respectively. We describe a new algorithm that converts a finite tree automaton to an equivalent regular tree expression. Our algorithm is analogous to the well-known state elimination method of the conversion of a string finite automaton to an equivalent string regular expression. We define a generalised finite tree automaton, the transitions of which read the sets of trees described by regular tree expressions. Our algorithm eliminates states of the generalised finite tree automaton, which is analogous to the elimination of states in converting the string finite automaton.

Proceedings paper

Department of Theoretical Computer Science

We define a tree pattern border array as a property of linearised trees analogous to border arrays from the string domain. We use it to define a new forward tree pattern matching algorithm for ordered trees, which finds all occurrences of a single given linearised tree pattern in a linearised input tree. As with the classical Morris-Pratt algorithm, the tree pattern border array is used to determine shift lengths in the matching phase of the tree pattern matching algorithm. We compare the new algorithm with the best performing previously existing algorithms based on backward linearised tree pattern matching algorithms, (non-)linearised tree pattern matching algorithms using finite tree automata or stringpath matchers. We show that the presented algorithm outperforms these for single tree pattern matching.

Proceedings paper

10.1609/aaai.v34i02.5550

Department of Theoretical Computer Science

Adaptivity to changing environments and constraints is key to success in modern society. We address this by proposing “incrementalized versions” of Stable Marriage and Stable Roommates. That is, we try to answer the following question: for both problems, what is the computational cost of adapting an existing stable matching after some of the preferences of the agents have changed. While doing so, we also model the constraint that the new stable matching shall be not too different from the old one. After formalizing these incremental versions, we provide a fairly comprehensive picture of the computational complexity landscape of Incremental Stable Marriage and Incremental Stable Roommates. To this end, we exploit the parameters “degree of change” both in the input (difference between old and new preference profile) and in the output (difference between old and new stable matching). We obtain both hardness and tractability results, in particular showing a fixed-parameter tractability result with respect to the parameter “distance between old and new stable matching”.

Proceedings paper

10.1609/aaai.v34i02.5551

Department of Theoretical Computer Science

We extend the work of Skowron et al. (AIJ, 2016) by considering the parameterized complexity of the following problem. We are given a set of items and a set of agents, where each agent assigns an integer utility value to each item. The goal is to find a set of k items that these agents would collectively use. For each such collective set of items, each agent provides a score that can be described using an OWA (ordered weighted average) operator and we seek a set with the highest total score. We focus on the parameterization by the number of agents and we find numerous fixed-parameter tractability results (however, we also find some W[1]-hardness results). It turns out that most of our algorithms even apply to the setting where each agent has an integer weight.

Proceedings paper

10.1007/978-3-030-64946-3_5

Department of Theoretical Computer Science

Since the early days of research in algorithms and complexity, the computation of stable matchings is a core topic. While in the classic setting the goal is to match up two agents (either from different “gender” (this is Stable Marriage) or “unrestricted” (this is Stable Roommates)), Knuth [1976] triggered the study of three- or multidimensional cases. Here, we focus on the study of Multidimensional Stable Roommates, known to be 𝖭𝖯 -hard since the early 1990’s. Many 𝖭𝖯 -hardness results, however, rely on very general input instances that do not occur in at least some of the specific application scenarios. With the quest for identifying islands of tractability, we look at the case of master lists. Here, as natural in applications where agents express their preferences based on “objective” scores, one roughly speaking assumes that all agent preferences are “derived from” a central master list, implying that the individual agent preferences shall be similar. Master lists have been frequently studied in the two-dimensional (classic) stable matching case, but seemingly almost never for the multidimensional case. This work, also relying on methods from parameterized algorithm design and complexity analysis, performs a first systematic study of Multidimensional Stable Roommates under the assumption of master lists.

doc. Ing. Jan Janoušek, Ph.D.

Prof. Tobias Wrigstad
Max Schaefer, MSc., DPhil.
Mgr. Tomáš Petříček, Ph.D.

Department of Theoretical Computer Science

Thesis on DSpace

doc. Ing. Jan Janoušek, Ph.D.

prof. RNDr. Alexandr Meduna, CSc.
prof. Philip Bille
prof. Giovanni Pighizzini

Department of Theoretical Computer Science

Thesis on DSpace

Mgr. Martin Jureček, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Department of Theoretical Computer Science

Machine learning is becoming increasingly popular as a go-to approach for many tasks due to its world-class results. As a result, antivirus developers are starting to incorporate machine learning models into their products. While these models improve malware detection capabilities, they also carry the disadvantage of being susceptible to adversarial attacks. Although this sensitivity has been demonstrated for many models in white-box settings, a black-box attack is more applicable in practice for the domain of malware detection. Therefore, we present a black-box scenario in which the attacker only has the predicted label at his disposal and forgoes any other information about the target classifier. Using reinforcement learning algorithms, we implemented an attack against the GBDT classifier trained on the EMBER dataset. We trained several RL agents on a dataset of Windows malware with an emphasis on preserving the original functionality of the malicious samples. We achieved an evasion rate of 58.92% against the targeted classifier using the PPO algorithm. In addition to targeting this detector, we studied how the adversarial attack can be transferred to other models. The agent previously trained against the GBDT classifier scored an evasion rate of 28.91% against MalConv, a model based solely on machine learning. We also tested the generated adversarial examples against top AV programs and achieved an evasion rate ranging from 10.24% to 25.7%. These results prove that not only machine learning-based models are vulnerable to adversarial attacks and that better safeguards need to be taken to protect our systems.

Thesis on DSpace

doc. RNDr. Dušan Knop, Ph.D.

Mgr. Michal Opler, Ph.D.

Department of Theoretical Computer Science

This thesis focuses on winner selection in committee election. We provide an overview of voting systems for single-winner and multi-winner election. Winner selection is often computationally hard, therefore we introduce election with structured preferences. In election with structured preferences, the votes are in some way restricted which may help to create more efficient winner selection algorithms. We describe some of the known structured preferences. We provide an overview of the current literature on the topic of structured and nearly structured preferences. We also review current work on committee election with structured preferences and usage of ordered weighted average (OWA) in committee election. We propose polynomial-time algorithms for finding a winning committee for approval election with OWA vector (0, ..., 0, 1) and interval preference restrictions. In such election, a voter approves a committee only if she approves all of its members. We use this property and show two approaches for finding a winning committee.

Thesis on DSpace

Ryan Michael Culpepper

doc. Ing. Filip Křikava, Ph.D.

Department of Theoretical Computer Science

This thesis presents an implementation of a functional, statically typed programming language inspired by Haskell. It mainly focuses on the challenges of implementing the type system for such an language. The implementation is based on multiple resources covering implementations of different type system features. The thesis also covers other aspects of the language implementation--lexical and syntactic analysis, translation into a smaller functional core language, and non-strict evaluation.

Thesis on DSpace

prof. Ing. Jan Holub, Ph.D.

prof. Ing. Michal Krátký, Ph.D.
Kwo-Sen Kuo, PhD.
Dimitar Mišev, PhD.

Department of Theoretical Computer Science

Thesis on DSpace

doc. RNDr. Tomáš Valla, Ph.D.

Prof., Dr. rer. nat. Robert Bredereck
RNDr. Martin Balko, Ph.D.
Paweł Rzążewski, PhD.

Department of Theoretical Computer Science

Thesis on DSpace

doc. Ing. Filip Křikava, Ph.D.

Vitaly Bragilevsky, MSc.

Department of Theoretical Computer Science

Haskell is one of the most well-known instances of a programming language that uses non-strict semantics. On the one hand, this brings the convenience of infinite data structures, user-defined control flow, and the possibility to avoid unnecessary computation. On the other hand, these benefits are hampered by the runtime overhead and hard-to-predict the behaviour of call-by-need. This begs the question: Is laziness worth it? To answer this question, we need to understand how laziness is used in the wild. To this end, we develop a tool for dynamic analysis used to trace the evaluation of function parameters. It is implemented as a compiler plugin for the Glasgow Haskell Compiler.

Thesis on DSpace

doc. RNDr. Dušan Knop, Ph.D.

Department of Theoretical Computer Science

In the Roommate diversity problem, agents that belong to one of the two types have to be allocated to fixed size rooms based on their preferences, which depend solely on the fraction of agents of their own type among their potential roommates. In this work we study the stability of outcomes with respect to the room size and structured preferences. We provide a new randomized algorithm for finding core stable outcomes and show the results which we have obtained with the algorithm. We have found a small single-peaked instance with empty core and have verified, that every instance of the Roommate diversity problem with room size = 3, all preferences single peaked and number of agents &amp;lt;= 30, room size = 3 and number of agents &amp;lt;= 15, room size = 4, all preferences single peaked and number of agents = 30, admits an outcome that is core stable. We present arguments why we believe that every instance of this problem with room size = 3, room size = 4 and all preferences single peaked, admits an outcome that is core stable.

Thesis on DSpace

doc. Ing. Štěpán Starosta, Ph.D.

doc. Ing. Jan Janoušek, Ph.D.

Department of Theoretical Computer Science

In this thesis, several algorithms for problems from the mathematical field combinatorics on words are thoroughly explained. The algorithms are also implemented in the free and open-source mathematics software system SageMath with the goal of their eventual integration into the same system. The algorithms include: classifying mortal and bounded letters of a morphism, deciding whether a morphism is injective, finding a simplification of a morphism, finding all infinite repetitions in a D0L system, and finding all factors (up to a certain length) of words of the language of a PD0L system. Furthermore, the problem of deciding whether a morphism of a D0L system is injective on the set of factors of words of the language of the system is discussed. The decidability of this problem is an open question, which is not answered in this thesis, but it is shown why it is nontrivial and where some approaches to solving this problem fail.

Thesis on DSpace

Ing. Daniel Langr, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Department of Theoretical Computer Science

Frequent heap allocations can have a significant impact on the overall performance of a program. The problem becomes even more critical in multithreaded applications, where too many interactions with heap can grow into the main bottleneck and effectively diminish scalability. Profiling such applications with existing heap profilers is almost impossible due to the enormous runtime overhead they add. This thesis describes the typical memory layout of a Linux process, briefly shows the internals of the GNU C memory allocator, analyzes available heap profiling tools, and guides the reader through the process of constructing a~custom heap profiler. Further, the thesis proposes a concept of low-latency heap profiling. Based on that, a new profiler Heaprof has been developed and compared with other heap profiling tools. Experimental results revealed that Heaprof was the only tool capable of profiling without further compromising the program's scalability. For 8-threaded benchmarks, Heaprof achieved up to 8 times profiling speedup.

Thesis on DSpace

Ing. Petr Máj, Ph.D.

Ing. Tomáš Pecka

Department of Theoretical Computer Science

This thesis presents tiny x86 architecture and virtual machine designed to help students understand various compiler techniques and their effect on the program performance. Compared to existing instruction set architectures, tiny x86 is simpler, easier to use as it comes with a C++ API as opposed to binary encodings and does not limit itself to single design principles (both CISC and RISC features are supported). The VM also offers extensive configuration options, allowing it to (de-)emphasize various architecture features (register pressure, memory latency, instruction timings, etc.). The VM is already used in the NI-GEN (Code Generation) course at FIT CTU, where its simplicity allows the students to write full compiler pipeline during the term.

Thesis on DSpace