OpenRaiser/Intern-Atlas huggingface dataset:
Universal Coating for Programmable Matter
Venue: arXiv cs.ET 2016
Year: 2016

The idea behind universal coating is to have a thin layer of a specific substance covering an object of any shape so that one can measure a certain condition (like temperature or cracks) at any spot on the surface of the object without requiring direct access to that spot. We study the universal coating problem in the context of self-organizing programmable matter consisting of simple computational elements, called particles, that can establish and release bonds and can actively move in a self-organized way. Based on that matter, we present a worst-case work-optimal universal coating algorithm that uniformly coats any object of arbitrary shape and size that allows a uniform coating. Our particles are anonymous, do not have any global information, have constant-size memory, and utilize only local interactions.
Low-rank Matrix Factorization under General Mixture Noise Distributions
Venue: arXiv cs.CV 2016
Year: 2016

Many computer vision problems can be posed as learning a low-dimensional subspace from high dimensional data. The low rank matrix factorization (LRMF) represents a commonly utilized subspace learning strategy. Most of the current LRMF techniques are constructed on the optimization problems using L1-norm and L2-norm losses, which mainly deal with Laplacian and Gaussian noises, respectively. To make LRMF capable of adapting more complex noise, this paper proposes a new LRMF model by assuming noise as Mixture of Exponential Power (MoEP) distributions and proposes a penalized MoEP (PMoEP) model by combining the penalized likelihood method with MoEP distributions. Such setting facilitates the learned LRMF model capable of automatically fitting the real noise through MoEP distributions. Each component in this mixture is adapted from a series of preliminary super- or sub-Gaussian candidates. Moreover, by facilitating the local continuity of noise components, we embed Markov random field into the PMoEP model and further propose the advanced PMoEP-MRF model. An Expectation Maximization (EM) algorithm and a variational EM (VEM) algorithm are also designed to infer the parameters involved in the proposed PMoEP and the PMoEP-MRF model, respectively. The superseniority of our methods is demonstrated by extensive experiments on synthetic data, face modeling, hyperspectral image restoration and background subtraction.
A Polynomial-time Algorithm to Compute Generalized Hermite Normal Form of Matrices over Z[x]
Venue: arXiv cs.SC 2016
Year: 2016

In this paper, a polynomial-time algorithm is given to compute the generalized Hermite normal form for a matrix F over Z[x], or equivalently, the reduced Groebner basis of the Z[x]-module generated by the column vectors of F. The algorithm is also shown to be practically more efficient than existing algorithms. The algorithm is based on three key ingredients. First, an F4 style algorithm to compute the Groebner basis is adopted, where a novel prolongation is designed such that the coefficient matrices under consideration have polynomial sizes. Second, fast algorithms to compute Hermite normal forms of matrices over Z are used. Third, the complexity of the algorithm are guaranteed by a nice estimation for the degree and height bounds of the polynomials in the generalized Hermite normal form.
Attention Sensitive Web Browsing
Venue: arXiv cs.HC 2016
Year: 2016

With a number of cheap commercial dry EEG kits available today, it is possible to look at user attention driven scenarios for interaction with the web browser. Using EEG to determine the user's attention level is preferable to using methods such as gaze tracking or time spent on the webpage. In this paper we use the attention level in three different ways. First, as a control mechanism, to control user interface elements such as menus or buttons. Second, to make the web browser responsive to the current attention level. Third, as a means for the web developer to control the user experience based on the level of attention paid by the user, thus creating attention sensitive websites. We present implementation details for each of these, using the NeuroSky MindWave sensor. We also explore issues in the system, and possibility of an EEG based web standard.
Some Experimental Issues in Financial Fraud Detection: An Investigation
Venue: arXiv cs.CR 2016
Year: 2016

Financial fraud detection is an important problem with a number of design aspects to consider. Issues such as algorithm selection and performance analysis will affect the perceived ability of proposed solutions, so for auditors and re-searchers to be able to sufficiently detect financial fraud it is necessary that these issues be thoroughly explored. In this paper we will revisit the key performance metrics used for financial fraud detection with a focus on credit card fraud, critiquing the prevailing ideas and offering our own understandings. There are many different performance metrics that have been employed in prior financial fraud detection research. We will analyse several of the popular metrics and compare their effectiveness at measuring the ability of detection mechanisms. We further investigated the performance of a range of computational intelligence techniques when applied to this problem domain, and explored the efficacy of several binary classification methods.
(Leftmost-Outermost) Beta Reduction is Invariant, Indeed
Venue: arXiv cs.PL 2016
Year: 2016

