OpenRaiser/Intern-Atlas huggingface dataset:
OpenHEC: A Framework for Application Programmers to Design FPGA-based Systems
Venue: arXiv cs.OH 2014
Year: 2014

Today, there is a trend to incorporate more intelligence (e.g., vision capabilities) into a wide range of devices, which makes high performance a necessity for computing systems. Furthermore, for embedded systems, low power consumption should be generally considered together with high computing performance. FPGAs, as programmable logic devices able to support different types of fine-grained parallelisms, their power and performance advantages were recognized widely. However, designing applications on FPGA-based systems is traditionally far from a task can be carried out by software programmers. Generally, hardware engineers and even system-level software engineers have more hardware/architectural knowledge but fewer algorithm and application knowledge. Thus, it is critical for computing systems to allow application-level programmers to realize their idea conveniently, which is popular in computing systems based on the general processor. In this paper, the OpenHEC (Open Framework for High-Efficiency Computing) framework is proposed to provide a design framework for application-level software programmers to use FPGA-based platforms. It frees users from hardware and architectural details to let them focus more on algorithms/applications. This framework was integrated with the commercial Xilinx ISE/Vivado to make it to be used immediately. After implementing a widely-used feature detection algorithm on OpenHEC from the perspective of software programmers, it shows this framework is applicable for application programmers with little hardware knowledge.
Social Learning in a Human Society: An Experimental Study
Venue: arXiv cs.SI 2014
Year: 2014

This paper presents an experimental study to investigate the learning and decision making behavior of individuals in a human society. Social learning is used as the mathematical basis for modelling interaction of individuals that aim to perform a perceptual task interactively. A psychology experiment was conducted on a group of undergraduate students at the University of British Columbia to examine whether the decision (action) of one individual affects the decision of the subsequent individuals. The major experimental observation that stands out here is that the participants of the experiment (agents) were affected by decisions of their partners in a relatively large fraction (60%) of trials. We fit a social learning model that mimics the interactions between participants of the psychology experiment. Misinformation propagation (also known as data incest) within the society under study is further investigated in this paper.
On the Complexity of Role Colouring Planar Graphs, Trees and Cographs
Venue: arXiv cs.DS 2014
Year: 2014

We prove several results about the complexity of the role colouring problem. A role colouring of a graph $G$ is an assignment of colours to the vertices of $G$ such that two vertices of the same colour have identical sets of colours in their neighbourhoods. We show that the problem of finding a role colouring with $1< k <n$ colours is NP-hard for planar graphs. We show that restricting the problem to trees yields a polynomially solvable case, as long as $k$ is either constant or has a constant difference with $n$, the number of vertices in the tree. Finally, we prove that cographs are always $k$-role-colourable for $1<k\leq n$ and construct such a colouring in polynomial time.
A Circulant Approach to Skew-Constacyclic Codes
Venue: arXiv cs.IT 2014
Year: 2014

We introduce circulant matrices that capture the structure of a skew-polynomial ring F[x;θ] modulo the left ideal generated by a polynomial of the type x^n-a. This allows us to develop an approach to skew-constacyclic codes based on such circulants. Properties of these circulants are derived, and in particular it is shown that the transpose of a certain circulant is a circulant again. This recovers the well-known result that the dual of a skew-constacyclic code is a constacyclic code again. Special attention is paid to the case where x^n-a is two-sided.
A Sytematic Piggybacking Design for Minimum Storage Regenerating Codes
Venue: arXiv cs.IT 2014
Year: 2014

Piggybacking is an efficient method to decrease the repair bandwidth of Maximum Distance Separable (MDS) codes or Minimum Storage Regenerating (MSR) codes. In this paper, for minimizing the repair bandwidth of parity nodes of the known MSR codes with high rate, which is usually the whole size of the original data, i.e., the maximal, a new systematic piggybacking design is proposed through an in-depth analysis of the design of piggybacking. As a result, new MSR codes are obtained with almost optimal repair bandwidth of parity nodes while retaining the optimal repair bandwidth of systematic nodes. Furthermore, MSR codes with balanced download during node repair process are presented based on the new piggybacking design.
Energy-Efficient Power Allocation for Secure Communications in Large-Scale MIMO Relaying Systems
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we address the problem of energy-efficient power allocation for secure communications in an amplify-and-forward (AF) large-scale multiple-input multiple-output (LS-MIMO) relaying system in presence of a passive eavesdropper. The benefits of an AF LS-MIMO relay are exploited to significantly improve the secrecy performance, especially the secrecy energy efficiency (bit per Joule). We first analyze the impact of transmit power at the relay on the secrecy outage capacity, and prove that the secrecy outage capacity is a concave function of transmit power under very practical assumptions, i.e. no eavesdropper channel state information (CSI) and imperfect legitimate CSI. Then, we propose an energy-efficient power allocation scheme to maximize the secrecy energy efficiency. Finally, simulation results validate the advantage of the proposed energy-efficient scheme compared to the capacity maximization scheme.
Learn Convolutional Neural Network for Face Anti-Spoofing
Venue: arXiv cs.CV 2014
Year: 2014

