OpenRaiser/Intern-Atlas huggingface dataset:
Relay Selection for Wireless Communications Against Eavesdropping: A Security-Reliability Tradeoff Perspective
Venue: arXiv cs.IT 2015
Year: 2015

This article examines the secrecy coding aided wireless communications from a source to a destination in the presence of an eavesdropper from a security-reliability tradeoff (SRT) perspective. Explicitly, the security is quantified in terms of the intercept probability experienced at the eavesdropper, while the outage probability encountered at the destination is used to measure the transmission reliability. We characterize the SRT of conventional direct transmission from the source to the destination and show that if the outage probability is increased, the intercept probability decreases, and vice versa. We first demonstrate that the employment of relay nodes for assisting the source-destination transmissions is capable of defending against eavesdropping, followed by quantifying the benefits of single-relay selection (SRS) as well as of multi-relay selection (MRS) schemes. More specifically, in the SRS scheme, only the single "best" relay is selected for forwarding the source signal to the destination, whereas the MRS scheme allows multiple relays to participate in this process. It is illustrated that both the SRS and MRS schemes achieve a better SRT than the conventional direct transmission, especially upon increasing the number of relays. Numerical results also show that as expected, the MRS outperforms the SRS in terms of its SRT. Additionally, we present some open challenges and future directions for the wireless relay aided physical-layer security.
Symbolic Segmentation Using Algorithm Selection
Venue: arXiv cs.CV 2015
Year: 2015

In this paper we present an alternative approach to symbolic segmentation; instead of implementing a new method we approach symbolic segmentation as an algorithm selection problem. That is, let there be $n$ available algorithms for symbolic segmentation, a selection mechanism forms a set of input features and image attributes and selects on a case by case basis the best algorithm. The selection mechanism is demonstrated from within an algorithm framework where the selection is done in a set of various algorithm networks. Two sets of experiments are performed and in both cases we demonstrate that the algorithm selection allows to increase the result of the symbolic segmentation by a considerable amount.
Continuous Mental Effort Evaluation during 3D Object Manipulation Tasks based on Brain and Physiological Signals
Venue: arXiv cs.HC 2015
Year: 2015

Designing 3D User Interfaces (UI) requires adequate evaluation tools to ensure good usability and user experience. While many evaluation tools are already available and widely used, existing approaches generally cannot provide continuous and objective measures of usa-bility qualities during interaction without interrupting the user. In this paper, we propose to use brain (with ElectroEncephaloGraphy) and physiological (ElectroCardioGraphy, Galvanic Skin Response) signals to continuously assess the mental effort made by the user to perform 3D object manipulation tasks. We first show how this mental effort (a.k.a., mental workload) can be estimated from such signals, and then measure it on 8 participants during an actual 3D object manipulation task with an input device known as the CubTile. Our results suggest that monitoring workload enables us to continuously assess the 3DUI and/or interaction technique ease-of-use. Overall, this suggests that this new measure could become a useful addition to the repertoire of available evaluation tools, enabling a finer grain assessment of the ergonomic qualities of a given 3D user interface.
An Analogy Based Method for Freight Forwarding Cost Estimation
Venue: arXiv cs.OH 2015
Year: 2015

The author explored estimation by analogy (EBA) as a means of estimating the cost of international freight consignment. A version of the k-Nearest Neighbors algorithm (k-NN) was tested by predicting job costs from a database of over 5000 actual jobs booked by an Irish freight forwarding firm over a seven year period. The effect of a computer intensive training process on overall accuracy of the method was found to be insignificant when the method was implemented with four or fewer neighbors. Overall, the accuracy of the analogy based method, while still significantly less accurate than manually working up estimates, might be worthwhile to implement in practice, depending labor costs in an adopting firm. A simulation model was used to compare manual versus analytical estimation methods. The point of indifference occurs when it takes a firm more than 1.5 worker hours to prepare a manual estimate (at current Irish labor costs). Suggestions are given for future experiments to improve the sampling policy of the method to improve accuracy and to improve overall scalability.
Predicting Regional Economic Indices using Big Data of Individual Bank Card Transactions
Venue: arXiv cs.CY 2015
Year: 2015

For centuries quality of life was a subject of studies across different disciplines. However, only with the emergence of a digital era, it became possible to investigate this topic on a larger scale. Over time it became clear that quality of life not only depends on one, but on three relatively different parameters: social, economic and well-being measures. In this study we focus only on the first two, since the last one is often very subjective and consequently hard to measure. Using a complete set of bank card transactions recorded by Banco Bilbao Vizcaya Argentaria (BBVA) during 2011 in Spain, we first create a feature space by defining various meaningful characteristics of a particular area performance through activity of its businesses, residents and visitors. We then evaluate those quantities by considering available official statistics for Spanish provinces (e.g., housing prices, unemployment rate, life expectancy) and investigate whether they can be predicted based on our feature space. For the purpose of prediction, our study proposes a supervised machine learning approach. Our finding is that there is a clear correlation between individual spending behavior and official socioeconomic indexes denoting quality of life. Moreover, we believe that this modus operandi is useful to understand, predict and analyze the impact of human activity on the wellness of our society on scales for which there is no consistent official statistics available (e.g., cities and towns, districts or smaller neighborhoods).
An Efficient Dynamic Programming Algorithm for STR-IC-SEQ-EC-LCS Problem
Venue: arXiv cs.DS 2015
Year: 2015