Slot and van Emde Boas' weak invariance thesis states that reasonable machines can simulate each other within a polynomially overhead in time. Is lambda-calculus a reasonable machine? Is there a way to measure the computational complexity of a lambda-term? This paper presents the first complete positive answer to this long-standing problem. Moreover, our answer is completely machine-independent and based over a standard notion in the theory of lambda-calculus: the length of a leftmost-outermost derivation to normal form is an invariant cost model. Such a theorem cannot be proved by directly relating lambda-calculus with Turing machines or random access machines, because of the size explosion problem: there are terms that in a linear number of steps produce an exponentially long output. The first step towards the solution is to shift to a notion of evaluation for which the length and the size of the output are linearly related. This is done by adopting the linear substitution calculus (LSC), a calculus of explicit substitutions modeled after linear logic proof nets and admitting a decomposition of leftmost-outermost derivations with the desired property. Thus, the LSC is invariant with respect to, say, random access machines. The second step is to show that LSC is invariant with respect to the lambda-calculus. The size explosion problem seems to imply that this is not possible: having the same notions of normal form, evaluation in the LSC is exponentially longer than in the lambda-calculus. We solve such an impasse by introducing a new form of shared normal form and shared reduction, deemed useful. Useful evaluation avoids those steps that only unshare the output without contributing to beta-redexes, i.e. the steps that cause the blow-up in size. The main technical contribution of the paper is indeed the definition of useful reductions and the thorough analysis of their properties.
Loop Free Multipath Routing Algorithm
Venue: arXiv cs.NI 2016
Year: 2016

Single path routing that is currently used in the internet routers,is easy to implement as it simplifies the routing tables and packet flow paths. However it is not optimal and has shortcomings in utilizing the network resources optimally, load balancing & fast recovery in case of faults (fault tolerance). The given algorithm resolves all these problems by using all possible multiple paths for transfer of information, while retaining loop-free property. We have proposed a new dynamic loop-free multipath routing algorithm which improves network throughput and network resource utilization, reduces average transmission delay, and is not affected by faults in the links and router nodes. The main idea of this algorithm is to maintain multiple possible next hops for a destination along with weights. At every node, the traffic to a destination is split among multiple next hops in proportion to the estimated weights. The number of multiple next hops also changes depending on the traffic conditions, but it is never less than one.
Security and Privacy in Future Internet Architectures - Benefits and Challenges of Content Centric Networks
Venue: arXiv cs.CR 2016
Year: 2016

As the shortcomings of our current Internet become more and more obvious, researchers have started creating alternative approaches for the Internet of the future. Their design goals are mainly content-orientation, security, support for mobility and cloud computing. The probably most popular architecture is called Content Centric Networking. Every communication is treated as a distribution of content and caches are used within the network to improve the effectiveness. While the performance gain of Content Centric Networks is undoubted, there are questions about security and especially privacy since it is not one of its main design principle. In this work, we compare the Content Centric Networking approach with the current Internet with respect to security and privacy. We analyze improvements that have been made and new problems that have yet to be resolved. The Internet of the future could be content-oriented, so it is essential to identify potential security and privacy issues that are inherent to the architecture early on.
Artificial Noise Aided Secrecy Information and Power Transfer in OFDMA Systems
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we study simultaneous wireless information and power transfer (SWIPT) in orthogonal frequency division multiple access (OFDMA) systems with the coexistence of information receivers (IRs) and energy receivers (ERs). The IRs are served with best-effort secrecy data and the ERs harvest energy with minimum required harvested power. To enhance the physical layer security for IRs and yet satisfy energy harvesting requirements for ERs, we propose a new frequency domain artificial noise (AN) aided transmission strategy. With the new strategy, we study the optimal resource allocation for the weighted sum secrecy rate maximization for IRs by power and subcarrier allocation at the transmitter. The studied problem is shown to be a mixed integer programming problem and thus non-convex, while we propose an efficient algorithm for solving it based on the Lagrange duality method. To further reduce the computational complexity, we also propose a suboptimal algorithm of lower complexity. The simulation results illustrate the effectiveness of proposed algorithms as compared against other heuristic schemes.
Design of a Low-Power 1.65 Gbps Data Channel for HDMI Transmitter
Venue: arXiv cs.AR 2016
Year: 2016

This paper presents a design of low power data channel for application in High Definition Multimedia Interface (HDMI) Transmitter circuit. The input is 10 bit parallel data and output is serial data at 1.65 Gbps. This circuit uses only a single frequency of serial clock input. All other timing signals are derived within the circuit from the serial clock. This design has dedicated lines to disable and enable all its channels within two pixel-clock periods only. A pair of disable and enable functions performed immediately after power-on of the circuit serves as the reset function. The presented design is immune to data-dependent switching spikes in supply current and pushes them in the range of serial frequency and its multiples. Thus filtering requirements are relaxed. The output stage uses a bias voltage of 2.8 volts for a receiver pull-up voltage of 3.3 volts. The reported data channel is designed using UMC 180 nm CMOS Technology. The design is modifiable for other inter-board serial interfaces like USB and LAN with different number of bits at the parallel input.
Rules and derivations in an elementary logic course
Venue: arXiv cs.LO 2016
Year: 2016