Though having achieved some progresses, the hand-crafted texture features, e.g., LBP [23], LBP-TOP [11] are still unable to capture the most discriminative cues between genuine and fake faces. In this paper, instead of designing feature by ourselves, we rely on the deep convolutional neural network (CNN) to learn features of high discriminative ability in a supervised manner. Combined with some data pre-processing, the face anti-spoofing performance improves drastically. In the experiments, over 70% relative decrease of Half Total Error Rate (HTER) is achieved on two challenging datasets, CASIA [36] and REPLAY-ATTACK [7] compared with the state-of-the-art. Meanwhile, the experimental results from inter-tests between two datasets indicates CNN can obtain features with better generalization ability. Moreover, the nets trained using combined data from two datasets have less biases between two datasets.
Performance and analysis of Quadratic Residue Codes of lengths less than 100
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, the performance of quadratic residue (QR) codes of lengths within 100 is given and analyzed when the hard decoding, soft decoding, and linear programming decoding algorithms are utilized. We develop a simple method to estimate the soft decoding performance, which avoids extensive simulations. Also, a simulation-based algorithm is proposed to obtain the maximum likelihood decoding performance of QR codes of lengths within 100. Moreover, four important theorems are proposed to predict the performance of the hard decoding and the maximum-likelihood decoding in which they can explore some internal properties of QR codes. It is shown that such four theorems can be applied to the QR codes with lengths less than 100 for predicting the decoding performance. In contrast, they can be straightforwardly generalized to longer QR codes. The result is never seen in the literature, to our knowledge. Simulation results show that the estimated hard decoding performance is very accurate in the whole signal-to-noise ratio (SNR) regimes, whereas the derived upper bounds of the maximum likelihood decoding are only tight for moderate to high SNR regions. For each of the considered QR codes, the soft decoding is approximately 1.5 dB better than the hard decoding. By using powerful redundant parity-check cuts, the linear programming-based decoding algorithm, i.e., the ACG-ALP decoding algorithm performs very well for any QR code. Sometimes, it is even superior to the Chase-based soft decoding algorithm significantly, and hence is only a few tenths of dB away from the maximum likelihood decoding.
Report on the Aachen OCL Meeting
Venue: arXiv cs.SE 2014
Year: 2014

As a continuation of the OCL workshop during the MODELS 2013 conference in October 2013, a number of OCL experts decided to meet in November 2013 in Aachen for two days to discuss possible short term improvements of OCL for an upcoming OMG meeting and to envision possible future long-term developments of the language. This paper is a sort of \minutes of the meeting" and intended to quickly inform the OCL community about the discussion topics.
Engineering Delta Modeling Languages
Venue: arXiv cs.SE 2014
Year: 2014

Delta modeling is a modular, yet flexible approach to capture spatial and temporal variability by explicitly representing the differences between system variants or versions. The conceptual idea of delta modeling is language-independent. But, in order to apply delta modeling for a concrete language, so far, a delta language had to be manually developed on top of the base language leading to a large variety of heterogeneous language concepts. In this paper, we present a process that allows deriving a delta language from the grammar of a given base language. Our approach relies on an automatically generated language extension that can be manually adapted to meet domain-specific needs. We illustrate our approach using delta modeling on a textual variant of statecharts.
When is a container a comonad?
Venue: arXiv cs.PL 2014
Year: 2014

Abbott, Altenkirch, Ghani and others have taught us that many parameterized datatypes (set functors) can be usefully analyzed via container representations in terms of a set of shapes and a set of positions in each shape. This paper builds on the observation that datatypes often carry additional structure that containers alone do not account for. We introduce directed containers to capture the common situation where every position in a data-structure determines another data-structure, informally, the sub-data-structure rooted by that position. Some natural examples are non-empty lists and node-labelled trees, and data-structures with a designated position (zippers). While containers denote set functors via a fully-faithful functor, directed containers interpret fully-faithfully into comonads. But more is true: every comonad whose underlying functor is a container is represented by a directed container. In fact, directed containers are the same as containers that are comonads. We also describe some constructions of directed containers. We have formalized our development in the dependently typed programming language Agda.
Algorithms that satisfy a stopping criterion, probably
Venue: arXiv cs.NA 2014
Year: 2014