In this paper, we consider a generalized longest common subsequence problem, in which a constraining sequence of length $s$ must be included as a substring and the other constraining sequence of length $t$ must be excluded as a subsequence of two main sequences and the length of the result must be maximal. For the two input sequences $X$ and $Y$ of lengths $n$ and $m$, and the given two constraining sequences of length $s$ and $t$, we present an $O(nmst)$ time dynamic programming algorithm for solving the new generalized longest common subsequence problem. The time complexity can be reduced further to cubic time in a more detailed analysis. The correctness of the new algorithm is proved.
Modeling of Mobile Vehicle Skid in Traction Movement Mode
Venue: arXiv cs.SY 2015
Year: 2015

In the paper, a mathematical model assembling a "driver - mobile vehicle - road environment" system and capable of simulating the process of mobile vehicles skid in traction movement mode is proposed. The usage of non-linear drift models allows the development of efficient algorithms for mobile vehicles dynamic stabilization systems.
A Novel Energy Aware Node Clustering Algorithm for Wireless Sensor Networks Using a Modified Artificial Fish Swarm Algorithm
Venue: arXiv cs.AI 2015
Year: 2015

Clustering problems are considered amongst the prominent challenges in statistics and computational science. Clustering of nodes in wireless sensor networks which is used to prolong the life-time of networks is one of the difficult tasks of clustering procedure. In order to perform nodes clustering, a number of nodes are determined as cluster heads and other ones are joined to one of these heads, based on different criteria e.g. Euclidean distance. So far, different approaches have been proposed for this process, where swarm and evolutionary algorithms contribute in this regard. In this study, a novel algorithm is proposed based on Artificial Fish Swarm Algorithm (AFSA) for clustering procedure. In the proposed method, the performance of the standard AFSA is improved by increasing balance between local and global searches. Furthermore, a new mechanism has been added to the base algorithm for improving convergence speed in clustering problems. Performance of the proposed technique is compared to a number of state-of-the-art techniques in this field and the outcomes indicate the supremacy of the proposed technique.
Resolvability in Eγ with Applications to Lossy Compression and Wiretap Channels
Venue: arXiv cs.IT 2015
Year: 2015

We study the amount of randomness needed for an input process to approximate a given output distribution of a channel in the $E_γ$ distance. A general one-shot achievability bound for the precision of such an approximation is developed. In the i.i.d.~setting where $γ=\exp(nE)$, a (nonnegative) randomness rate above $\inf_{Q_{\sf U}: D(Q_{\sf X}||π_{\sf X})\le E} \{D(Q_{\sf X}||π_{\sf X})+I(Q_{\sf U},Q_{\sf X|U})-E\}$ is necessary and sufficient to asymptotically approximate the output distribution $π_{\sf X}^{\otimes n}$ using the channel $Q_{\sf X|U}^{\otimes n}$, where $Q_{\sf U}\to Q_{\sf X|U}\to Q_{\sf X}$. The new resolvability result is then used to derive a one-shot upper bound on the error probability in the rate distortion problem, and a lower bound on the size of the eavesdropper list to include the actual message in the wiretap channel problem. Both bounds are asymptotically tight in i.i.d.~settings.
Measurement Matrix Design for Compressive Detection with Secrecy Guarantees
Venue: arXiv cs.IT 2015
Year: 2015

In this letter, we consider the problem of detecting a high dimensional signal based on compressed measurements with physical layer secrecy guarantees. We assume that the network operates in the presence of an eavesdropper who intends to discover the state of the nature being monitored by the system. We design measurement matrices which maximize the detection performance of the network while guaranteeing a certain level of secrecy. We solve the measurement matrix design problem under three different scenarios: $a)$ signal is known, $b)$ signal lies in a low dimensional subspace, and $c)$ signal is sparse. It is shown that the security performance of the system can be improved by using optimized measurement matrices along with artificial noise injection based techniques.
Monotonic Properties of Collections of Maximum Independent Sets of a Graph
Venue: arXiv cs.DM 2015
Year: 2015

