OpenRaiser/Intern-Atlas huggingface dataset:
The Barth-Boneh-Waters Private Broadcast Encryption Scheme Revisited
Venue: arXiv cs.CR 2014
Year: 2014

The primitive of private broadcast encryption introduced by Barth, Boneh and Waters, is used to encrypt a message to several recipients while hiding the identities of the recipients. In their construction, a recipient has to first decrypt the received ciphertext to extract the verification key for one-time signature. He then uses the verification key to check whether the ciphertext is malformed. The authors did not consider that information delivered over a channel, especially over a broadcast channel, should be authenticated as to its origin. We remark that the conventional public key signature suffices to authenticate data origin and filter out all malformed ciphertexts. We also discuss the disadvantages of the primitive of one-time signature used in their construction.
Falsifiable implies Learnable
Venue: arXiv cs.LG 2014
Year: 2014

The paper demonstrates that falsifiability is fundamental to learning. We prove the following theorem for statistical learning and sequential prediction: If a theory is falsifiable then it is learnable -- i.e. admits a strategy that predicts optimally. An analogous result is shown for universal induction.
Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree
Venue: arXiv cs.CC 2014
Year: 2014

A homomorphism from a graph G to a graph H is locally bijective, surjective, or injective if its restriction to the neighborhood of every vertex of G is bijective, surjective, or injective, respectively. We prove that the problems of testing whether a given graph G allows a homomorphism to a given graph H that is locally bijective, surjective, or injective, respectively, are NP-complete, even when G has pathwidth at most 5, 4, or 2, respectively, or when both G and H have maximum degree 3. We complement these hardness results by showing that the three problems are polynomial-time solvable if G has bounded treewidth and in addition G or H has bounded maximum degree.
GPGPU Computing
Venue: arXiv cs.DC 2014
Year: 2014

Since the first idea of using GPU to general purpose computing, things have evolved over the years and now there are several approaches to GPU programming. GPU computing practically began with the introduction of CUDA (Compute Unified Device Architecture) by NVIDIA and Stream by AMD. These are APIs designed by the GPU vendors to be used together with the hardware that they provide. A new emerging standard, OpenCL (Open Computing Language) tries to unify different GPU general computing API implementations and provides a framework for writing programs executed across heterogeneous platforms consisting of both CPUs and GPUs. OpenCL provides parallel computing using task-based and data-based parallelism. In this paper we will focus on the CUDA parallel computing architecture and programming model introduced by NVIDIA. We will present the benefits of the CUDA programming model. We will also compare the two main approaches, CUDA and AMD APP (STREAM) and the new framwork, OpenCL that tries to unify the GPGPU computing models.
Weak Unit Disk and Interval Representation of Planar Graphs
Venue: arXiv cs.DM 2014
Year: 2014

We study a variant of intersection representations with unit balls, that is, unit disks in the plane and unit intervals on the line. Given a planar graph and a bipartition of the edges of the graph into near and far sets, the goal is to represent the vertices of the graph by unit balls so that the balls representing two adjacent vertices intersect if and only if the corresponding edge is near. We consider the problem in the plane and prove that it is NP-hard to decide whether such a representation exists for a given edge-partition. On the other hand, every series-parallel graph admits such a representation with unit disks for any near/far labeling of the edges. We also show that the representation problem on the line is equivalent to a variant of a graph coloring. We give examples of girth-4 planar and girth-3 outerplanar graphs that have no such representation with unit intervals. On the other hand, all triangle-free outerplanar graphs and all graphs with maximum average degree less than 26/11 can always be represented. In particular, this gives a simple proof of representability of all planar graphs with large girth.
On Index Coding and Graph Homomorphism
Venue: arXiv cs.IT 2014
Year: 2014

In this work, we study the problem of index coding from graph homomorphism perspective. We show that the minimum broadcast rate of an index coding problem for different variations of the problem such as non-linear, scalar, and vector index code, can be upper bounded by the minimum broadcast rate of another index coding problem when there exists a homomorphism from the complement of the side information graph of the first problem to that of the second problem. As a result, we show that several upper bounds on scalar and vector index code problem are special cases of one of our main theorems. For the linear scalar index coding problem, it has been shown in [1] that the binary linear index of a graph is equal to a graph theoretical parameter called minrank of the graph. For undirected graphs, in [2] it is shown that $\mathrm{minrank}(G) = k$ if and only if there exists a homomorphism from $\bar{G}$ to a predefined graph $\bar{G}_k$. Combining these two results, it follows that for undirected graphs, all the digraphs with linear index of at most k coincide with the graphs $G$ for which there exists a homomorphism from $\bar{G}$ to $\bar{G}_k$. In this paper, we give a direct proof to this result that works for digraphs as well. We show how to use this classification result to generate lower bounds on scalar and vector index. In particular, we provide a lower bound for the scalar index of a digraph in terms of the chromatic number of its complement. Using our framework, we show that by changing the field size, linear index of a digraph can be at most increased by a factor that is independent from the number of the nodes.
Faster Computation of Expected Hypervolume Improvement
Venue: arXiv cs.DS 2014
Year: 2014