Iterative numerical algorithms are typically equipped with a stopping criterion, where the iteration process is terminated when some error or misfit measure is deemed to be below a given tolerance. This is a useful setting for comparing algorithm performance, among other purposes. However, in practical applications a precise value for such a tolerance is rarely known; rather, only some possibly vague idea of the desired quality of the numerical approximation is at hand. We discuss four case studies from different areas of numerical computation, where uncertainty in the error tolerance value and in the stopping criterion is revealed in different ways. This leads us to think of approaches to relax the notion of exactly satisfying a tolerance value. We then concentrate on a {\em probabilistic} relaxation of the given tolerance. This allows, for instance, derivation of proven bounds on the sample size of certain Monte Carlo methods. We describe an algorithm that becomes more efficient in a controlled way as the uncertainty in the tolerance increases, and demonstrate this in the context of some particular applications of inverse problems.
Infinite Networks, Halting and Local Algorithms
Venue: arXiv cs.DC 2014
Year: 2014

The immediate past has witnessed an increased amount of interest in local algorithms, i.e., constant time distributed algorithms. In a recent survey of the topic (Suomela, ACM Computing Surveys, 2013), it is argued that local algorithms provide a natural framework that could be used in order to theoretically control infinite networks in finite time. We study a comprehensive collection of distributed computing models and prove that if infinite networks are included in the class of structures investigated, then every universally halting distributed algorithm is in fact a local algorithm. To contrast this result, we show that if only finite networks are allowed, then even very weak distributed computing models can define nonlocal algorithms that halt everywhere. The investigations in this article continue the studies in the intersection of logic and distributed computing initiated in (Hella et al., PODC 2012) and (Kuusisto, CSL 2013).
Hourglass Automata
Venue: arXiv cs.FL 2014
Year: 2014

In this paper, we define the class of hourglass automata, which are timed automata with bounded clocks that can be made to progress backwards as well as forwards at a constant rate. We then introduce a new clock update for timed automata that allows hourglass automata to be expressed. This allows us to show that language emptiness remains decidable with this update when the number of clocks is two or less. This is done by showing that we can construct a finite untimed graph using clock regions from any timed automaton that use this new update.
Improved Undecidability Results for Reachability Games on Recursive Timed Automata
Venue: arXiv cs.FL 2014
Year: 2014

We study reachability games on recursive timed automata (RTA) that generalize Alur-Dill timed automata with recursive procedure invocation mechanism similar to recursive state machines. It is known that deciding the winner in reachability games on RTA is undecidable for automata with two or more clocks, while the problem is decidable for automata with only one clock. Ouaknine and Worrell recently proposed a time-bounded theory of real-time verification by claiming that restriction to bounded-time recovers decidability for several key decision problem related to real-time verification. We revisited games on recursive timed automata with time-bounded restriction in the hope of recovering decidability. However, we found that the problem still remains undecidable for recursive timed automata with three or more clocks. Using similar proof techniques we characterize a decidability frontier for a generalization of RTA to recursive stopwatch automata.
Dynamic Role Authorization in Multiparty Conversations
Venue: arXiv cs.LO 2014
Year: 2014

Protocol specifications often identify the roles involved in communications. In multiparty protocols that involve task delegation it is often useful to consider settings in which different sites may act on behalf of a single role. It is then crucial to control the roles that the different parties are authorized to represent, including the case in which role authorizations are determined only at runtime. Building on previous work on conversation types with flexible role assignment, here we report initial results on a typed framework for the analysis of multiparty communications with dynamic role authorization and delegation. In the underlying process model, communication prefixes are annotated with role authorizations and authorizations can be passed around. We extend the conversation type system so as to statically distinguish processes that never incur in authorization errors. The proposed static discipline guarantees that processes are always authorized to communicate on behalf of an intended role, also covering the case in which authorizations are dynamically passed around in messages.
Compliance for reversible client/server interactions
Venue: arXiv cs.LO 2014
Year: 2014

In the setting of session behaviours, we study an extension of the concept of compliance when a disciplined form of backtracking is present. After adding checkpoints to the syntax of session behaviours, we formalise the operational semantics via a LTS, and define a natural notion of checkpoint compliance. We then obtain a co-inductive characterisation of such compliance relation, and an axiomatic presentation that is proved to be sound and complete. As a byproduct we get a decision procedure for the new compliance, being the axiomatic system algorithmic.
Simultaneous Embeddability of Two Partitions
Venue: arXiv cs.CG 2014
Year: 2014