Let G be a simple graph with vertex set V(G). A subset S of V(G) is independent if no two vertices from S are adjacent. The graph G is known to be a Konig-Egervary if alpha(G) + mu(G)= |V(G)|, where alpha(G) denotes the size of a maximum independent set and mu(G) is the cardinality of a maximum matching. Let Omega(G) denote the family of all maximum independent sets, and f be the function from the set of subcollections Gamma of Omega(G) such that f(Gamma) = (the cardinality of the union of elements of Gamma) + (the cardinality of the intersection of elements of Gamma). Our main finding claims that f is "<<"-increasing, where the preorder {Gamma1} << {Gamma2} means that the union of all elements of {Gamma1} is a subset of the union of all elements of {Gamma2}, while the intersection of all elements of {Gamma2} is a subset of the intersection of all elements of {Gamma1}. Let us say that a family {Gamma} is a Konig-Egervary collection if f(Gamma) = 2*alpha(G). We conclude with the observation that for every graph G each subcollection of a Konig-Egervary collection is Konig-Egervary as well.
Communication Complexity of Permutation-Invariant Functions
Venue: arXiv cs.CC 2015
Year: 2015

Motivated by the quest for a broader understanding of communication complexity of simple functions, we introduce the class of "permutation-invariant" functions. A partial function $f:\{0,1\}^n \times \{0,1\}^n\to \{0,1,?\}$ is permutation-invariant if for every bijection $π:\{1,\ldots,n\} \to \{1,\ldots,n\}$ and every $\mathbf{x}, \mathbf{y} \in \{0,1\}^n$, it is the case that $f(\mathbf{x}, \mathbf{y}) = f(\mathbf{x}^π, \mathbf{y}^π)$. Most of the commonly studied functions in communication complexity are permutation-invariant. For such functions, we present a simple complexity measure (computable in time polynomial in $n$ given an implicit description of $f$) that describes their communication complexity up to polynomial factors and up to an additive error that is logarithmic in the input size. This gives a coarse taxonomy of the communication complexity of simple functions. Our work highlights the role of the well-known lower bounds of functions such as 'Set-Disjointness' and 'Indexing', while complementing them with the relatively lesser-known upper bounds for 'Gap-Inner-Product' (from the sketching literature) and 'Sparse-Gap-Inner-Product' (from the recent work of Canonne et al. [ITCS 2015]). We also present consequences to the study of communication complexity with imperfectly shared randomness where we show that for total permutation-invariant functions, imperfectly shared randomness results in only a polynomial blow-up in communication complexity after an additive $O(\log \log n)$ overhead.
A Matrix Public Key Cryptosystem
Venue: arXiv cs.CR 2015
Year: 2015

We discuss a matrix public key cryptosystem and its numerical implementation.
Visual Madlibs: Fill in the blank Image Generation and Question Answering
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we introduce a new dataset consisting of 360,001 focused natural language descriptions for 10,738 images. This dataset, the Visual Madlibs dataset, is collected using automatically produced fill-in-the-blank templates designed to gather targeted descriptions about: people and objects, their appearances, activities, and interactions, as well as inferences about the general scene or its broader context. We provide several analyses of the Visual Madlibs dataset and demonstrate its applicability to two new description generation tasks: focused description generation, and multiple-choice question-answering for images. Experiments using joint-embedding and deep learning methods show promising results on these tasks.
Manufacturing Pathway and Experimental Demonstration for Nanoscale Fine-Grained 3-D Integrated Circuit Fabric
Venue: arXiv cs.OH 2015
Year: 2015

At sub-20nm technologies CMOS scaling faces severe challenges primarily due to fundamental device scaling limitations, interconnection overhead and complex manufacturing. Migration to 3D has been long sought as a possible pathway to continue scaling, however, intrinsic requirements of CMOS are not compatible for fine-grained 3D integration. We proposed a truly fine-grained 3D integrated circuit fabric called Skybridge that solves nanoscale challenges and achieves orders of magnitude benefits over CMOS. In Skybridge, device, circuit, connectivity, thermal management and manufacturing issues are addressed in an integrated 3D compatible manner. At the core of Skybridge assembly are uniform vertical nanowires, which are functionalized with architected features for fabric integration. All active components are created primarily using sequential material deposition steps on these nanowires. Lithography and doping are performed prior to any functionalization and their precision requirements are significantly reduced. This paper introduces Skybridge manufacturing pathway that is developed based on extensive process, device simulations and experimental metrology, and uses established processes. Experimental demonstrations of key process steps are also shown.
Copeland Dueling Bandits
Venue: arXiv cs.LG 2015
Year: 2015