When teaching an elementary logic course to students who have a general scientific background but have never been exposed to logic, we have to face the problem that the notions of deduction rule and of derivation are completely new to them, and are related to nothing they already know, unlike, for instance, the notion of model, that can be seen as a generalization of the notion of algebraic structure. In this note, we defend the idea that one strategy to introduce these notions is to start with the notion of inductive definition [1]. Then, the notion of derivation comes naturally. We also defend the idea that derivations are pervasive in logic and that defining precisely this notion at an early stage is a good investment to later define other notions in proof theory, computability theory, automata theory, ... Finally, we defend the idea that to define the notion of derivation precisely, we need to distinguish two notions of derivation: labeled with elements and labeled with rule names. This approach has been taken in [2].
Robust Successive Compute-and-Forward over Multi-User Multi-Relay Networks
Venue: arXiv cs.IT 2016
Year: 2016

This paper develops efficient Compute-and-forward (CMF) schemes in multi-user multi-relay networks. To solve the rank failure problem in CMF setups and to achieve full diversity of the network, we introduce two novel CMF methods, namely, extended CMF and successive CMF. The former, having low complexity, is based on recovering multiple equations at relays. The latter utilizes successive interference cancellation (SIC) to enhance the system performance compared to the state-of-the-art schemes. Both methods can be utilized in a network with different number of users, relays, and relay antennas, with negligible feedback channels or signaling overhead. We derive new concise formulations and explicit framework for the successive CMF method as well as an approach to reduce its computational complexity. Our theoretical analysis and computer simulations demonstrate the superior performance of our proposed CMF methods over the conventional schemes. Furthermore, based on our simulation results, the successive CMF method yields additional signal-to-noise ratio gains and shows considerable robustness against channel estimation error, compared to the extended CMF method.
Family of 2-simplex cognitive tools and their application for decision-making and its justifications
Venue: arXiv cs.HC 2016
Year: 2016

Urgency of application and development of cognitive graphic tools for usage in intelligent systems of data analysis, decision making and its justifications is given. Cognitive graphic tool "2-simplex prism" and examples of its usage are presented. Specificity of program realization of cognitive graphics tools invariant to problem areas is described. Most significant results are given and discussed. Future investigations are connected with usage of new approach to rendering, cross-platform realization, cognitive features improving and expanding of n-simplex family.
Partitioning a triangle-free planar graph into a forest and a forest of bounded degree
Venue: arXiv cs.DM 2016
Year: 2016

An $({\cal F},{\cal F}_d)$-partition of a graph is a vertex-partition into two sets $F$ and $F_d$ such that the graph induced by $F$ is a forest and the one induced by $F_d$ is a forest with maximum degree at most $d$. We prove that every triangle-free planar graph admits an $({\cal F},{\cal F}_5)$-partition. Moreover we show that if for some integer $d$ there exists a triangle-free planar graph that does not admit an $({\cal F},{\cal F}_d)$-partition, then it is an NP-complete problem to decide whether a triangle-free planar graph admits such a partition.
State Space representation of non-stationary Gaussian Processes
Venue: arXiv cs.LG 2016
Year: 2016

The state space (SS) representation of Gaussian processes (GP) has recently gained a lot of interest. The main reason is that it allows to compute GPs based inferences in O(n), where $n$ is the number of observations. This implementation makes GPs suitable for Big Data. For this reason, it is important to provide a SS representation of the most important kernels used in machine learning. The aim of this paper is to show how to exploit the transient behaviour of SS models to map non-stationary kernels to SS models.
Grafalgo - A Library of Graph Algorithms and Supporting Data Structures (revised)
Venue: arXiv cs.DS 2016
Year: 2016

This report provides an (updated) overview of {\sl Grafalgo}, an open-source library of graph algorithms and the data structures used to implement them. The programs in this library were originally written to support a graduate class in advanced data structures and algorithms at Washington University. Because the code's primary purpose was pedagogical, it was written to be as straightforward as possible, while still being highly efficient. Grafalgo is implemented in C++ and incorporates some features of C++11. The library is available on an open-source basis and may be downloaded from https://code.google.com/p/grafalgo/. Source code documentation is at www.arl.wustl.edu/\textasciitilde jst/doc/grafalgo. While not designed as production code, the library is suitable for use in larger systems, so long as its limitations are understood. The readability of the code also makes it relatively straightforward to extend it for other purposes.
Toward Organic Computing Approach for Cybernetic Responsive Environment
Venue: arXiv cs.AI 2016
Year: 2016