We study the simultaneous embeddability of a pair of partitions of the same underlying set into disjoint blocks. Each element of the set is mapped to a point in the plane and each block of either of the two partitions is mapped to a region that contains exactly those points that belong to the elements in the block and that is bounded by a simple closed curve. We establish three main classes of simultaneous embeddability (weak, strong, and full embeddability) that differ by increasingly strict well-formedness conditions on how different block regions are allowed to intersect. We show that these simultaneous embeddability classes are closely related to different planarity concepts of hypergraphs. For each embeddability class we give a full characterization. We show that (i) every pair of partitions has a weak simultaneous embedding, (ii) it is NP-complete to decide the existence of a strong simultaneous embedding, and (iii) the existence of a full simultaneous embedding can be tested in linear time.
Scrum of scrums solution for large size teams using scrum methodology
Venue: arXiv cs.SE 2014
Year: 2014

Scrum is a structured framework to support complex product development. However, Scrum methodology faces a challenge of managing large teams. To address this challenge, in this paper we propose a solution called Scrum of Scrums. In Scrum of Scrums, we divide the Scrum team into teams of the right size, and then organize them hierarchically into a Scrum of Scrums. The main goals of the proposed solution are to optimize communication between teams in Scrum of Scrums; to make the system work after integration of all parts; to reduce the dependencies between the parts of system; and to prevent the duplication of parts in the system.
Consensus and Consistency Level Optimization of Fuzzy Preference Relation: A Soft Computing Approach
Venue: arXiv cs.AI 2014
Year: 2014

In group decision making (GDM) problems fuzzy preference relations (FPR) are widely used for representing decision makers' opinions on the set of alternatives. In order to avoid misleading solutions, the study of consistency and consensus has become a very important aspect. This article presents a simulated annealing (SA) based soft computing approach to optimize the consistency/consensus level (CCL) of a complete fuzzy preference relation in order to solve a GDM problem. Consistency level indicates as expert's preference quality and consensus level measures the degree of agreement among experts' opinions. This study also suggests the set of experts for the necessary modifications in their prescribed preference structures without intervention of any moderator.
Compression, Restoration, Re-sampling, Compressive Sensing: Fast Transforms in Digital Imaging
Venue: arXiv cs.CV 2014
Year: 2014

Transform image processing methods are methods that work in domains of image transforms, such as Discrete Fourier, Discrete Cosine, Wavelet and alike. They are the basic tool in image compression, in image restoration, in image re-sampling and geometrical transformations and can be traced back to early 1970-ths. The paper presents a review of these methods with emphasis on their comparison and relationships, from the very first steps of transform image compression methods to adaptive and local adaptive transform domain filters for image restoration, to methods of precise image re-sampling and image reconstruction from sparse samples and up to "compressive sensing" approach that has gained popularity in last few years. The review has a tutorial character and purpose.
Learning What's going on: reconstructing preferences and priorities from opaque transactions
Venue: arXiv cs.GT 2014
Year: 2014

We consider a setting where $n$ buyers, with combinatorial preferences over $m$ items, and a seller, running a priority-based allocation mechanism, repeatedly interact. Our goal, from observing limited information about the results of these interactions, is to reconstruct both the preferences of the buyers and the mechanism of the seller. More specifically, we consider an online setting where at each stage, a subset of the buyers arrive and are allocated items, according to some unknown priority that the seller has among the buyers. Our learning algorithm observes only which buyers arrive and the allocation produced (or some function of the allocation, such as just which buyers received positive utility and which did not), and its goal is to predict the outcome for future subsets of buyers. For this task, the learning algorithm needs to reconstruct both the priority among the buyers and the preferences of each buyer. We derive mistake bound algorithms for additive, unit-demand and single minded buyers. We also consider the case where buyers' utilities for a fixed bundle can change between stages due to different (observed) prices. Our algorithms are efficient both in computation time and in the maximum number of mistakes (both polynomial in the number of buyers and items).
Uncertainty Aware Query Execution Time Prediction
Venue: arXiv cs.DB 2014
Year: 2014

Predicting query execution time is a fundamental issue underlying many database management tasks. Existing predictors rely on information such as cardinality estimates and system performance constants that are difficult to know exactly. As a result, accurate prediction still remains elusive for many queries. However, existing predictors provide a single, point estimate of the true execution time, but fail to characterize the uncertainty in the prediction. In this paper, we take a first step towards providing uncertainty information along with query execution time predictions. We use the query optimizer's cost model to represent the query execution time as a function of the selectivities of operators in the query plan as well as the constants that describe the cost of CPU and I/O operations in the system. By treating these quantities as random variables rather than constants, we show that with low overhead we can infer the distribution of likely prediction errors. We further show that the estimated prediction errors by our proposed techniques are strongly correlated with the actual prediction errors.