A version of the dueling bandit problem is addressed in which a Condorcet winner may not exist. Two algorithms are proposed that instead seek to minimize regret with respect to the Copeland winner, which, unlike the Condorcet winner, is guaranteed to exist. The first, Copeland Confidence Bound (CCB), is designed for small numbers of arms, while the second, Scalable Copeland Bandits (SCB), works better for large-scale problems. We provide theoretical results bounding the regret accumulated by CCB and SCB, both substantially improving existing results. Such existing results either offer bounds of the form $O(K \log T)$ but require restrictive assumptions, or offer bounds of the form $O(K^2 \log T)$ without requiring such assumptions. Our results offer the best of both worlds: $O(K \log T)$ bounds without restrictive assumptions.
Learning to Answer Questions From Image Using Convolutional Neural Network
Venue: arXiv cs.CL 2015
Year: 2015

In this paper, we propose to employ the convolutional neural network (CNN) for the image question answering (QA). Our proposed CNN provides an end-to-end framework with convolutional architectures for learning not only the image and question representations, but also their inter-modal interactions to produce the answer. More specifically, our model consists of three CNNs: one image CNN to encode the image content, one sentence CNN to compose the words of the question, and one multimodal convolution layer to learn their joint representation for the classification in the space of candidate answer words. We demonstrate the efficacy of our proposed model on the DAQUAR and COCO-QA datasets, which are two benchmark datasets for the image QA, with the performances significantly outperforming the state-of-the-art.
Formal Concept Analysis for Knowledge Discovery from Biological Data
Venue: arXiv cs.AI 2015
Year: 2015

Due to rapid advancement in high-throughput techniques, such as microarrays and next generation sequencing technologies, biological data are increasing exponentially. The current challenge in computational biology and bioinformatics research is how to analyze these huge raw biological data to extract biologically meaningful knowledge. This review paper presents the applications of formal concept analysis for the analysis and knowledge discovery from biological data, including gene expression discretization, gene co-expression mining, gene expression clustering, finding genes in gene regulatory networks, enzyme/protein classifications, binding site classifications, and so on. It also presents a list of FCA-based software tools applied in biological domain and covers the challenges faced so far.
Hadoop Scheduling Base On Data Locality
Venue: arXiv cs.DC 2015
Year: 2015

In hadoop, the job scheduling is an independent module, users can design their own job scheduler based on their actual application requirements, thereby meet their specific business needs. Currently, hadoop has three schedulers: FIFO, computing capacity scheduling and fair scheduling policy, all of them are take task allocation strategy that considerate data locality simply. They neither support data locality well nor fully apply to all cases of jobs scheduling. In this paper, we took the concept of resources-prefetch into consideration, and proposed a job scheduling algorithm based on data locality. By estimate the remaining time to complete a task, compared with the time to transfer a resources block, to preselect candidate nodes for task allocation. Then we preselect a non-local map tasks from the unfinished job queue as resources-prefetch tasks. Getting information of resources blocks of preselected map task, select a nearest resources blocks from the candidate node and transferred to local through network. Thus we would ensure data locality good enough. Eventually, we design a experiment and proved resources-prefetch method can guarantee good job data locality and reduce the time to complete the job to a certain extent.
On the shortest path game: extended version
Venue: arXiv cs.DM 2015
Year: 2015

In this work we address a game theoretic variant of the shortest path problem, in which two decision makers (players) move together along the edges of a graph from a given starting vertex to a given destination. The two players take turns in deciding in each vertex which edge to traverse next. The decider in each vertex also has to pay the cost of the chosen edge. We want to determine the path where each player minimizes its costs taking into account that also the other player acts in a selfish and rational way. Such a solution is a subgame perfect equilibrium and can be determined by backward induction in the game tree of the associated finite game in extensive form. We show that the decision problem associated with such a path is PSPACE-complete even for bipartite graphs both for the directed and the undirected version. The latter result is a surprising deviation from the complexity status of the closely related game Geography. On the other hand, we can give polynomial time algorithms for directed acyclic graphs and for cactus graphs even in the undirected case. The latter is based on a decomposition of the graph into components and their resolution by a number of fairly involved dynamic programming arrays. Finally, we give some arguments about closing the gap of the complexity status for graphs of bounded treewidth.
Constraint Satisfaction and Semilinear Expansions of Addition over the Rationals and the Reals
Venue: arXiv cs.CC 2015
Year: 2015

A semilinear relation is a finite union of finite intersections of open and closed half-spaces over, for instance, the reals, the rationals, or the integers. Semilinear relations have been studied in connection with algebraic geometry, automata theory, and spatiotemporal reasoning. We consider semilinear relations over the rationals and the reals. Under this assumption, the computational complexity of the constraint satisfaction problem (CSP) is known for all finite sets containing R+={(x,y,z) | x+y=z}, <=, and {1}. These problems correspond to expansions of the linear programming feasibility problem. We generalise this result and fully determine the complexity for all finite sets of semilinear relations containing R+. This is accomplished in part by introducing an algorithm, based on computing affine hulls, which solves a new class of semilinear CSPs in polynomial time. We further analyse the complexity of linear optimisation over the solution set and the existence of integer solutions.