open_access
Refine
Year of publication
Document Type
- Doctoral Thesis (228)
- Article (26)
- Preprint (10)
- Conference Proceeding (9)
- Report (4)
- Book (3)
- Part of Periodical (3)
- Master's Thesis (1)
- Other (1)
Language
- English (285) (remove)
Has Fulltext
- yes (285)
Keywords
- Computersicherheit (8)
- Maßtheorie (8)
- Graphenzeichnen (6)
- Iteriertes Funktionensystem (5)
- Marketing (5)
- Multimedia (5)
- Software Engineering (5)
- Information Retrieval (4)
- Kryptologie (4)
- Modellierung (4)
Institute
- Fakultät für Informatik und Mathematik (102)
- Wirtschaftswissenschaftliche Fakultät (52)
- Mitarbeiter Lehrstuhl/Einrichtung der Fakultät für Informatik und Mathematik (47)
- Philosophische Fakultät (36)
- Mitarbeiter Lehrstuhl/Einrichtung der Wirtschaftswissenschaftlichen Fakultät (9)
- Sonstiger Autor der Fakultät für Informatik und Mathematik (9)
- Sozial- und Bildungswissenschaftliche Fakultät (8)
- Philosophische Fakultät / Südostasienkunde (6)
- Sonstiger Autor der Wirtschaftswissenschaftlichen Fakultät (5)
- Juristische Fakultät (4)
- Sonstiger Autor der Philosophischen Fakultät (2)
- Department für Katholische Theologie (1)
- Philosophische Fakultät / Geographie (1)
- Universitätsbibliothek (1)
- Zentrale Einrichtungen (1)
Cryptography is the scientific study of techniques for securing information and communication against adversaries. It is about designing and analyzing encryption schemes and protocols that protect data from unauthorized reading. However, in our modern information-driven society with highly complex and interconnected information systems, encryption alone is no longer enough as it makes the data unintelligible, preventing any meaningful computation without decryption. On the one hand, data owners want to maintain control over their sensitive data. On the other hand, there is a high business incentive for collaborating with an untrusted external party.
Modern cryptography encompasses different techniques, such as secure multiparty computation, homomorphic encryption or order-preserving encryption, that enable cloud users to encrypt their data before outsourcing it to the cloud while still being able to process and search on the outsourced and encrypted data without decrypting it. In this thesis, we rely on these cryptographic techniques for computing on encrypted data to propose efficient multiparty protocols for order-preserving encryption, decision tree evaluation and kth-ranked element computation.
We start with Order-preserving encryption (OPE) which allows encrypting data, while still enabling efficient range queries on the encrypted data. However, OPE is symmetric limiting, the use case to one client and one server. Imagine a scenario where a Data Owner (DO) outsources encrypted data to the Cloud Service Provider (CSP) and a Data Analyst (DA) wants to execute private range queries on this data. Then either the DO must reveal its encryption key or the DA must reveal the private queries. We overcome this limitation by allowing the equivalent of a public-key OPE.
Decision trees are common and very popular classifiers because they are explainable. The problem of evaluating a private decision tree on private data consists of a server holding a private decision tree and a client holding a private attribute vector. The goal is to classify the client’s input using the server’s model such that the client learns only the result of the classification, and the server learns nothing. In a first approach, we represent the tree as an array and execute only d interactive comparisons (instead of 2 d as in existing solutions), where d denotes the depth of the tree. In a second approach, we delegate the complete tree evaluation to the server using somewhat or fully homomorphic encryption where the ciphertexts are encrypted under the client’s public key.
A generalization of a decision tree is a random forest that consists of many decision trees. A classification with a random forest evaluates each decision tree in the forest and outputs the classification label which occurs most often. Hence, the classification labels are ranked by their number of occurrences and the final result is the best ranked one. The best ranked element is a special case of the kth-ranked element. In this thesis, we consider the secure computation of the kth-ranked element in a distributed setting with applications in benchmarking and auctions. We propose different approaches for privately computing the kth-ranked element in a star network, using either garbled circuits or threshold homomorphic encryption.
We consider a number of enhancements to the standard neural network training paradigm. First, we show that carefully designed parameter update rules may replace the need for a loss function and its gradient. We introduce a parameter update rule that generalises the standard cross-entropy gradient, and allows directly controlling the relative effect of easy and hard examples on the training process. We show that the proposed update rule cannot be derived by using a loss function and yields better classification accuracy compared to training with the standard cross-entropy loss.
In addition, we study the effect of the loss function choice on the learnt representations. We introduce the Single Logit Classification (SLC) task: classifying whether a given class is the correct class for a given example, in a computationally efficient manner, based on the appropriate class logit alone. A natural principle is proposed, the Principle of Logit Separation (PoLS), as a guideline for choosing and designing loss functions suitable for the SLC task. We mathematically analyse the alignment of eleven existing and novel loss functions with this principle. Experiment results show that using loss functions that are aligned with this principle results in a representation in the logits layer in which each logit is more informative of its class correctness, leading to a considerably better SLC accuracy.
Further, we attempt to alleviate the dependency of standard neural network models on large amounts of quality labels. The task of weakly supervised one-shot detection is considered, in which at training time the model is trained without any localisation labels, and at test time it needs to identify and localise instances of unseen classes. We propose the attention similarity networks (ASN) for this task. ASN use a Siamese neural network to compute a similarity score between an exemplar and different locations in a target example. Then, an attention mechanism performs localisation by learning to attend to the correct locations. The ASN model outperforms the relevant baselines for weakly supervised one-shot detection tasks in the audio and computer vision domains.
Finally, we consider the problem of quantifying prediction confidence in the regression setting. We propose two novel algorithms for emitting calibrated prediction intervals for neural network regressors, at any given confidence level. The two algorithms require binning of the output space and training the neural network regressor as a classifier. Then, the calibration algorithms choose the intervals in the output space, making sure they contain the amount of posterior probability mass that results in the desired confidence level.
We have proposed a strategy for the creation of attributes based on hidden Markov models (HMM) characterizing the transaction from different points of view. This strategy makes it possible to integrate a broad spectrum of sequential information into the attributes of transactions. In fact, we model the authentic and fraudulent behavior of merchants and card holders according to two univariate characteristics: the date and the amount of transactions. In addition, attributes based on HMMs are created in a supervised manner, thereby reducing the need for expert knowledge for the creation of the fraud detection system. Ultimately, our HMM-based multi-perspective approach allows automated data pre-processing to model time correlations to complement and eventually replace transaction aggregation strategies to improve detection efficiency. Experiments carried out on a large set of credit card transaction data from the real world (46 million transactions carried out by Belgian card holders between March and May 2015) have shown that the strategy proposed for data preprocessing based on HMM can detect more fraudulent transactions when combined with the strategy of preprocessing reference data based on expert knowledge for the detection of credit card fraud.
Our subject of study is strong approximation of stochastic differential equations (SDEs) with respect to the supremum and the L_p error criteria, and we seek approximations that are strongly asymptotically optimal in specific classes of approximations. For the supremum error, we prove strong asymptotic optimality for specific tamed Euler schemes relating to certain adaptive and to equidistant time discretizations. For the L_p error, we prove strong asymptotic optimality for specific tamed Milstein schemes relating to certain adaptive and to equidistant time discretizations. To illustrate our findings, we numerically analyze the SDE associated with the Heston–3/2–model originating from mathematical finance.
Nowadays, consumers are often required to disclose private data in various contexts such as while surfing the internet, downloading a mobile application, or engaging in a business relationship with a firm. Privacy-related decision-making research has so far mainly investigated data disclosure as a cognitive risk-benefit trade-off analysis. While this cognitive approach might be appropriate for situations where consumers have the opportunity for cognitive evaluations, there are many situations in the modern landscape where consumers cannot or do not want to engage in cognitive processing. Decision-making under stress or data disclosure to a business network of collaborating firms, for example, constitute challenges to purely cognitive decision-making approaches, calling for an extension of the established paradigm of cognitive privacy-related decision making. This dissertation advocates for the crucial role of affective processing in many modern data disclosure situations, where consumers do not engage in purely cognitive processing due to external hindrances or a lack of personal involvement in the data disclosure situation.
Geography, social context, time, and cultural mindset are four (out of many) cornerstones of human interaction. When building statistical models, their consideration is vital: They all cause dependency between individual observations, violating assumptions of independence and exchangeability. While this can be problematic and inhibit the unbiased inference of parameters, it can also be a fruitful source of insights and enhance prediction performance.
One class of models that serves to manage or profit from the presence of dependence is the class of latent variable models. This class of models assumes that the presence of non-explicit, unobserved causes of continuous or discrete nature can explain the observed correlations. Latent variable models explicitly take account of dependency, for example, by modeling an unobserved local source of pollution as a continuous spatial variable. Through their widespread use for information fitering, link prediction, and statistical inference, latent variable models have developed an essential impact on our daily life and the way we consume information.
The four articles in this thesis shed light on assumptions, usage, and potential drawbacks of latent variable models in various contexts that involve geographic and interaction data. We model unobserved sources of pollution in geophysical data, explore individual taste and mindsets in cross-cultural contexts, and predict the evolution of social relationships in software development projects. This combination of various perspectives contributes to the interdisciplinary exchange of methodological knowledge on the modeling of dependent data.
In high-performance computing, one primary objective is to exploit the performance that the given target hardware can deliver to the fullest. Compilers that have the ability to automatically optimize programs for a specific target hardware can be highly useful in this context. Iterative (or search-based) compilation requires little or no prior knowledge and can adapt more easily to concrete programs and target hardware than static cost models and heuristics. Thereby, iterative compilation helps in situations in which static heuristics do not reflect the combination of input program and target hardware well. Moreover, iterative compilation may enable the derivation of more accurate cost models and heuristics for optimizing compilers. In this context, the polyhedron model is of help as it provides not only a mathematical representation of programs but, more importantly, a uniform representation of complex sequences of program transformations by schedule functions. The latter facilitates the systematic exploration of the set of legal transformations of a given program.
Early approaches to purely iterative schedule optimization in the polyhedron model do not limit their search to schedules that preserve program semantics and, thereby, suffer from the need to explore numbers of illegal schedules. More recent research ensures the legality of program transformations but presumes a sequential rather than a parallel execution of the transformed program. Other approaches do not perform a purely iterative optimization.
We propose an approach to iterative schedule optimization for parallelization and tiling in the polyhedron model. Our approach targets loop programs that profit from data locality optimization and coarse-grained loop parallelization. The schedule search space can be explored either randomly or by means of a genetic algorithm.
To determine a schedule's profitability, we rely primarily on measuring the transformed code's execution time. While benchmarking is accurate, it increases the time and resource consumption of program optimization tremendously and can even make it impractical. We address this limitation by proposing to learn surrogate models from schedules generated and evaluated in previous runs of the iterative optimization and to replace benchmarking by performance prediction to the extent possible.
Our evaluation on the PolyBench 4.1 benchmark set reveals that, in a given setting, iterative schedule optimization yields significantly higher speedups in the execution of the program to be optimized. Surrogate performance models learned from training data that was generated during previous iterative optimizations can reduce the benchmarking effort without strongly impairing the optimization result. A prerequisite for this approach is a sufficient similarity between the training programs and the program to be optimized.
Algebraic solving of polynomial systems and satisfiability of propositional logic formulas are not two completely separate research areas, as it may appear at first sight. In fact, many problems coming from cryptanalysis, such as algebraic fault attacks, can be rephrased as solving a set of Boolean polynomials or as deciding the satisfiability of a propositional logic formula. Thus one can analyze the security of cryptosystems by applying standard solving methods from computer algebra and SAT solving. This doctoral thesis is dedicated to studying solvers that are based on logic and algebra separately as well as integrating them into one such that the combined solvers become more powerful tools for cryptanalysis.
This disseration is divided into three parts. In this first part, we recall some theory and basic techniques for algebraic and logic solving. We focus mainly on DPLL-based SAT solving and techniques that are related to border bases and Gröbner bases. In particular, we describe in detail the Border Basis Algorithm and discuss its specialized version for Boolean polynomials called the Boolean Border Basis Algorithm.
In the second part of the thesis, we deal with connecting solvers based on algebra and logic. The ultimate goal is to combine the strength of different solvers into one. Namely, we fuse the XOR reasoning from algebraic solvers with the light, efficient design of SAT solvers. As a first step in this direction, we design various conversions from sets of clauses to sets of Boolean polynomials, and vice versa, such that solutions and models are preserved via the conversions. In particular, based on a block-building mechanism, we design a new blockwise algorithm for the CNF to ANF conversion which is geared towards producing fewer and lower degree polynomials. The above conversions allow usto integrate both solvers via a communication interface.
To reach an even tighter integration, we consider proof systems that combine resolution and polynomial calculus, i.e. the two most used proof systems in logic and algebraic solving. Based on such a proof system, which we call SRES, we introduce new types of solving algorithms that demostrate the synergy between Gröbner-like and DPLL-like solving. At the end of the second part of the dissertation, we provide some experiments based on a new benchmark which illustrate that the our new method based on DPLL has the potential to outperform CDCL SAT solvers.
In the third part of the thesis, we focus on practical attacks on various cryptograhic primitives. For instance, we apply SAT solvers in the case of algebraic fault attacks on the symmetric ciphers LED and derivatives of the block cipher AES. The main goal there is to derive so-called fault equations automatically from the hardware description of the cryptosystem and thus automatizate the attack. To give some extra power to a SAT solver that inverts the hash functions SHA-1 and SHA-2, we describe how to tweak the SAT solver using a programmatic interface such that the propagation of the solver and thus the attack itself is improved.
Internet browsers include Application Programming Interfaces (APIs) to support Web applications that require complex functionality, e.g., to let end users watch videos, make phone calls, and play video games. Meanwhile, many Web applications employ the browser APIs to rely on the user's hardware to execute intensive computation, access the Graphics Processing Unit (GPU), use persistent storage, and establish network connections.
However, providing access to the system's computational resources, i.e., processing, storage, and networking, through the browser creates an opportunity for attackers to abuse resources. Principally, the problem occurs when an attacker compromises a Web site and includes malicious code to abuse its visitor's computational resources. For example, an attacker can abuse the user's system networking capabilities to perform a Denial of Service (DoS) attack against third parties. What is more, computational resource abuse has not received widespread attention from the Web security community because most of the current specifications are focused on content and session properties such as isolation, confidentiality, and integrity.
Our primary goal is to study computational resource abuse and to advance the state of the art by providing a general attacker model, multiple case studies, a thorough analysis of available security mechanisms, and a new detection mechanism. To this end, we implemented and evaluated three scenarios where attackers use multiple browser APIs to abuse networking, local storage, and computation. Further, depending on the scenario, an attacker can use browsers to perform Denial of Service against third-party Web sites, create a network of browsers to store and distribute arbitrary data, or use browsers to establish anonymous connections similarly to The Onion Router (Tor). Our analysis also includes a real-life resource abuse case found in the wild, i.e., CryptoJacking, where thousands of Web sites forced their visitors to perform crypto-currency mining without their consent. In the general case, attacks presented in this thesis share the attacker model and two key characteristics: 1) the browser's end user remains oblivious to the attack, and 2) an attacker has to invest little resources in comparison to the resources he obtains.
In addition to the attack's analysis, we present how existing, and upcoming, security enforcement mechanisms from Web security can hinder an attacker and their drawbacks. Moreover, we propose a novel detection approach based on browser API usage patterns. Finally, we evaluate the accuracy of our detection model, after training it with the real-life crypto-mining scenario, through a large scale analysis of the most popular Web sites.
In various fields of image analysis, determining the precise geometry of occurrent edges, e.g. the contour of an object, is a crucial task. Especially the curvature of an edge is of great practical relevance. In this thesis, we develop different methods to detect a variety of edge features, among them the curvature.
We first examine the properties of the parabolic Radon transform and show that it can be used to detect the edge curvature, as the smoothness of the parabolic Radon transform changes when the parabola is tangential to an edge and also, when additionally the curvature of the parabola coincides with the edge curvature. By subsequently introducing a parabolic Fourier transform and establishing a precise relation between the smoothness of a certain class of functions and the decay of the Fourier transform, we show that the smoothness result for the parabolic Radon transform can be translated into a change of the decay rate of the parabolic Fourier transform.
Furthermore, we introduce an extension of the continuous shearlet transform which additionally utilizes shears of higher order. This extension, called the Taylorlet transform, allows for a detection of the position and orientation, as well as the curvature and other higher order geometric information of edges. We introduce novel vanishing moment conditions which enable a more robust detection of the geometric edge features and examine two different constructions for Taylorlets. Lastly, we translate the results of the Taylorlet transform in R^2 into R^3 and thereby allow for the analysis of the geometry of object surfaces.
The appearance of web and online media has created a substantial change in the manner by which employers and applicants interact. The development of web 1.0 applications with one-way communication and the advancement of web 2.0 technologies with interactive components have extended the spectrum of recruitment channels. The new recruitment media channels have led the selection and analysis of their impact out of interaction on each other to a new challenge within academical literature. This dissertation addresses these issues in three separate essays.
Study 1 focuses on the impact of Facebook as a social media recruitment channel on recruitment success. Many companies embed Facebook into their recruitment strategy as an additional recruitment channel for reaching potential applicants and motivating them to apply for available positions. Study 1 analyzes these activities and addresses the question of whether different Facebook activities influence recruitment success above and beyond other undertakings on traditional and online media channels. Study 1 concludes that on Facebook, company posts with a general focus and posts containing work or recruitment information both have a positive impact on recruitment success. The results of Study 1 are validated by company interviews with human resources (HR) managers who are responsible for the overall HR strategy of the company. Study 1 is the first academic work within HR and marketing research, which analyzes the impact of a company’s Facebook activities.
Study 2 examines the impact of traditional media recruitment channels on recruitment success. Many companies employ traditional media channels for their recruitment marketing actions with the aim of achieving recruitment success. Study 2 uses media richness theory as a basis for analyzing the impact of a company’s activities within traditional media channels on recruitment success. Study 2 concludes that exhibition fair and online marketing activities influence recruitment success. In connection with brand equity theory, Study 2 also verifies whether the addition of Facebook activities reinforces the impact of traditional media channels on recruitment success. The results indicate that general Facebook activities have a reinforcing impact on exhibition fair and print media recruitment practices.
Finally, Study 3 focuses on both the literature overview of traditional and social media recruitment practices and social media influence from the marketing literature. It also summarizes and categorizes previous research on the influence of traditional, online, and social media recruitment practices; the effect of a multichannel mix; and the influence of social media and social networking sites on different business outcomes from the marketing literature. Additionally, Study 3 identifies the research gaps and provides recommendations for future studies.
This dissertation uses vector autoregression modelling, including a validation with the help of company interviews and the employment of media richness, signaling, and brand equity theories, combined with a thorough analysis of the research need. The dissertation closes the research gap regarding the analysis of the impact of Facebook, online, and traditional media on recruitment success. It also adds new perspectives to the HR and marketing literature.
The processing of personal information is omnipresent in our data-driven society enabling personalized services, which are regulated by privacy policies. Although privacy policies are strictly defined by the General Data Protection Regulation (GDPR), no systematic mechanism is in place to enforce them. Especially if data is merged from several sources into a data-set with different privacy policies associated, the management and compliance to all privacy requirements is challenging during the processing of the data-set. Privacy policies can vary hereby due to different policies for each source or personalization of privacy policies by individual users. Thus, the risk for negligent or malicious processing of personal data due to defiance of privacy policies exists.
To tackle this challenge, a privacy-preserving framework is proposed. Within this framework privacy policies are expressed in the proposed Layered Privacy Language (LPL) which allows to specify legal privacy policies and privacy-preserving de-identification methods. The policies are enforced by a Policy-based De-identification (PD) process. The PD process enables efficient compliance to various privacy policies simultaneously while applying pseudonymization, personal privacy anonymization and privacy models for de-identification of the data-set. Thus, the privacy requirements of each individual privacy policy are enforced filling the gap between legal privacy policies and their technical enforcement.
The dissertation is located in the field of quantizations of certain stochastic processes, namely a solution X of a multidimensional stochastic differential equation (SDE). The quantization problem for X consists in approximating X by a a random element which takes only finitely many values. Our main interest lies in the investigation of the asymptotic behavior of the Nth minimal quantization error of X as N tends to infinity, which incorporates the determination of both the sharp rate of convergence and explicit asymptotic constants. Especially explicit asymptotic constants have been so far unknown in the context of multidimensional SDEs. Furthermore, as part of our analysis, we provide a method which yields a strongly asymptotically optimal sequence of N-quantization of X. In certain special cases our method is fully constructive and the algorithm is easy to implement.
A widely used class of codes are stencil codes. Their general structure is very simple: data points in a large grid are repeatedly recomputed from neighboring values. This predefined neighborhood is the so-called stencil. Despite their very simple structure, stencil codes are hard to optimize since only few computations are performed while a comparatively large number of values have to be accessed, i.e., stencil codes usually have a very low computational intensity. Moreover, the set of optimizations and their parameters also depend on the hardware on which the code is executed.
To cut a long story short, current production compilers are not able to fully optimize this class of codes and optimizing each application by hand is not practical. As a remedy, we propose a set of optimizations and describe how they can be applied automatically by a code generator for the domain of stencil codes. A combination of a space and time tiling is able to increase the data locality, which significantly reduces the memory-bandwidth requirements: a standard three-dimensional 7-point Jacobi stencil can be accelerated by a factor of 3. This optimization can target basically any stencil code, while others are more specialized. E.g., support for arbitrary linear data layout transformations is especially beneficial for colored kernels, such as a Red-Black Gauss-Seidel smoother. On the one hand, an optimized data layout for such kernels reduces the bandwidth requirements while, on the other hand, it simplifies an explicit vectorization.
Other noticeable optimizations described in detail are redundancy elimination techniques to eliminate common subexpressions both in a sequence of statements and across loop boundaries, arithmetic simplifications and normalizations, and the vectorization mentioned previously. In combination, these optimizations are able to increase the performance not only of the model problem given by Poisson’s equation, but also of real-world applications: an optical flow simulation and the simulation of a non-isothermal and non-Newtonian fluid flow.
Our internal clock, the circadian clock, determines at which time we have our best cognitive abilities, are physically strongest, and when we are tired. Circadian clock phase is influenced primarily through exposure to light. A direct pathway from the eyes to the suprachiasmatic nucleus, where the circadian clock resides, is used to synchronise the circadian clock to external light-dark cycles.
In modern society, with the ability to work anywhere at anytime and a full social agenda, many struggle to keep internal and external clocks synchronised. Living against our circadian clock makes us less efficient and poses serious health impact, especially when exercised over a long period of time, e.g. in shift workers. Assessing circadian clock phase is a cumbersome and uncomfortable task. A common method, dim light melatonin onset testing, requires a series of eight saliva samples taken in hourly intervals while the subject stays in dim light condition from 5 hours before until 2 hours past their habitual bedtime.
At the same time, sensor-rich smartphones have become widely available and wearable computing is on the rise. The hypothesis of this thesis is that smartphones and wearables can be used to record sensor data to monitor human circadian rhythms in free-living. To test this hypothesis, we conducted research on specialised wearable hardware and smartphones to record relevant data, and developed algorithms to monitor circadian clock phase in free-living. We first introduce our smart eyeglasses concept, which can be personalised to the wearers head and 3D-printed. Furthermore, hardware was integrated into the eyewear to recognise typical activities of daily living (ADLs). A light sensor integrated into the eyeglasses bridge was used to detect screen use. In addition to wearables, we also investigate if sleep-wake patterns can be revealed from smartphone context information. We introduce novel methods to detect sleep opportunity, which incorporate expert knowledge to filter and fuse classifier outputs. Furthermore, we estimate light exposure from smartphone sensor and weather in- formation. We applied the Kronauer model to compare the phase shift resulting from head light measurements, wrist measurements, and smartphone estimations.
We found it was possible to monitor circadian phase shift from light estimation based on smartphone sensor and weather information with a weekly error of 32±17min, which outperformed wrist measurements in 11 out of 12 participants. Sleep could be detected from smartphone use with an onset error of 40±48 min and wake error of 42±57 min. Screen use could be detected smart eyeglasses with 0.9 ROC AUC for ambient light intensities below 200lux. Nine clusters of ADLs were distinguished using Gaussian mixture models with an average accuracy of 77%. In conclusion, a combination of the proposed smartphones and smart eyeglasses applications could support users in synchronising their circadian clock to the external clocks, thus living a healthier lifestyle.
Credit card fraud has emerged as major problem in the electronic payment sector. In this thesis, we study data-driven fraud detection and address several of its intricate challenges by means of machine learning methods with the goal to identify fraudulent transactions that have been issued illegitimately on behalf of the rightful card owner. In particular, we explore several means to leverage contextual information beyond a transaction’s basic attributes on the transaction level, sequence level and user level.
On the transaction level, we aim to identify fraudulent transactions which, in terms of their attribute values, are globally distinguishable from genuine transactions. We provide an empirical study of the influence of class imbalance and forecasting horizons on the classification performance of a random forest classifier. We augment transactions with additional features extracted from external knowledge sources and show that external information about countries and calendar events improves classification performance most noticeably on card-not-present transactions.
On the sequence level, we aim to detect frauds that are inconspicuous in the background of all transactions but peculiar with respect to the short-term sequence they appear in. We use a Long Short-term Memory network (LSTM) for modeling the sequential succession of transactions. Our results suggest that LSTM-based modeling is a promising strategy for characterizing sequences of card-present transactions but it is not adequate for card-not-present transactions.
On the user level, we elaborate on feature aggregations and propose a flexible concept allowing us define numerous features by means of a simple syntax. We provide a CUDA-based implementation for the computationally expensive extraction with a speed-up of two orders of magnitude over a single-core implementation. Our feature selection study reveals that aggregates extracted from users’ transaction sequences are more useful than those extracted from merchant sequences. Moreover, we discover multiple sets of candidate features with equivalent performance as manually engineered aggregates while being structurally different.
Regarding future work, we motivate the usage of simple and transparent machine learning methods for credit card fraud detection and we sketch a simple user-focused modeling approach.
The main research question of this thesis is to develop a theory that would provide foundations for the development of Web of Things (WoT) systems. A theory for WoT shall provide a model of the ‘things’ WoT agents relate to such that these relations determine what interactions take place between these agents. This thesis presents a knowledge-based approach in which the semantics of WoT systems is given by a transformation (an homomorphism) between a graph representing agent interactions and a knowledge graph describing ‘things’. It focuses on three aspects of knowledge graphs in particular: the vocabulary with which assertions can be made, the rules that can be defined over this vocabulary and its serialization to efficiently exchange pieces of a knowledge graph. Each aspect is developed in a dedicated chapter, with specific contributions to the state-of-the-art.
The need for a unified vocabulary to describe ‘things’ in WoT and the Internet of Things (IoT) has been identified early on in the literature. Many proposals have been consequently published, in the form of Web ontologies. In Ch. 2, a systematic review of these proposals is being developed, as well as a comparison with the data models of the principal IoT frameworks and protocols. The contribution of the thesis in that respect is an alignment between the Thing Description (TD) model and the Semantic Sensor Network (SSN) ontology, two standards of the World Wide Web Consortium (W3C). The scope of this thesis is generally limited to Web standards, especially those defined by the Resource Description framework (RDF).
Web ontologies do not only expose a vocabulary but also rules to extend a knowledge graph by means of reasoning. Starting from a set of TD documents, new relations between ‘things’ can be “discovered” this way, indicating possible interactions between the servients that relate to them. The experiments presented in Ch. 3 were done on the basis of this semantic discovery framework on two use cases: a building automation use case provided by Intel Labs and an industrial control use case developed internally at Siemens. The relations to discover often involve anonymous nodes in the knowledge graph: the chapter also introduces a novel skolemization algorithm to correctly process these nodes on a well-defined fragment of the Web Ontology Language (OWL).
Finally, because this semantic discovery framework relies on the exchange of TD documents, Ch. 4 introduces a binary format for RDF that proves efficient in serializing TD assertions such that even the smallest WoT agents, i.e. micro-controllers, can store and process them. A formalization for the semantics-preserving compaction and querying of TD documents is also introduced in this chapter, at the basis of an embedded RDF store called the µRDF store. The ability of all WoT agents to query logical assertions about themselves and their environment, as found in TD documents, is a first step towards knowledge-based intelligent systems that can operate autonomously and dynamically in a decentralized way. The µRDF store is an attempt to illustrate the practical outcomes of the theory of WoT developed throughout this thesis.
Service Provisions and Business Relationships in the Digital Era – Four Essays in the B2B Context
(2019)
Digitalization has fundamentally changed how services are provided and how service providers and their customers interact with each other in the business-to-business (B2B) context. Against the backdrop of these developments, this thesis considers – in four essays – the changes brought about by both service and sales digitalization. Each essay investigates for one research topic the aspects of existing knowledge regarding non-digital services and/or sales which can be transferred to digital services and sales and which aspects must be adjusted. The aim is to support B2B firms that offer or receive services or plan to do so in the future which cope with the challenges of service and sales digitalization.
In doing so, the first and second essay investigate the contingency effect of service digitalization on service characteristics from the provider and customer views, respectively. Both essays aim at explaining service value as an endogenous variable. In the first essay, service modularity and service flexibility are considered as predecessors that help explain service value. The second essay investigates the effect of customer cocreation on service value. Whereas the first and second essay focus on service characteristics, the third and fourth essay focus on business relationships. Both essays explain relational conflict, one important facet of business relationships, as the endogenous variable and consider the perspectives of both providers and customers. The third essay elaborates on the diverging effect of service digitalization on relational conflict from these two perspectives. The fourth essay incorporates both service and sales digitalization and investigates the contingency effects of the two forms of digitalization on the relationship between coercive power use and relational conflict.
In conclusion, this thesis provides a more fine-grained view on the construct digitalization by differentiating explicitly between service digitalization and sales digitalization and introduces a new conceptualization of service (see all four essays) and sales digitalization (see the fourth essay) by treating digitalization as a continuum. Furthermore, this thesis investigates the opportunities and challenges brought about by digitalization. In particular, the first and second essays show the opportunities service digitalization creates for providers, who could benefit from service modularity, and customers, who could benefit from the integration of their own resources into service provisions. In addition, the third essay shows that for providers service digitalization has a positive and for customers contrarily a negative effect on relation conflict. The fourth essay shows that sales and service digitalization positively moderate the effect of coercive power use on relational conflict for weaker parties in business relationships (except for weaker providers) but not for stronger parties. In sum, this thesis contributes to a better understanding of the consequences of service and sales digitalization and provides recommendations for companies facing challenges and decisions related to this development.
Blockchains and distributed ledger technology (DLT) that rely on Proof-of-Work (PoW) typically show limited performance. Several recent approaches incorporate Byzantine fault-tolerant (BFT) consensus protocols in their DLT design as Byzantine consensus allows for increased performance and energy efficiency, as well as it offers proven liveness and safety properties. While there has been a broad variety of research on BFT consensus protocols over the last decades, those protocols were originally not intended to scale for a large number of nodes. Thus, the quest for scalable BFT consensus was initiated with the emerging research interest in DLT. In this paper, we first provide a broad analysis of various optimization techniques and approaches used in recent protocols to scale Byzantine consensus for large environments such as BFT blockchain infrastructures. We then present an overview of both efforts and assumptions made by existing protocols and compare their solutions.
In geo-replicated systems, the heterogeneous latencies of connections between replicas limit the system’s ability to achieve fast consensus. State machine replication (SMR) protocols can be refined for their deployment in wide-area networks by using a weighting scheme for active replication that employs additional replicas and assigns higher voting power to faster replicas. Utilizing more variability in quorum formation allows replicas to swifter proceed to subsequent protocol stages, thus decreasing consensus latency. However, if network conditions vary during the system’s lifespan or faults occur, the system needs a solution to autonomously adjust to new conditions. We incorporate the idea of self-optimization into geographically distributed, weighted replication by introducing AWARE, an automated and dynamic voting weight tuning and leader positioning scheme. AWARE measures replica-replica latencies and uses a prediction model, thriving to minimize the system’s consensus latency. In experiments using different Amazon EC2 regions, AWARE dynamically optimizes consensus latency by self-reliantly finding a fast weight configuration yielding latency gains observed by clients located across the globe.
In the last decade, crowdsourcing has proved its ability to address large scale data collection tasks, such as labeling large data sets, at a low cost and in a short time. However, the performance and behavior variability between workers as well as the variability in task designs and contents, induce an unevenness in the quality of the produced contributions and, thus, in the final output quality. In order to maintain the effectiveness of crowdsourcing, it is crucial to control the quality of the contributions. Furthermore, maintaining the efficiency of crowdsourcing requires the time and cost overhead related to the quality control to be at its lowest. While effective, current quality control techniques such as contribution aggregation, worker selection, context-specific reputation systems, and multi-step workflows, suffer from fairly high time and budget overheads and from their dependency on prior knowledge about individual workers.
In this thesis, we address this challenge by leveraging the similarity between completed and incoming tasks as well as the correlation between the worker declarative profiles and their performance in previous tasks in order to perform an efficient task-aware worker selection. To this end, we propose CAWS (Context AwareWorker Selection) method which operates in two phases; in an offline phase, completed tasks are clustered into homogeneous groups for each of which the correlation with the workers declarative profile is learned. Then, in the online phase, incoming tasks are matched to one of the existing clusters and the correspondent, previously inferred profile model is used to select the most reliable online workers for the given task. Using declarative profiles helps eliminate any probing process, which reduces the time and the budget while maintaining the crowdsourcing quality. Furthermore, the set of completed tasks, when compared to a probing task split, provides a larger corpus from which a more precise profile model can be learned. This translates to a better selection quality, especially for harder tasks.
In order to evaluate CAWS, we introduce CrowdED (Crowdsourcing Evaluation Dataset), a rich dataset to evaluate quality control methods and quality-driven task vectorization and clustering. The generation of CrowdED relies on a constrained sampling approach that allows to produce a task corpus which respects both, the budget and type constraints. Beside helping in evaluating CAWS, and through its generality and richness, CrowdED helps in plugging the benchmarking gap present in the crowdsourcing quality control community.
Using CrowdED, we evaluate the performance of CAWS in terms of the quality of the worker selection and in terms of the achieved time and budget reduction. Results shows the following: first, automatic grouping is able to achieve a learning quality similar to job-based grouping. And second, CAWS is able to outperform the state-of-the-art profile-based worker selection when it comes to quality. This is especially true when strong budget and time constraints are present on the requester side.
Finally, we complement our work by a software contribution consisting of an open source framework called CREX (CReate Enrich eXtend). CREX allows the creation, the extension and the enrichment of crowdsourcing datasets. It provides the tools to vectorize, cluster and sample a task corpus to produce constrained task sets and to automatically generate custom crowdsourcing campaign sites.
In the public debate it is often assumed that communication in so-called “Echo Chambers” - online structures in which like-minded people share mostly messages that confirm their mutual, shared attitudes - can lead to negative outcomes such as increased societal polarization between groups holding opposing beliefs. This thesis aimed to examine this assumption from a psychological perspective and substantiate it empirically. First, based on existing research and psychological theories, a working definition of Echo Chambers was formulated, that highlights two key factors: Selective Exposure to attitudinally congruent messages and communication in homogeneous networks. Then, three studies were conducted to test links between these factors and two individual-level outcomes that are associated to subjects’ actual behavior: Their False Consensus, that is, how strongly subjects perceive the public in agreement with their own attitudes, and their Intergroup Bias, which reflects to which degree subjects’ identify as members of an in-group that is in conflict with negatively perceived out-groups. The studies employed questionnaire-based, experimental, as well as real-word data driven approaches. Overall, they confirm that exposure to Echo Chamber-like online structures can indeed lead to a more favorably distorted perception of public opinions and to more signs of Intergroup Bias in subjects’ communicational style. Thus, the thesis provides first psychologically founded empirical evidence for effects of online Echo Chamber exposure on behavior-related individual-level outcomes. The results can serve as a basis for further research as well as for the discussion of possible strategies to counter negative effects of online Echo Chambers.
Die Forschung zu Lehrkrafturteilen hat in den letzten drei Jahrzehnten beträchtliche Fortschritte gemacht. Die Bedeutung des Lehrkrafturteils und die Variabilität in der Urteilsgenauigkeit erfordern eine eingehendere Untersuchung. Basierend auf der Überprüfung früherer Studien wurde ein systematischer analytischer Rahmen vorbereitet, der aus drei Hauptstudien besteht, um das Verständnis der Prozesse und Merkmale von Lehrkrafturteilen zu erweitern. In den drei vorgestellten Studien wurde insbesondere untersucht, wie Lehrkrafturteile durch verschiedene Schülermerkmale generiert werden, welche Möglichkeiten es gibt, die Urteilsgenauigkeit von Lehrkräften zu verbessern und ob die Urteilsgenauigkeit von Lehrkräften im Laufe der Zeit stabil bleiben kann.
In der ersten Studie wurde das Linsenmodell der Theorie der sozialen Beurteilung angewendet, um die Einschätzungen von Lehrpersonen über die Leistung von Schülerinnen und Schülern und ihre Strategien der Informationsverarbeitung besser zu verstehen. 260 Lehrkräfte aus sieben chinesischen Grundschulen wurden gebeten, aus sieben Informationsquellen Schülermerkmale auszuwählen und zu bewerten, anhand derer sie die Leistungen der Schüler beurteilen könnten. Die Lehrpersonen entwickelten eine klare Hierarchie der verwendeten Datenquellen. Die besten Informationen wurden aus den Fähigkeiten und Einstellungen der Schülerinnen und Schüler gewonnen und die am wenigsten wichtigen Informationen aus der sozialen Interaktion mit anderen sowie aus der Schüler-Demografie. Um genauere Einschätzungen zu treffen, sollten die Lehrkräfte über gültige Indikatoren für die Schülerleistung informiert werden.
Die zweite Studie zielte darauf ab, die Urteilsgenauigkeit von Lehrkräften und die Leistung der Schülerinnen und Schüler durch den Einsatz von Classroom-Response-Systemen („Clickern“) zu fördern. 20 Schulklassen mit 459 Schülerinnen und Schülern der sechsten Klasse und ihren Mathematiklehrkräften wurden für eine fünfwöchige quasi-experimentelle Interventionsstudie mit einem Pre- und Post-Test in drei Gruppen eingeteilt. Die Ergebnisse zeigen, dass beide Ziele weitgehend erreicht werden konnten. Schülerinnen und Schüler der Clicker-Gruppe haben durch die Intervention mehr mathematisches Wissen erworben als Studenten der Tagebuch- und Kontrollgruppe. Die Lehrkrafturteile aller drei Gruppen wurden vom Pre- zum Post-Test genauer. Lehrpersonen, die Clicker verwendeten, beurteilten jedoch mit höchster Genauigkeit. Clicker können als wertvolles Werkzeug zur Verbesserung der Urteilsgenauigkeit von Lehrkräften empfohlen werden.
In der dritten Studie wurde die zeitliche Stabilität der Urteilsgenauigkeit der Lehrkräfte hinsichtlich Motivation, Emotion und Leistung der Schülerinnen und Schüler untersucht. Neun Klassen mit 326 Sechstklässlern einer chinesischen Grundschule und ihren Mathematiklehrpersonen nahmen an der Studie teil. Die Schüler arbeiteten an einem standardisierten Mathematik-Test und einem Selbstbeschreibungsfragebogen zu Motivation und Emotion. Die Lehrpersonen beurteilten die Motivation, Emotion und Leistung jedes einzelnen Schülers anhand einzelner Items. Das Lehrkrafturteil und die Eigenschaften der Schülerinnen und Schüler wurden innerhalb von vier Wochen zweimal gemessen. Die Ergebnisse zeigten, dass die Lehrkräfte in der Lage waren, die Schülerleistungen mit hoher Genauigkeit, die Motivation der Schülerinnen und Schüler mit mäßiger bis hoher Genauigkeit und die Emotion der Schülerinnen und Schüler meist mit geringer Genauigkeit zu bewerten. Die Urteilsgenauigkeit der Lehrpersonen war sehr stabil mit nur geringen Veränderungen an den verschiedenen Genauigkeitskomponenten. Es kann gefolgert werden, dass chinesische Grundschullehrkräfte in der Lage sind, zu verschiedenen Zeitpunkten faire Urteile über Schülerleistungen und der Motivation ihrer Schülerinnen und Schüler zu treffen. Die Emotionen der Schülerinnen und Schüler sind für Lehrpersonen jedoch schwer zu erfassen.
Software has become an important part of our life. Therefore, the number of different applications scenarios and user requirements of software systems grows rapidly. To satisfy these requirements, software vendors build configurable software systems that can be tailored to diverse needs without rebuilding them from scratch, which reduces costs and development time.
Despite considerable advances in software engineering, which allow building high-quality configurable software systems, some challenges remain. One of these challenges is the feature interaction problem that arises when parts (features), from which a configurable system is composed, interact in unexpected ways, and inadvertently change the behavior or quality attributes (such as performance) of the system.
The goal of this dissertation is to systematically study the nature of feature interactions, their causes, their influence on performance of configurable systems, and, based on empirical results, suggest ways of improving techniques for detecting and predicting feature interactions.
More specifically, we compared and evaluated different strategies for the analysis of configurable software systems. The results of our evaluation complement empirical data from previous work about how different analysis strategies for configurable software systems compare with respect to different aspects, such as performance. These results shall be used to develop effective and scalable techniques and tools for analysis of configurable software including feature-interaction detection and prediction techniques and tools.
Technically, we used a machine-learning technique to quantify the influence of feature interactions on performance of real-world configurable systems. We studied the characteristics of interactions that have the largest influence on performance and found that interactions among few features have higher influence than interactions among many features. With a growing number of interacting features, the influence of the corresponding interactions decreases consistently. This implies that interactions involving multiple features can be ignored in practice because of their marginal influence on performance. We also investigated the causes of the interactions and were able to identify several patterns that link these interactions to the architecture of the systems: For example, we found that if a data processing system consisted of multiple features that processed the same data in sequence then these features interacted. The identified patterns can help to anticipate performance interactions already at an early development stage when a system’s architecture is designed.
Furthermore, considering that control-flow interactions (observable at the level of control flow among features) are easier to detect than performance interactions (externally observable through measuring performance of different combinations of features), we conducted a case study on two configurable systems. In this case study, we investigated a possible relation among control-flow feature interactions and performance feature interactions. We also discussed how this relation can be exploited by interaction detection and performance prediction techniques to make them more time efficient and precise. Our case study on two real-world configurable systems revealed that a relation indeed exists, and we were able to show how it can be used to reduce the search space of possibly existing performance interactions. The study can serve as a blueprint for further studies that can rely on our conceptual framework for investigating relations among external and internal interactions.
Overall, the contribution of this dissertation consists of scientific and technical insights, practical tool implementations, empirical evaluations, and case studies that advance the current state of research in the area of feature interactions in configurable software systems. In particular, we provide insights into the causes of feature interactions and their influence on performance of real-world configurable systems (e.g., interaction patterns, decreasing influence of interactions with growing number of involved features). Our results also suggest ways of improving techniques for detecting and predicting feature interactions (e.g., ignoring interactions among multiple features, reducing the search space based on relations among interactions).
The Semantic Web exists for about 20 years by now, but its applicability as well as its presence does not live up to the standards of its original idea. Incorporated Semantic Web Technologies do have an initial barrier to learn and apply, which can discourage many potential users. This leads to less available data overall in addition to decreased data quality.
This work solves parts of the aforementioned problem by supporting idiomatic entry to those Semantic Web Technologies, allowing for "easier" accessibility and usability. Anno4j is a Java library that implements a form of Object-Relational Mapping for RDF data. With its application, RDF data can be created via a mapping by simply instantiating Java objects - an object-oriented programming concept the user is familiar with. On the other side, requesting persisted data is supported by a path-based querying possibility, while other features like transactional behaviour, code generation, and automated validation of input contribute to a more effective, comprehensive, and straightforward usage.
A use-case is provided by the MICO Platform, a centralized software instance that connects autonomous multimedia extractors in a workflow-driven fashion. This leads to a rich metadata background for the inserted multimedia files, enabling them to be used in diverse scenarios as well as unlocking yet hidden semantics. For this task it was necessary to design and implement a metadata model that is able to aggregate and merge the varying extractor results under a common denominator: the MICO Metadata Model.
The results of this work allow the use case to incorporate idiomatic Semantic Web Technologies which are then usable natively by non-Semantic Web experts. Additionally, an increase has been achieved in forms of data integration, synchronisation, integrity and validity, as well as an overall more comprehensive and rich implementation of the multimedia extractors.
Analysing security assumptions taken for the WebRTC and postMessage APIs led us to find a novel attack abusing the browsers' persistent storage capabilities. The presented attack can be executed without the website's visitor knowledge, and it requires neither browser vulnerabilities nor additional software on the browser's side. To exemplify this, we study how can an attacker use browsers to create a network for persistent storage and distribution of arbitrary data.
In our proof of concept, the total storage of the network, and therefore the space used within each browser, grows linearly with the number of origins delivering the malicious JavaScript code. Further, data transfers between browsers are not restricted by the Same Origin Policy, which allows for a unified cross-origin browser network, regardless of the origin from which the script executing the functionality is loaded from.
In the course of our work, we assess the feasibility of a real-life deployment of the network by running experiments using Linux containers and browser automation tools. Moreover, we show how security mechanisms against third-party tracking, cross-site scripting and click-jacking can diminish the attack's impact, or even prevent it.
We introduce a new browser abuse scenario where an attacker uses local storage capabilities without the website's visitor knowledge to create a network of browsers for persistent storage and distribution of arbitrary data. We describe how security-aware users can use mechanisms such as the Content Security Policy (CSP), sandboxing, and third-party tracking protection, i.e., CSP & Company, to limit the network's effectiveness. From another point of view, we also show that the upcoming Suborigin standard can inadvertently thwart existing countermeasures, if it is adopted.
Direct access to the system's resources such as the GPU, persistent storage and networking has enabled in-browser crypto-mining. Thus, there has been a massive response by rogue actors who abuse browsers for mining without the user's consent. This trend has grown steadily for the last months until this practice, i.e., CryptoJacking, has been acknowledged as the number one security threat by several antivirus companies.
Considering this, and the fact that these attacks do not behave as JavaScript malware or other Web attacks, we propose and evaluate several approaches to detect in-browser mining. To this end, we collect information from the top 330.500 Alexa sites. Mainly, we used real-life browsers to visit sites while monitoring resource-related API calls and the browser's resource consumption, e.g., CPU.
Our detection mechanisms are based on dynamic monitoring, so they are resistant to JavaScript obfuscation. Furthermore, our detection techniques can generalize well and classify previously unseen samples with up to 99.99\% precision and recall for the benign class and up to 96\% precision and recall for the mining class. These results demonstrate the applicability of detection mechanisms as a server-side approach, e.g., to support the enhancement of existing blacklists.
Last but not least, we evaluated the feasibility of deploying prototypical implementations of some detection mechanisms directly on the browser. Specifically, we measured the impact of in-browser API monitoring on page-loading time and performed micro-benchmarks for the execution of some classifiers directly within the browser. In this regard, we ascertain that, even though there are engineering challenges to overcome, it is feasible and beneficial for users to bring the mining detection to the browser.
Allowing users to control access to their data is paramount for the success of the Internet of Things; therefore, it is imperative to ensure it, even when data has left the users' control, e.g. shared with cloud infrastructure. Consequently, we propose several state of the art mechanisms from the security and privacy research fields to cope with this requirement.
To illustrate how each mechanism can be applied, we derive a data-centric architecture providing access control and privacy guaranties for the users of IoT-based applications. Moreover, we discuss the limitations and challenges related to applying the selected mechanisms to ensure access control remotely. Also, we validate our architecture by showing how it empowers users to control access to their health data in a quantified self use case.
This doctoral thesis is dedicated to improve a linear algebra attack on the so-called braid group-based Diffie-Hellman conjugacy problem (BDHCP). The general procedure of the attack is to transform a BDHCP to the problem of solving several simultaneous matrix equations. A first improvement is achieved by reducing the solution space of the matrix equations to matrices that have a specific structure, which we call here the left braid structure. Using the left braid structure the number of matrix equations to be solved reduces to one. Based on the left braid structure we are further able to formulate a structure-based attack on the BDHCP. That is to transform the matrix equation to a system of linear equations and exploiting the structure of the corresponding extended coefficient matrix, which is induced by the left braid structure of the solution space. The structure-based attack then has an empirically high probability to solve the BDHCP with significantly less arithmetic operations than the original attack. A third improvement of the original linear algebra attack is to use an algorithm that combines Gaussian elimination with integer polynomial interpolation and the Chinese remainder theorem (CRT), instead of fast matrix multiplication as suggested by others. The major idea here is to distribute the task of solving a system of linear equations over a giant finite field to several much smaller finite fields. Based on our empirically measured bounds for the degree of the polynomials to be interpolated and the bit size of the coefficients and integers to be recovered via the CRT, we conclude an improvement of the run time complexity of the original algorithm by a factor of n^8 bit operations in the best case, and still n^6 in the worst case.
Free digital platforms constitute one of the most important phenomena of modern times; they create value by bringing together customer groups that would not have interacted without digital technology or that could have done so only by incurring increased costs. In the free digital platform model, firms pay for the interaction with end consumers that use the digital platform for free. Extant research on two-sided markets has provided rich evidence for how digital platforms can attract enough members from both customer groups to enable the interaction between the customer groups. However, this research lacks insights into how free
digital platforms can create value for their customer groups once these customer groups joined the platform, and extract this value for themselves.
To address this substantial research gap, in this dissertation, I investigate the overall research question of how activities of free digital platforms affect the value creation for their customer groups and the ability of the platform to extract this value. In a first step, I examine this value creation and value extraction by focusing on concrete activities of free digital platforms. In Study 1, I investigate how offering firms the possibility of personalizing and positioning their search ads on search engines affects consumers’ search engine click behavior. In Study 2, I examine how adapting ad positions to consumers’ previous online shopping behavior on search engines influences consumers’ click and conversion behavior. In Study 3, I investigate the impact of a review platform’s policy of tagging reviews as written on either mobile or nonmobile devices on consumers’ perceptions of review helpfulness. In a second step, in Study 4, I generalize these findings by investigating the overall impact of such customer-oriented activities on value creation for customer groups and on the extraction of this value by free digital platforms.
These four studies yield three major findings. First, free digital platforms’ activities toward one customer group always affect the value creation of the other customer group as well. Second, free digital platforms should emphasize value creation activities especially for non-paying customer groups. Third, internal, operative, and macro-environments influence the value creation and value extraction of free digital platforms.
With this dissertation, I make substantial contributions to research on two-sided markets, customer orientation, search engine advertising, and online reviews. In addition, my dissertation provides numerous actionable recommendations for managers of free digital platforms and outlines promising avenues for further research.
In three studies, this dissertation contributes to the link between, on the one hand, how a firm’s supply chain is organized and, on the other, how good its financial and stock market performance is. Study I examines the relationship between the degree of vertical integration and financial performance. Study II links the degree of vertical integration, both theoretically and empirically, to long-term stock returns. Study III concentrates on the relationship between inventory efficiency and financial performance.
An increasing number of companies report that eco-sustainable initiatives have a positive impact on firms’ economic performance and concurrently allow the combination of social and commercial goals by optimizing environmental and economic decisions simultaneously. These initiatives are considered an integral part of organizational sustainability transformations, which are a special case of multilayered, complex organizational change efforts that relate to environmental, organizational, and individual factors. Institutional logics and information systems (IS) have shown to be two important perspectives from which to explore mechanisms and processes central to organizational sustainability transformations. Institutional logics offer a unique perspective to investigate organizational change for sustainability because they provide a new approach to organizational change that incorporates macro structures, culture, and agency to explain how actions are enabled or constrained. It thus allows for insights into the complex and miscellaneous interplay of external and internal determinants that govern organizational transformation processes towards sustainability. By providing insights into institutional changes of practice and behaviors, an institutional logic perspective allows for a detailed analysis of organizational transformations. Within these change processes, IS have shown to be an efficient and pervasive tool to leverage sustainability by integrating human and technological factors. Since IS have become a key resource for the encouragement of organizational sustainability transformations, adopting an IS perspective allows for an understanding of mechanisms and processes that enable IS to foster sustainability in organizations. Thus, this dissertation draws on four studies by investigateing an institutional logic perspective as well as an IS perspective to explore organizational sustainability transformations and facilitate an in-depth understanding of organizational, human, and technological factors that encourage sustainability in organizational transformations.
Information has a particular importance in online purchase decision processes. As opposed to consumers in online markets, consumers in online markets cannot inspect the physical product to evaluate it and reduce their perceived risk. Hence, consumers in online markets are dependent upon the information that they can gather about a product in which they are interested. Therefore, they have two primary sources of information: Product descriptions and customer reviews. Both sources affect consumers’ purchase decision processes and hence have an economic impact for consumers, shop providers and manufacturers. It is important to know how these sources of information influence a customer’s online purchase decision and how to extract the relevant information.
To examine these research objectives, several studies applying different methodological approaches have been conducted. The results are presented in this dissertation.
In the age of globalization, exponential growth and digitalization, organizations need to make faster decisions, as well as continually innovate and adapt to changing customer needs to ensure their long-term competitiveness (Kammerlander et al. 2018; Magnusson and Martini 2008). Notably, large and established companies find it difficult to keep up with start-ups and smaller companies as well as with digital transformation (Christensen et al. 2015).
Thus, organizations are increasingly providing their workforce with Enterprise Social Networks (ESNs) as intra-organizational social software platforms.
Although ESNs hold great promises for organizations and their employees (Mäntymäki and Riemer 2016), most ESN initiatives fail to leverage the intended benefits (Chin et al. 2015). This dissertation seeks to open up the black box behind this seemingly paradoxical relationship.
It comprises four studies that are guided by the following research questions:
R 1: How do different types of users (posters and lurkers) differ in their motivations for participating in ESNs? (= Paper 1)
R 2: Why do employees deliberately not use the ESN? (= Paper 2)
R 3: How can ESNs be successfully implemented and improved to overcome the challenges perceived by employees? (= Paper 3)
R 4: Does ESN usage impact on individual task performance? And how can ESNs be used effectively to increase performance outcomes? (= Paper 4)
Overall, the four studies contribute to a better understanding of the non-adoption phenomenon of ESNs, provide rich insights on employees’ underlying reasons and challenges regarding ESN usage, while underscoring the potential value of ESNs.
This cumulative thesis consists of six single contributions: five independent essays and an introductory chapter. All of the conributions have been published or accepted for publication. The overarching scope of these essays is to analyze different factors accounting for the stability of post-Soviet authoritarian regimes and the obstacles, which Western democracy promoters can face when dealing with autocrats. The starting point for these enquiries has been the striking inability of Western democracies and in particular of the European Union to encourage and to assist political transformation in the majority of the post-Soviet republics.
Securitization Theory has been applied and advanced continuously since the publication of the seminal work “Security – A New Framework for Analysis” by Buzan et al. in 1998. Various extensions, clarifications and definitions have been added over the years. Ontological and epistemological debates as well as debates about the normativity of the concept have taken place, furthering the approach incrementally and adapting it to new empirical cases. This paper aims at contributing to the improvement of the still useful framework in a more general way by amending it with well-established findings from another discipline: Psychology. The exploratory article will point out what elements of Securitization Theory might benefit most from incorporating insights from Psychology and in which ways they might change our understanding of the phenomenon. Some well-studied phenomena in the field of (Social) Psychology, it is argued here, play an important role for the construction and perception of security threats and the acceptance of the audience to grant the executive branch extraordinary measures to counter these threats: availability heuristic, loss-aversion and social identity theory are central psychological concepts that can help us to better understand how securitization works, and in which situations securitizing moves have great or little chances to reverberate. The empirical cases of the 9/11 and Paris terror attacks will serve to illustrate the potential of this approach, allowing for variances in key factors, among them: (point in) time, system of government and ideological orientation. As a hypotheses-generating pilot study, the paper will conclude by discussing further research possibilities in the field of Securitization.
In this thesis I empirically assess a wide range of constraints faced by different types of entrepreneurs in developing countries and the effectiveness of different policy interventions aimed at removing them. Thereby, the thesis contributes to the growing literature on enterprises and entrepreneurial activities in developing countries, by producing valuable evidence on which are the constraints faced by which types of entrepreneurs in starting, surviving, and growing, as well as on which interventions work, and for whom. The thesis hence provides important insights for policy formulation aimed at inclusive growth.
It consists of three self-contained papers, which put different emphasis on three different areas in which important research gaps remain. The first paper, which is presented in chapter 2, focuses on interventions aimed at removing firm-level shocks. It consists of a systematic review of evaluations of targeted programs and broader policies that intend to promote micro-, small and medium-sized enterprises (MSMEs) in developing countries, and assesses which of these interventions are effective in creating jobs. The paper presented in chapter 3 considers death of small, mainly one-person and household businesses. Together with my co-author, I collated panel data on more than 14,000 small firms from 16 firm panel surveys conducted in 12 developing countries. We use this unique panel dataset to provide answers to the following questions: What is the rate of firm death over different horizons? Which firms are more likely to die? Why do they die and what happens afterwards? In chapter 4, I take a closer look at household-level shocks and non-separability between the household and the firm, and assess whether extending health insurance to previously uninsured households leads to increased investment in productive activities, by assessing the impact of a large national health insurance scheme, the Mexican Seguro Popular, on investment in productive agricultural and non-agricultural assets and activities in rural areas. Using panel data from the Mexican rural evaluation surveys of the Oportunidades cash transfer program, I estimate the effect of the program on out-of-pocket health care expenditures and productive assets and account for possible self-selection of households into the program, using difference-in-differences estimation, as well as a propensity score matched difference-in-differences specification.
This study examines the dynamics which lead to revitalization of everyday life in the public spaces of Cagayan de Oro, a medium-sized urban center in Northern Mindanao, the Philippines. By employing the oriental philosophies together with western thoughts such as Henri Lefebvre, Alain Touraine and Jürgen Habermas, this study elucidates that the core of perceived, lived and conceived spaces is ‘the Subject.’ Once the Subject utilizes the public sphere to instill social action, social space is ultimately produced. Hawkers, grassroots environmental activists, street readers and artists are the social Subjects who partake in the vibrancy of public spaces. The social Subjects utilize public spaces as venues of social transformation. Thus, this study argues that the social Subjects’ role in democratic process lead to inclusivity of the marginalized sector in the public spaces of the city.
Due to the need for fast and energy-efficient accesses to growing amounts of data, the share and number of embedded memories inside modern microchips has been continuously increasing within the last years. Since embedded memories have the highest integration density of a fabrication technology they pose special test challenges due to complex manufacturing defects as well as strong transistor aging phenomena. This necessitates efficient methods for detecting more subtle defects while keeping test costs low. This work presents novel methods and techniques for improving the efficiency of embedded memory manufacturing tests. The proposed methods are demonstrated in an industrial setting based on production-proven transistor, memory as well as chip models and their benefits over the current state-of-the art is worked out.
While in some Eastern European countries a wave of colored revolutions challenged existing political orders, Belarus has remained largely untouched by mass protests. In Minsk, the diffusion of democratic ideas leading to the mobilization of population meets a stable authoritarian regime. Nevertheless, the stagnating democratization process cannot be only attributed to the strong authoritarian rule and abuse of power. Indeed, Belarusian president Alexander Lukashenko still enjoys popularity by a large part of the population. Although international observers report that elections in Belarus have never been free and fair, few commentators doubt that Lukashenko would not have won in democratic elections. This evidence suggests that the regime succeeded in building a strong legitimizing basis, which has not been seriously challenged during the last two decades. This paper explores the authoritarian stability in Belarus by looking at the patterns of state ideology. The government effectively spreads state ideology since the early 2000s. Ideology departments have been created in almost all state institutions. The education sector has been affected by the introduction of the compulsory course "The Fundamentals of Belarusian State Ideology" at all universities, and increasing attention to the patriotic education at schools. Based on document analysis, I trace the creation of "ideological vertical" in Belarus and focuse on the issue of ideology in education and youth policy sectors.
Previous laboratory studies on the centipede game have found that subjects exhibit surprisingly high levels of cooperation. Across disciplines, it has recently been highlighted that these high levels of cooperation might be explained by “team reasoning”, the willingness to think as a team rather than as an individual. We run an experiment with a standard centipede game as a baseline. In two treatments, we seek to induce team reasoning by making a joint goal salient. First, we implement a probabilistic variant of the centipede game that makes it easy to identify a joint goal. Second, we frame the game as a situation where a team of two soccer players attempts to score a goal. This frame increases the salience even more. Compared to the baseline, our treatments induce higher levels of cooperation. In a second experiment, we obtain similar evidence in a more natural environment–a beer garden during the 2014 FIFA Soccer World Cup. Our study contributes to understanding how a salient goal can support cooperation.
This thesis distills technical requirements for an increased probative value and data protection compliance, and maps them onto cryptographic properties for which it constructs provably secure and especially private malleable signature schemes (MSS). MSS are specialised digital signature schemes that allow the signatory to authorize certain subsequent modifications, which will not negatively affect the signature verification result.
Legally, regulations such as European Regulation 910/2014 (eIDAS), ‘follow-up’ to longstanding Directive 1999/93/EC, describe the requirements in technology-neutral language. eIDAS states that, when a digital signature meets the full requirements it becomes a qualified electronic signature and then it “[...] shall have the equivalent legal effect of a handwritten signature [...]” [Art. 25 Regulation 910/2014]. The question of what legal effect this has with regards to the probative value that is assigned is actually not determined in EU Regulation 910/2014 but in European member state law. This thesis concentrates in its analysis on the — in this respect detailed — German Code of Civil Procedure (ZPO). Following the ZPO, a signature awards the signed document with at least a high probative value of prima facie evidence. For signed documents of official authority the ZPO’s statutory rules even award evidence with a legal presumption of authenticity. This increased probative value is also awarded to electronic documents bearing electronic signatures when those conform to the eIDAS requirements. The requirements centre around the technical security goals of integrity and accountability. Technical mechanisms use cryptographic means to detect the absence of unauthorized modifications (integrity) and allow to authenticate the signed document’s signatory (accountability).
However, the specialised malleable signature schemes’ main advantage is a cryptographic property termed privacy: An authorized subsequent modification will protect the confidentiality of the modified original. Moreover, the MSS will retain a verifiable signature if only authorized modifications were carried out. If these properties are reached with provable security the schemes are called private malleable signature schemes. This thesis analyses two forms of MSS discussed in existing literature: Redactable signature schemes (RSS) which allow subsequent deletions, and sanitizable signature schemes (SSS) which allow subsequent edits. These two forms have many application scenarios: A signatory can delegate that a later redaction might take place while retaining the integrity and authenticity protection for the still remaining parts. The verification of a signature on a redacted or sanitized document still enables the verifying entity to corroborate the signatory’s identity with the help of flanking technical and organisational mechanisms, e.g. a trusted public key infrastructure. The valid signature further corroborates the absence of unauthorized changes, because the MSS is still cryptographically protecting the signed document from undetected unauthorized changes inflicted by adversaries. Due to the confidentiality protection for the overwritten parts of the document following from cryptographic privacy the sanitization and redaction can be used to safeguard personal data to comply with data protection regulation or withhold trade-secrets.
The research question is: Can a malleable signature scheme be private to be compliant with EU data protection regulation and at the same time fulfil the integrity protection legally required in the EU to achieve a high probative value for the data signed?
Answering this requires to understand the protection requirements in respect to accountability and integrity rooted in Regulation 910/2014 and related legal texts. This thesis has analysed the previous Directive 1999/93/EC as well as German SigG and SigVO or UK and US laws. Besides that, legal texts, laws and regulations for the protection requirements of personal data (or PII) have been analysed to distill the confidentiality requirements, e.g. the German BDSG or the EU Regulation 2016/679 (GDPR). Moreover, an answer to the research question entails understanding the relevant difference between regular digital signature schemes, like RSASSA-PSS from PKCS-v2.2 [422], which are legally accepted mechanisms for generating qualified electronic signatures and MSS for which the legal status was completely unknown before the thesis. Especially as MSS allow the authorized entity to adapt the signature, such that it is valid after the authorized modification, without the knowledge or use of the signatory’s signature generation key. On verification of an MSS the verifying entity still sees a valid signature technically appointing the legal signatory as the origin of a document, which might — however — have undergone authorized modifications after the signature was applied.
The thesis documents the results achieved in several domains:
1. Analysis of legal requirements towards integrity protection for an increased probative value and towards the confidentiality protection for use as a privacy-enhancing-technique to comply with data protection regulation.
2. Definition of a suitable terminology for integrity protection to capture (a) the differences between classical and malleable signature schemes, (b) the subtleties among existing MSS, as well as (c) the legal requirements.
3. Harmonisation of existing MSS and their cryptographic properties and the analysis of their shortcomings with respect to the legal requirements.
4. Design of new cryptographic properties and their provably secure cryptographic instantiations, i.e., the thesis proposes nine new cryptographic constructions accompanied by rigorous proofs of their security with respect to the formally defined cryptographic properties.
5. Final evaluation of the increased probative value and data-protection level achievable through the eight proposed cryptographic malleable signature schemes.
The thesis concludes that the detection of any subsequent modification (authorized and unauthorized) is of paramount legal importance in order to meet EU Regulation 910/2014. Further, this thesis formally defined a public form of the legally requested integrity verification which allows the verifying entity to corroborate the absence of any unauthorized modifications with a valid signature verification while simultaneously detecting the presence of an authorized modification — if at least one such authorized modification has subsequently occurred. This property, called non-interactive public accountability (PUB), has been formally defined in this thesis, was published and has already been adopted by the academic community. It was carefully conceived to not negatively impact a base-line level of privacy protection, as non-interactive public accountability had to destroy an existing strong privacy notion of transparency, which was identified as a hinderance to legal equivalence arguments. With RSS and SSS constructions that meet these properties, the thesis can give a positive answer to the research question:
Private MSS can reach a level of integrity protection and guarantee a level of accountability comparable to that of technical mechanisms that are legally accepted to generate qualified electronic signatures giving an increased probative value to the signed document, while at the same time protect the overwritten contents’ confidentiality.
Performance optimization of stencil codes requires data locality improvements. The polyhedron model for loop transformation is well suited for such optimizations with established techniques, such as the PLuTo algorithm and diamond tiling. However, in the domain of our project ExaStencils, stencil codes, it fails to yield optimal results. As an alternative, we propose a new, optimized, multi-dimensional polyhedral search space exploration and demonstrate its effectiveness: we obtain better results than existing approaches in several cases. We also propose how to specialize the search for the domain of stencil codes, which dramatically reduces the exploration effort without significantly impairing performance.
Smart Grids integrate currently isolated power and communications networks, while introducing several new technologies on the hardware and software sides. One of the most important ingredients is the potential for demand-response programs, which offer the possibility of sending instructions to consumers to adapt their power consumption over a certain period of time. However, high-frequency data collection exposes consumers’ usage behaviors, leading to security and privacy challenges for Smart Grids.
In this thesis, three cryptographic schemes are constructed for different demand-response programs. In the mandatory incentive-based demand-response program, privacy preservation depends on the power consumption of consumers. An anonymous authentication scheme is constructed for overload auditing and privacy preservation. Consumers’ identities are anonymous during normal operation. The operation center defines an acceptable consumption threshold at times of power shortage. Consumers must follow the instruction and curtail their power consumption to meet the threshold. If they do so, the consumers keep their anonymity, while disobedient consumers, whose power consumption exceeds the threshold, can be identified. Security analysis demonstrates that the constructed anonymous authentication scheme is secure in a random oracle model. In the voluntary incentivebased demand-response program, consumers are categorized as either obedient or disobedient consumers according to their consumption curtailment. Consumers utilize a homomorphic encryption algorithm to encrypt their usage and report the ciphertexts to the operation center periodically. At a time of grid instability, the obedient consumers reduce their consumption and prove their curtailment by using a range proof. Both the usage reports and the proofs from obedient consumers concerning their consumption are reported without leaking private information. In order to achieve the real-time requirement, a security model is proposed and a batch verification algorithm is constructed, which is proved to be secure in the defined oracle model. Apart from reward and penalty detection in demand-response programs, theft detection is also an important requirement in Smart Grids. In order to achieve theft detection, this thesis employs the dynamic k-times anonymous authentication and blind signatures to create an efficient theft detection mechanism in the prepaid card system, where consumers pay for their consumption in advance and obtain credentials. A consumer sends the credentials anonymously and obtains corresponding credentials during times of consumption. If a thief tries to send reused credentials to steal electricity, his anonymity will be revoked. Finally, this thesis proves that the proposed mechanism finds the real identities of power thieves, without sacrificing the privacy of honest consumers under the random oracle model.
The Internet of Things (IoT) is a network of computational services, devices, and people, which share information with each other. In IoT, inter-system communication is possible and human interaction is not required. IoT devices are penetrating the home and office building environments. According to current estimates, about 35 billion IoT devices will be connected by the year 20212. In the IoT business model, value comes from integrating devices into applications, e.g., home and office automation. In general, an IoT application associates different information sources with actions which can modify the environment, e.g., change the room’s temperature, inform a person, e.g., send an e-mail, or activate other services, e.g., buy milk on-line.
In this thesis, we focus on the commissioning and verification processes of IoT devices used in building automation applications. Within a building’s lifespan, new devices are added, interior spaces are refurbished, and faulty devices are replaced. All of these changes are currently made manually. Furthermore, consider that a context-aware Building Management System (BMS) is an IoT application, which measures direct-context from the building’s sensors to characterize environmental conditions, user locations, and state. Additionally, a BMS combines sensor information to derive inferred-context, such as user activity. Similar to IoT devices, inferred-context instances have to be created manually. As the number of devices and inferred-context instances increases, keeping track of all associations becomes a time-consuming and error-prone task.
The hypothesis of the thesis is that users who interact with the building create use-patterns in the data, which describe functional relations between devices and inferred-context instances, e.g., which desk-movement sensor is used to infer desk-presence and controls which overhead light; additionally, use-patterns can also provide structural relations, e.g., the relative position of spatial sensors. To test the hypothesis, this thesis presents an extension to the new IoT class rule programming paradigm, which simplifies rule creation based on classes. The proposed extension uses a semantic compiler to simplify the device and inferred-context associations. Using direct-context information and template classes, the compiler creates all possible inferredcontext instances. Buildings using context-aware BMSs will have a dynamic response to user behaviour, e.g., required illumination for computer-work is provided by adjusting blinds or increasing the dim setting of overhead ceiling lamps. We propose a rule mining framework to extract use-patterns and find the functional and structural relationships between devices. The rule mining framework uses three stages: (1) event extraction, (2) rule mining, (3) structure creation. The event extraction combines the building’s data into a time-series of device events. Then, in the rule mining stage, rules are mined from the time series, where we use the established algorithm temporal interval tree association rule learner. Additionally, we proposed a rule extraction algorithm for spatial sensor’s data. The algorithm is based on statistical analysis of user transition times between adjacent sensors. We also introduce a new rule extraction algorithm based on increasing belief. In the last stage, structure creation uses the extracted rules to produce device association groups, hierarchical representation of the building, or the relative location of spatial sensors. The proposed algorithms were tested using a year-long installation in a living-lab consisting of a four-person office, a 12-person open office, and a meeting room. For the spatial sensors, four locations within public buildings were used: a meeting room, a hallway, T-crossing, and a foyer. The recording times range from two weeks to two months depending on scenario complexity.
We found that user-generated patterns appear in building data. The rule mining framework produced structures that represent functional and spatial relationships of building’s devices and provide sufficient information to automate maintenance tasks, e.g., automatic device naming. Furthermore, we found that environmental changes are also a source of device data patterns, which provide additional associations. For example, using the framework we found the façade group for exterior light sensors. The façade group can be used to automatically find an alternative signal source to replace broken outdoor light sensors. Finally, the rule mining framework successfully retrieved the relative location of spatial sensors in all locations but the foyer.
Data management is a cornerstone for any kind of information system - including the aerospace and aviation sector. In contrast to conventional domains, software development in the avionics domain must adhere to a legally binding certification process, called qualification. The success of the process depends on compliance with international standards, such as DO-178: Software Considerations in Airborne Systems and Equipment Certification. From a software developer's perspective, challenges arise in terms of methods and tools. Techniques that have a potential impact on the deterministic and predictable execution of avionics software are prohibited.
The objective of this thesis' research is to develop a scalable method to realize data-management for multi-variant avionics software under the restrictions and constraints of the domain. Since avionics software faces very long-term life-cycles (up to 75 years), a particular focus is being placed on maintenance and evolution. Based on the insights gained in a semi-structured interview at Airbus Helicopters, industrial established approaches to implement qualified avionics software are assessed at first and compared with respect to strengths and weaknesses for data-management afterwards. As a result, a novel development approach is proposed, combining model-based techniques and product-line technology to derive the source code of highly specific data-management variants, as well as the majority of assets required for the qualification process, from a declarative system specification.
In order to demonstrate the practicability of the approach in industry, a framework is presented that is deployed and applied at Airbus Helicopters to generate qualifiable data-management components for the variants of the NH90 helicopter. The maintainability is shown by means of a domain-specific optimization, in which the model-based and generative approach is used to establish safe memory overlays at compile-time. Key findings reveal a substantially reduced memory footprint (29,1% in case of a real-world scenario), as well as an significantly facilitated implementation process, which would not be accomplishable using conventional methods for software development in the avionics domain.
German state elections are in focus of this work due to the decreasing importance of the "catch all parties" and rise of the AfD in 2013. As small parties like the AfD first reached the 5% threshold in state parliaments (e.g. in the Saxony state election 2014), state elections can be used as barometer elections for the national ones. Further, state elections fill the gap between the 4-year national election cycle and provide additional information for the national election.
The aim of this thesis is to forecast state elections based on polling data from different institutes. Despite occurring errors in polls like measurement or sampling errors - which are also discussed in this work - forecasting is made with aggregate models depending on short term polling data. Irregular polling data have to be customized to generate daily data to apply parametric regression based models. To forecast single vote shares in multi-party elections, the range of methods varies from basic methods like averaging over nonparametric regression based methods to dynamic linear models.
The Linear Ordering problem consists in finding a total ordering of the vertices of a directed graph such that the number of backward arcs, i.e., arcs whose heads precede their tails in the ordering, is minimized. A minimum set of backward arcs corresponds to an optimal solution to the equivalent Feedback Arc Set problem and forms a minimum Cycle Cover.
Linear Ordering and Feedback Arc Set are classic NP-hard optimization problems and have a wide range of applications. Whereas both problems have been studied intensively on dense graphs and tournaments, not much is known about their structure and properties on sparser graphs. There are also only few approximative algorithms that give performance guarantees especially for graphs with bounded vertex degree.
This thesis fills this gap in multiple respects: We establish necessary conditions for a linear ordering (and thereby also for a feedback arc set) to be optimal, which provide new and fine-grained insights into the combinatorial structure of the problem. From these, we derive a framework for polynomial-time algorithms that construct linear orderings which adhere to one or more of these conditions. The analysis of the linear orderings produced by these algorithms is especially tailored to graphs with bounded vertex degrees of three and four and improves on previously known upper bounds. Furthermore, the set of necessary conditions is used to implement exact and fast algorithms for the Linear Ordering problem on sparse graphs. In an experimental evaluation, we finally show that the property-enforcing algorithms produce linear orderings that are very close to the optimum and that the exact representative delivers solutions in a timely manner also in practice.
As an additional benefit, our results can be applied to the Acyclic Subgraph problem, which is the complementary problem to Feedback Arc Set, and provide insights into the dual problem of Feedback Arc Set, the Arc-Disjoint Cycles problem.
This paper aims at the documentation of the results of a study dealing with the relationship between in-group and out-group attitudes. The research enquires into the question whether nationalistic, patriotic, and anti-immigration attitudes are only correlated with each other or whether there is a causal relationship. The presentation of the Mplus output together with the correlation and covariance matrices will allow the readers to control the results and, if they want to do it, to test alternative models.