The developpment of the Internet of Things (IoT) concept revives Responsive Environments (RE) technologies. Nowadays, the idea of a permanent connection between physical and digital world is technologically possible. The capillar Internet relates to the Internet extension into daily appliances such as they become actors of Internet like any hu-man. The parallel development of Machine-to-Machine communications and Arti cial Intelligence (AI) technics start a new area of cybernetic. This paper presents an approach for Cybernetic Organism (Cyborg) for RE based on Organic Computing (OC). In such approach, each appli-ance is a part of an autonomic system in order to control a physical environment. The underlying idea is that such systems must have self-x properties in order to adapt their behavior to external disturbances with a high-degree of autonomy.
Fuzzy Object-Oriented Dynamic Networks. I
Venue: arXiv cs.AI 2016
Year: 2016

The concepts of fuzzy objects and their classes are described that make it possible to structurally represent knowledge about fuzzy and partially-defined objects and their classes. Operations over such objects and classes are also proposed that make it possible to obtain sets and new classes of fuzzy objects and also to model variations in object structures under the influence of external factors.
Live-action Virtual Reality Games
Venue: arXiv cs.HC 2016
Year: 2016

This paper proposes the concept of "live-action virtual reality games" as a new genre of digital games based on an innovative combination of live-action, mixed-reality, context-awareness, and interaction paradigms that comprise tangible objects, context-aware input devices, and embedded/embodied interactions. Live-action virtual reality games are "live-action games" because a player physically acts out (using his/her real body and senses) his/her "avatar" (his/her virtual representation) in the game stage, which is the mixed-reality environment where the game happens. The game stage is a kind of "augmented virtuality"; a mixed-reality where the virtual world is augmented with real-world information. In live-action virtual reality games, players wear HMD devices and see a virtual world that is constructed using the physical world architecture as the basic geometry and context information. Physical objects that reside in the physical world are also mapped to virtual elements. Live-action virtual reality games keeps the virtual and real-worlds superimposed, requiring players to physically move in the environment and to use different interaction paradigms (such as tangible and embodied interaction) to complete game activities. This setup enables the players to touch physical architectural elements (such as walls) and other objects, "feeling" the game stage. Players have free movement and may interact with physical objects placed in the game stage, implicitly and explicitly. Live-action virtual reality games differ from similar game concepts because they sense and use contextual information to create unpredictable game experiences, giving rise to emergent gameplay.
An Automaton Learning Approach to Solving Safety Games over Infinite Graphs
Venue: arXiv cs.FL 2016
Year: 2016

We propose a method to construct finite-state reactive controllers for systems whose interactions with their adversarial environment are modeled by infinite-duration two-player games over (possibly) infinite graphs. The proposed method targets safety games with infinitely many states or with such a large number of states that it would be impractical---if not impossible---for conventional synthesis techniques that work on the entire state space. We resort to constructing finite-state controllers for such systems through an automata learning approach, utilizing a symbolic representation of the underlying game that is based on finite automata. Throughout the learning process, the learner maintains an approximation of the winning region (represented as a finite automaton) and refines it using different types of counterexamples provided by the teacher until a satisfactory controller can be derived (if one exists). We present a symbolic representation of safety games (inspired by regular model checking), propose implementations of the learner and teacher, and evaluate their performance on examples motivated by robotic motion planning in dynamic environments.
Profiling-Assisted Decoupled Access-Execute
Venue: arXiv cs.AR 2016
Year: 2016

As energy efficiency became a critical factor in the embedded systems domain, dynamic voltage and frequency scaling (DVFS) techniques have emerged as means to control the system's power and energy efficiency. Additionally, due to the compact design, thermal issues become prominent. State of the art work promotes software decoupled access-execution (DAE) that statically generates code amenable to DVFS techniques. The compiler builds memory-bound access phases, designed to prefetch data in the cache at low frequency, and compute-bound phases, that consume the data and perform computations at high frequency. This work investigates techniques to find the optimal balance between lightweight and efficient access phases. A profiling step guides the selection of loads to be prefetched in the access phase. For applications whose behavior vary significantly with respect to the input data, the profiling can be performed online, accompanied by just-in-time compilation. We evaluated the benefits in energy efficiency and performance for both static and dynamic code generation and showed that precise prefetching of critical loads can result in 20% energy improvements, on average. DAE is particularly beneficial for embedded systems as by alternating access phases (executed at low frequency) and execute phases (at high frequency) DAE proactively reduces the temperature and therefore prevents thermal emergencies.