The expected improvement algorithm (or efficient global optimization) aims for global continuous optimization with a limited budget of black-box function evaluations. It is based on a statistical model of the function learned from previous evaluations and an infill criterion - the expected improvement - used to find a promising point for a new evaluation. The `expected improvement' infill criterion takes into account the mean and variance of a predictive multivariate Gaussian distribution. The expected improvement algorithm has recently been generalized to multiobjective optimization. In order to measure the improvement of a Pareto front quantitatively the gain in dominated (hyper-)volume is used. The computation of the expected hypervolume improvement (EHVI) is a multidimensional integration of a step-wise defined non-linear function related to the Gaussian probability density function over an intersection of boxes. This paper provides a new algorithm for the exact computation of the expected improvement to more than two objective functions. For the bicriteria case it has a time complexity in $O(n^2)$ with $n$ denoting the number of points in the current best Pareto front approximation. It improves previously known algorithms with time complexity $O(n^3 \log n)$. For tricriteria optimization we devise an algorithm with time complexity of $O(n^3)$. Besides discussing the new time complexity bounds the speed of the new algorithm is also tested empirically on test data. It is shown that further improvements in speed can be achieved by reusing data structures built up in previous iterations. The resulting numerical algorithms can be readily used in existing implementations of hypervolume-based expected improvement algorithms.
A Secure TFTP Protocol with Security Proofs
Venue: arXiv cs.CR 2014
Year: 2014

Advances in smart devices has witnessed major developments in many mobile applications such as Android applications. These smart devices normally interconnect to the internet using wireless technology and applications using the TFTP protocol among these wireless devices are becoming commonplace. In this work, we present an enhanced lightweight security protocol for smart device and server communications using Trivial File Transfer Protocol (TFTP). We suggest the use of lightweight symmetric encryption for data encryption and asymmetric encryption for key exchange protocols in TFTP. The target implementation of secure TFTP is for embedded devices such as Wi-Fi Access Points (AP) and remote Base Stations (BS). In this paper we present the security proofs based on an attack model (IND-CCA2) for securing TFTP protocol. We also present the security reduction of SSW-ARQ protocol from Cramer-Shoup encryption scheme and fixed-time side channel security. We have also introduced a novel adversary model in IND-CCA2-(SC-TA) and it is considered a practical model because the model incorporates the timing attack.
Simultaneous Wireless Information and Power Transfer in Modern Communication Systems
Venue: arXiv cs.IT 2014
Year: 2014

Energy harvesting for wireless communication networks is a new paradigm that allows terminals to recharge their batteries from external energy sources in the surrounding environment. A promising energy harvesting technology is wireless power transfer where terminals harvest energy from electromagnetic radiation. Thereby, the energy may be harvested opportunistically from ambient electromagnetic sources or from sources that intentionally transmit electromagnetic energy for energy harvesting purposes. A particularly interesting and challenging scenario arises when sources perform simultaneous wireless information and power transfer (SWIPT), as strong signals not only increase power transfer but also interference. This paper provides an overview of SWIPT systems with a particular focus on the hardware realization of rectenna circuits and practical techniques that achieve SWIPT in the domains of time, power, antennas, and space. The paper also discusses the benefits of a potential integration of SWIPT technologies in modern communication networks in the context of resource allocation and cooperative cognitive radio networks.
Towards a Calculus of Echo State Networks
Venue: arXiv cs.NE 2014
Year: 2014

Reservoir computing is a recent trend in neural networks which uses the dynamical perturbations on the phase space of a system to compute a desired target function. We present how one can formulate an expectation of system performance in a simple class of reservoir computing called echo state networks. In contrast with previous theoretical frameworks, which only reveal an upper bound on the total memory in the system, we analytically calculate the entire memory curve as a function of the structure of the system and the properties of the input and the target function. We demonstrate the precision of our framework by validating its result for a wide range of system sizes and spectral radii. Our analytical calculation agrees with numerical simulations. To the best of our knowledge this work presents the first exact analytical characterization of the memory curve in echo state networks.
Energy-Aware Cloud Management through Progressive SLA Specification
Venue: arXiv cs.DC 2014
Year: 2014

Novel energy-aware cloud management methods dynamically reallocate computation across geographically distributed data centers to leverage regional electricity price and temperature differences. As a result, a managed VM may suffer occasional downtimes. Current cloud providers only offer high availability VMs, without enough flexibility to apply such energy-aware management. In this paper we show how to analyse past traces of dynamic cloud management actions based on electricity prices and temperatures to estimate VM availability and price values. We propose a novel SLA specification approach for offering VMs with different availability and price values guaranteed over multiple SLAs to enable flexible energy-aware cloud management. We determine the optimal number of such SLAs as well as their availability and price guaranteed values. We evaluate our approach in a user SLA selection simulation using Wikipedia and Grid'5000 workloads. The results show higher customer conversion and 39% average energy savings per VM.
Storing sequences in binary tournament-based neural networks
Venue: arXiv cs.NE 2014
Year: 2014

An extension to a recently introduced architecture of clique-based neural networks is presented. This extension makes it possible to store sequences with high efficiency. To obtain this property, network connections are provided with orientation and with flexible redundancy carried by both spatial and temporal redundancy, a mechanism of anticipation being introduced in the model. In addition to the sequence storage with high efficiency, this new scheme also offers biological plausibility. In order to achieve accurate sequence retrieval, a double layered structure combining hetero-association and auto-association is also proposed.
Multi-tensor Completion for Estimating Missing Values in Video Data
Venue: arXiv cs.CV 2014
Year: 2014

Many tensor-based data completion methods aim to solve image and video in-painting problems. But, all methods were only developed for a single dataset. In most of real applications, we can usually obtain more than one dataset to reflect one phenomenon, and all the datasets are mutually related in some sense. Thus one question raised whether such the relationship can improve the performance of data completion or not? In the paper, we proposed a novel and efficient method by exploiting the relationship among datasets for multi-video data completion. Numerical results show that the proposed method significantly improve the performance of video in-painting, particularly in the case of very high missing percentage.
Facets and Typed Relations as Tools for Reasoning Processes in Information Retrieval
Venue: arXiv cs.IR 2014
Year: 2014

Faceted arrangement of entities and typed relations for representing different associations between the entities are established tools in knowledge representation. In this paper, a proposal is being discussed combining both tools to draw inferences along relational paths. This approach may yield new benefit for information retrieval processes, especially when modeled for heterogeneous environments in the Semantic Web. Faceted arrangement can be used as a se-lection tool for the semantic knowledge modeled within the knowledge repre-sentation. Typed relations between the entities of different facets can be used as restrictions for selecting them across the facets.
Investigation on Demand Side Management Techniques in the Smart Grid using Game Theory and ICT Concepts
Venue: arXiv cs.DC 2014
Year: 2014

This paper investigates how concepts from game theory and ICT can contribute to solve challenges in demand side management, an important concept in the upcoming smart grid. Demand side management is about modifying the energy load distribution on the demand side, for example in order to reduce peaks in energy usage. This can be done by shifting energy demands where possible. We start with describing a number of smart grid concepts and assumptions (smart meters, pricing, appliance scheduling) and explain the advantages demand side management has. After the introduction of game theoretic concepts, it becomes possible to mathematically describe the demand side management problem. Next step is to solve the mathematical formulation, and show how complex demand side management becomes if the number of energy users increases. By means of distributed ICT algorithms however, it is possible to still find a solution. Based on existing literature, different algorithms are studied. Though results in literature looked promising, several conclusions on convergence of the algorithm in general, and convergence towards the most optimal results in particular are challenged.
How many citations are there in the Data Citation Index?
Venue: arXiv cs.DL 2014
Year: 2014

Descriptive analysis on the citation distribution of the Thomson Reuters' Data Citation Index by publication type and four broad areas: Science, Engineering & Technology, Humanities & Arts and Social Sciences.
Ensemble Learning of Colorectal Cancer Survival Rates
Venue: arXiv cs.LG 2014
Year: 2014

In this paper, we describe a dataset relating to cellular and physical conditions of patients who are operated upon to remove colorectal tumours. This data provides a unique insight into immunological status at the point of tumour removal, tumour classification and post-operative survival. We build on existing research on clustering and machine learning facets of this data to demonstrate a role for an ensemble approach to highlighting patients with clearer prognosis parameters. Results for survival prediction using 3 different approaches are shown for a subset of the data which is most difficult to model. The performance of each model individually is compared with subsets of the data where some agreement is reached for multiple models. Significant improvements in model accuracy on an unseen test set can be achieved for patients where agreement between models is achieved.
Primary User Traffic Classification in Dynamic Spectrum Access Networks
Venue: arXiv cs.PF 2014
Year: 2014

This paper focuses on analytical studies of the primary user (PU) traffic classification problem. Observing that the gamma distribution can represent positively skewed data and exponential distribution (popular in communication networks performance analysis literature) it is considered here as the PU traffic descriptor. We investigate two PU traffic classifiers utilizing perfectly measured PU activity (busy) and inactivity (idle) periods: (i) maximum likelihood classifier (MLC) and (ii) multi-hypothesis sequential probability ratio test classifier (MSPRTC). Then, relaxing the assumption on perfect period measurement, we consider a PU traffic observation through channel sampling. For a special case of negligible probability of PU state change in between two samplings, we propose a minimum variance PU busy/idle period length estimator. Later, relaxing the assumption of the complete knowledge of the parameters of the PU period length distribution, we propose two PU traffic classification schemes: (i) estimate-then-classify (ETC), and (ii) average likelihood function (ALF) classifiers considering time domain fluctuation of the PU traffic parameters. Numerical results show that both MLC and MSPRTC are sensitive to the periods measurement errors when the distance among distribution hypotheses is small, and to the distribution parameter estimation errors when the distance among hypotheses is large. For PU traffic parameters with a partial prior knowledge of the distribution, the ETC outperforms ALF when the distance among hypotheses is small, while the opposite holds when the distance is large.
Inter-session Network Coding for Transmitting Multiple Layered Streams over Single-hop Wireless Networks
Venue: arXiv cs.IT 2014
Year: 2014

This paper studies the problem of transmitting multiple independent layered video streams over single-hop wireless networks using network coding (NC). We combine feedback-free random linear NC (RLNC) with unequal error protection (UEP) and our goal is to investigate the benefits of coding across streams, i.e. inter session NC. To this end, we present a transmission scheme that in addition to mixing packets of different layers of each stream (intra-session NC), mixes packets of different streams as well. Then, we propose the analytical formulation of the layer decoding probabilities for each user and utilize it to define a theoretical performance metric. Assessing this performance metric under various scenarios, it is observed that inter-session NC improves the trade-off among the performances of users. Furthermore, the analytical results show that the throughput gain of inter-session NC over intra-session NC increases with the number of independent streams and also by increasing packet error rate, but degrades as network becomes more heterogeneous.
Citizen Electronic Identities using TPM 2.0
Venue: arXiv cs.CR 2014
Year: 2014

Electronic Identification (eID) is becoming commonplace in several European countries. eID is typically used to authenticate to government e-services, but is also used for other services, such as public transit, e-banking, and physical security access control. Typical eID tokens take the form of physical smart cards, but successes in merging eID into phone operator SIM cards show that eID tokens integrated into a personal device can offer better usability compared to standalone tokens. At the same time, trusted hardware that enables secure storage and isolated processing of sensitive data have become commonplace both on PC platforms as well as mobile devices. Some time ago, the Trusted Computing Group (TCG) released the version 2.0 of the Trusted Platform Module (TPM) specification. We propose an eID architecture based on the new, rich authorization model introduced in the TCGs TPM 2.0. The goal of the design is to improve the overall security and usability compared to traditional smart card-based solutions. We also provide, to the best our knowledge, the first accessible description of the TPM 2.0 authorization model.
Structured Low-Rank Matrix Factorization with Missing and Grossly Corrupted Observations
Venue: arXiv cs.LG 2014
Year: 2014

Recovering low-rank and sparse matrices from incomplete or corrupted observations is an important problem in machine learning, statistics, bioinformatics, computer vision, as well as signal and image processing. In theory, this problem can be solved by the natural convex joint/mixed relaxations (i.e., l_{1}-norm and trace norm) under certain conditions. However, all current provable algorithms suffer from superlinear per-iteration cost, which severely limits their applicability to large-scale problems. In this paper, we propose a scalable, provable structured low-rank matrix factorization method to recover low-rank and sparse matrices from missing and grossly corrupted data, i.e., robust matrix completion (RMC) problems, or incomplete and grossly corrupted measurements, i.e., compressive principal component pursuit (CPCP) problems. Specifically, we first present two small-scale matrix trace norm regularized bilinear structured factorization models for RMC and CPCP problems, in which repetitively calculating SVD of a large-scale matrix is replaced by updating two much smaller factor matrices. Then, we apply the alternating direction method of multipliers (ADMM) to efficiently solve the RMC problems. Finally, we provide the convergence analysis of our algorithm, and extend it to address general CPCP problems. Experimental results verified both the efficiency and effectiveness of our method compared with the state-of-the-art methods.
Anatomy of the Third-Party Web Tracking Ecosystem
Venue: arXiv cs.SI 2014
Year: 2014

The presence of third-party tracking on websites has become customary. However, our understanding of the third-party ecosystem is still very rudimentary. We examine third-party trackers from a geographical perspective, observing the third-party tracking ecosystem from 29 countries across the globe. When examining the data by region (North America, South America, Europe, East Asia, Middle East, and Oceania), we observe significant geographical variation between regions and countries within regions. We find trackers that focus on specific regions and countries, and some that are hosted in countries outside their expected target tracking domain. Given the differences in regulatory regimes between jurisdictions, we believe this analysis sheds light on the geographical properties of this ecosystem and on the problems that these may pose to our ability to track and manage the different data silos that now store personal data about us all.