OpenRaiser/Intern-Atlas huggingface dataset:
Evaluating Opportunistic Delivery of Large Content with TCP over WiFi in I2V Communication
Venue: arXiv cs.NI 2014
Year: 2014

With the increasing interest in connected vehicles, it is useful to evaluate the capability of delivering large content over a WiFi infrastructure to vehicles. The throughput achieved over WiFi channels can be highly variable and also rapidly degrades as the distance from the access point increases. While this behavior is well understood at the data link layer, the interactions across the various protocol layers (data link and up through the transport layer) and the effect of mobility may reduce the amount of content transferred to the vehicle, as it travels along the roadway. This paper examines the throughput achieved at the TCP layer over a carefully designed outdoor WiFi environment and the interactions across the layers that impact the performance achieved, as a function of the receiver mobility. The experimental studies conducted reveal that impairments over the WiFi link (frame loss, ARQ and increased delay) and the residual loss seen by TCP causes a cascade of duplicate ACKs to be generated. This triggers large congestion window reductions at the sender, leading to a drastic degradation of throughput to the vehicular client. To ensure outdoor WiFi infrastructures have the potential to sustain reasonable downlink throughput for drive-by vehicles, we speculate that there is a need to adapt how WiFi and TCP (as well as mobility protocols) function for such vehicular applications.
Entropy NAND: Early Functional Completeness in Entropy Networks
Venue: arXiv cs.IT 2014
Year: 2014

An observer increases in relative entropy as it receives information from what it is observing. In a system of only an observer and the observed, an increase in the relative entropy of the observer is a decrease in the relative entropy of the observed. Linking together these directional entropy disequilibriums we show that NAND and NOR functionality arise in such networks at very low levels of complexity.
Applying Geospatial Semantic Array Programming for a Reproducible Set of Bioclimatic Indices in Europe
Venue: arXiv cs.CE 2014
Year: 2014

Bioclimate-driven regression analysis is a widely used approach for modelling ecological niches and zonation. Although the bioclimatic complexity of the European continent is high, a particular combination of 12 climatic and topographic covariates was recently found able to reliably reproduce the ecological zoning of the Food and Agriculture Organization of the United Nations (FAO) for forest resources assessment at pan-European scale, generating the first fuzzy similarity map of FAO ecozones in Europe. The reproducible procedure followed to derive this collection of bioclimatic indices is now presented. It required an integration of data-transformation modules (D-TM) using geospatial tools such as Geographic Information System (GIS) software, and array-based mathematical implementation such as semantic array programming (SemAP). Base variables, intermediate and final covariates are described and semantically defined by providing the workflow of D-TMs and the mathematical formulation following the SemAP notation. Source layers to derive base variables were extracted by exclusively relying on global-scale public open geodata in order for the same set of bioclimatic covariates to be reproducible in any region worldwide. In particular, two freely available datasets were exploited for temperature and precipitation (WorldClim) and elevation (Global Multi-resolution Terrain Elevation Data). The working extent covers the European continent to the Urals with a resolution of 30 arc-second. The proposed set of bioclimatic covariates will be made available as open data in the European Forest Data Centre (EFDAC). The forthcoming complete set of D-TM codelets will enable the 12 covariates to be easily reproduced and expanded through free software.
Compressed Sensing With Side Information: Geometrical Interpretation and Performance Bounds
Venue: arXiv cs.IT 2014
Year: 2014

We address the problem of Compressed Sensing (CS) with side information. Namely, when reconstructing a target CS signal, we assume access to a similar signal. This additional knowledge, the side information, is integrated into CS via L1-L1 and L1-L2 minimization. We then provide lower bounds on the number of measurements that these problems require for successful reconstruction of the target signal. If the side information has good quality, the number of measurements is significantly reduced via L1-L1 minimization, but not so much via L1-L2 minimization. We provide geometrical interpretations and experimental results illustrating our findings.
Finite Automata for the Sub- and Superword Closure of CFLs: Descriptional and Computational Complexity
Venue: arXiv cs.FL 2014
Year: 2014

We answer two open questions by (Gruber, Holzer, Kutrib, 2009) on the state-complexity of representing sub- or superword closures of context-free grammars (CFGs): (1) We prove a (tight) upper bound of $2^{\mathcal{O}(n)}$ on the size of nondeterministic finite automata (NFAs) representing the subword closure of a CFG of size $n$. (2) We present a family of CFGs for which the minimal deterministic finite automata representing their subword closure matches the upper-bound of $2^{2^{\mathcal{O}(n)}}$ following from (1). Furthermore, we prove that the inequivalence problem for NFAs representing sub- or superword-closed languages is only NP-complete as opposed to PSPACE-complete for general NFAs. Finally, we extend our results into an approximation method to attack inequivalence problems for CFGs.
Linearly-Coupled Fountain Codes
Venue: arXiv cs.IT 2014
Year: 2014

Network-coded multiple access (NCMA) is a communication scheme for wireless multiple-access networks where physical-layer network coding (PNC) is employed. In NCMA, a user encodes and spreads its message into multiple packets. Time is slotted and multiple users transmit packets (one packet each) simultaneously in each timeslot. A sink node aims to decode the messages of all the users from the sequence of receptions over successive timeslots. For each timeslot, the NCMA receiver recovers multiple linear combinations of the packets transmitted in that timeslot, forming a system of linear equations. Different systems of linear equations are recovered in different timeslots. A message decoder then recovers the original messages of all the users by jointly solving multiple systems of linear equations obtained over different timeslots. We propose a low-complexity digital fountain approach for this coding problem, where each source node encodes its message into a sequence of packets using a fountain code. The aforementioned systems of linear equations recovered by the NCMA receiver effectively couple these fountain codes together. We refer to the coupling of the fountain codes as a linearly-coupled (LC) fountain code. The ordinary belief propagation (BP) decoding algorithm for conventional fountain codes is not optimal for LC fountain codes. We propose a batched BP decoding algorithm and analyze the convergence of the algorithm for general LC fountain codes. We demonstrate how to optimize the degree distributions and show by numerical results that the achievable rate region is nearly optimal. Our approach significantly reduces the decoding complexity compared with the previous NCMA schemes based on Reed-Solomon codes and random linear codes, and hence has the potential to increase throughput and decrease delay in computation-limited NCMA systems.
New SVD based initialization strategy for Non-negative Matrix Factorization
Venue: arXiv cs.LG 2014
Year: 2014

There are two problems need to be dealt with for Non-negative Matrix Factorization (NMF): choose a suitable rank of the factorization and provide a good initialization method for NMF algorithms. This paper aims to solve these two problems using Singular Value Decomposition (SVD). At first we extract the number of main components as the rank, actually this method is inspired from [1, 2]. Second, we use the singular value and its vectors to initialize NMF algorithm. In 2008, Boutsidis and Gollopoulos [3] provided the method titled NNDSVD to enhance initialization of NMF algorithms. They extracted the positive section and respective singular triplet information of the unit matrices {C(j)}k j=1 which were obtained from singular vector pairs. This strategy aims to use positive section to cope with negative elements of the singular vectors, but in experiments we found that even replacing negative elements by their absolute values could get better results than NNDSVD. Hence, we give another method based SVD to fulfil initialization for NMF algorithms (SVD-NMF). Numerical experiments on two face databases ORL and YALE [16, 17] show that our method is better than NNDSVD.
Convex Model Predictive Control for Vehicular Systems
Venue: arXiv cs.RO 2014
Year: 2014

In this work, we present a method to perform Model Predictive Control (MPC) over systems whose state is an element of $SO(n)$ for $n=2,3$. This is done without charts or any local linearization, and instead is performed by operating over the orbitope of rotation matrices. This results in a novel MPC scheme without the drawbacks associated with conventional linearization techniques. Instead, second order cone- or semidefinite-constraints on state variables are the only requirement beyond those of a QP-scheme typical for MPC of linear systems. Of particular emphasis is the application to aeronautical and vehicular systems, wherein the method removes many of the transcendental trigonometric terms associated with these systems' state space equations. Furthermore, the method is shown to be compatible with many existing variants of MPC, including obstacle avoidance via Mixed Integer Linear Programming (MILP).
Approximate False Positive Rate Control in Selection Frequency for Random Forest
Venue: arXiv cs.LG 2014
Year: 2014

Random Forest has become one of the most popular tools for feature selection. Its ability to deal with high-dimensional data makes this algorithm especially useful for studies in neuroimaging and bioinformatics. Despite its popularity and wide use, feature selection in Random Forest still lacks a crucial ingredient: false positive rate control. To date there is no efficient, principled and computationally light-weight solution to this shortcoming. As a result, researchers using Random Forest for feature selection have to resort to using heuristically set thresholds on feature rankings. This article builds an approximate probabilistic model for the feature selection process in random forest training, which allows us to compute an estimated false positive rate for a given threshold on selection frequency. Hence, it presents a principled way to determine thresholds for the selection of relevant features without any additional computational load. Experimental analysis with synthetic data demonstrates that the proposed approach can limit false positive rates on the order of the desired values and keep false negative rates low. Results show that this holds even in the presence of a complex correlation structure between features. Its good statistical properties and light-weight computational needs make this approach widely applicable to feature selection for a wide-range of applications.
On the Oblivious Transfer Capacity of Generalized Erasure Channels against Malicious Adversaries
Venue: arXiv cs.CR 2014
Year: 2014

Noisy channels are a powerful resource for cryptography as they can be used to obtain information-theoretically secure key agreement, commitment and oblivious transfer protocols, among others. Oblivious transfer (OT) is a fundamental primitive since it is complete for secure multi-party computation, and the OT capacity characterizes how efficiently a channel can be used for obtaining string oblivious transfer. Ahlswede and Csiszár (\emph{ISIT'07}) presented upper and lower bounds on the OT capacity of generalized erasure channels (GEC) against passive adversaries. In the case of GEC with erasure probability at least 1/2, the upper and lower bounds match and therefore the OT capacity was determined. It was later proved by Pinto et al. (\emph{IEEE Trans. Inf. Theory 57(8)}) that in this case there is also a protocol against malicious adversaries achieving the same lower bound, and hence the OT capacity is identical for passive and malicious adversaries. In the case of GEC with erasure probability smaller than 1/2, the known lower bound against passive adversaries that was established by Ahlswede and Csiszár does not match their upper bound and it was unknown whether this OT rate could be achieved against malicious adversaries as well. In this work we show that there is a protocol against malicious adversaries achieving the same OT rate that was obtained against passive adversaries. In order to obtain our results we introduce a novel use of interactive hashing that is suitable for dealing with the case of low erasure probability ($p^* <1/2$).
Towards Static Analysis of Functional Programs using Tree Automata Completion
Venue: arXiv cs.LO 2014
Year: 2014

This paper presents the first step of a wider research effort to apply tree automata completion to the static analysis of functional programs. Tree Automata Completion is a family of techniques for computing or approximating the set of terms reachable by a rewriting relation. The completion algorithm we focus on is parameterized by a set E of equations controlling the precision of the approximation and influencing its termination. For completion to be used as a static analysis, the first step is to guarantee its termination. In this work, we thus give a sufficient condition on E and T(F) for completion algorithm to always terminate. In the particular setting of functional programs, this condition can be relaxed into a condition on E and T(C) (terms built on the set of constructors) that is closer to what is done in the field of static analysis, where abstractions are performed on data.
Quadratic Zero-Difference Balanced Functions, APN Functions and Strongly Regular Graphs
Venue: arXiv cs.IT 2014
Year: 2014

Let $F$ be a function from $\mathbb{F}_{p^n}$ to itself and $δ$ a positive integer. $F$ is called zero-difference $δ$-balanced if the equation $F(x+a)-F(x)=0$ has exactly $δ$ solutions for all non-zero $a\in\mathbb{F}_{p^n}$. As a particular case, all known quadratic planar functions are zero-difference 1-balanced; and some quadratic APN functions over $\mathbb{F}_{2^n}$ are zero-difference 2-balanced. In this paper, we study the relationship between this notion and differential uniformity; we show that all quadratic zero-difference $δ$-balanced functions are differentially $δ$-uniform and we investigate in particular such functions with the form $F=G(x^d)$, where $\gcd(d,p^n-1)=δ+1$ and where the restriction of $G$ to the set of all non-zero $(δ+1)$-th powers in $\mathbb{F}_{p^n}$ is an injection. We introduce new families of zero-difference $p^t$-balanced functions. More interestingly, we show that the image set of such functions is a regular partial difference set, and hence yields strongly regular graphs; this generalizes the constructions of strongly regular graphs using planar functions by Weng et al. Using recently discovered quadratic APN functions on $\mathbb{F}_{2^8}$, we obtain $15$ new $(256, 85, 24, 30)$ negative Latin square type strongly regular graphs.
Coverage Region Analysis for MIMO Amplify-and-Forward Relay Channel with the Source to Destination Link
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we study and analyze coverage region for half-duplex multiple-input multiple-output (MIMO) relay channel with amplify-and-forward (AF) strategy at the relay station. By assuming mixed Rayleigh and Rician fading channels with two different relay station situations, we consider the objective of maximizing coverage region for a given transmission rate and find the optimal relay location in the sense of maximizing coverage region. using Monte Carlo simulations, the coverage region and capacity bounds are shown for different fading cases and different relay station locations. Finally, we compare our results with previous ones obtained for decode-and-forward (DF) MIMO relay channel.
Communicating Lists Over a Noisy Channel
Venue: arXiv cs.IT 2014
Year: 2014

This work considers a communication scenario where the transmitter chooses a list of size K from a total of M messages to send over a noisy communication channel, the receiver generates a list of size L and communication is considered successful if the intersection of the lists at two terminals has cardinality greater than a threshold T. In traditional communication systems K=L=T=1. The fundamental limits of this setup in terms of K, L, T and the Shannon capacity of the channel between the terminals are examined. Specifically, necessary and/or sufficient conditions for asymptotically error free communication are provided.
GSP with General Independent Click-Through-Rates
Venue: arXiv cs.GT 2014
Year: 2014

The popular generalized second price (GSP) auction for sponsored search is built upon a separable model of click-through-rates that decomposes the likelihood of a click into the product of a "slot effect" and an "advertiser effect" --- if the first slot is twice as good as the second for some bidder, then it is twice as good for everyone. Though appealing in its simplicity, this model is quite suspect in practice. A wide variety of factors including externalities and budgets have been studied that can and do cause it to be violated. In this paper we adopt a view of GSP as an iterated second price auction (see, e.g., Milgrom 2010) and study how the most basic violation of separability --- position dependent, arbitrary public click-through-rates that do not decompose --- affects results from the foundational analysis of GSP (Varian 2007, Edelman et al. 2007). For the two-slot setting we prove that for arbitrary click-through-rates, for arbitrary bidder values, an efficient pure-strategy equilibrium always exists; however, without separability there always exist values such that the VCG outcome and payments cannot be realized by any bids, in equilibrium or otherwise. The separability assumption is therefore necessary in the two-slot case to match the payments of VCG but not for efficiency. We moreover show that without separability, generic existence of efficient equilibria is sensitive to the choice of tie-breaking rule, and when there are more than two slots, no (bid-independent) tie-breaking rule yields the positive result. In light of this we suggest alternative mechanisms that trade the simplicity of GSP for better equilibrium properties when there are three or more slots.
Bounds on Multiple Sensor Fusion
Venue: arXiv cs.SY 2014
Year: 2014

We consider the problem of fusing measurements from multiple sensors, where the sensing regions overlap and data are non-negative---possibly resulting from a count of indistinguishable discrete entities. Because of overlaps, it is, in general, impossible to fuse this information to arrive at an accurate estimate of the overall amount or count of material present in the union of the sensing regions. Here we study the range of overall values consistent with the data. Posed as a linear programming problem, this leads to interesting questions associated with the geometry of the sensor regions, specifically, the arrangement of their non-empty intersections. We define a computational tool called the fusion polytope and derive a condition for this to be in the positive orthant thus simplifying calculations. We show that, in two dimensions, inflated tiling schemes based on rectangular regions fail to satisfy this condition, whereas inflated tiling schemes based on hexagons do.
Relational Linear Programs
Venue: arXiv cs.AI 2014
Year: 2014

We propose relational linear programming, a simple framework for combing linear programs (LPs) and logic programs. A relational linear program (RLP) is a declarative LP template defining the objective and the constraints through the logical concepts of objects, relations, and quantified variables. This allows one to express the LP objective and constraints relationally for a varying number of individuals and relations among them without enumerating them. Together with a logical knowledge base, effectively a logical program consisting of logical facts and rules, it induces a ground LP. This ground LP is solved using lifted linear programming. That is, symmetries within the ground LP are employed to reduce its dimensionality, if possible, and the reduced program is solved using any off-the-shelf LP solver. In contrast to mainstream LP template languages like AMPL, which features a mixture of declarative and imperative programming styles, RLP's relational nature allows a more intuitive representation of optimization problems over relational domains. We illustrate this empirically by experiments on approximate inference in Markov logic networks using LP relaxations, on solving Markov decision processes, and on collective inference using LP support vector machines.
Multi-Scale Local Shape Analysis and Feature Selection in Machine Learning Applications
Venue: arXiv cs.CG 2014
Year: 2014

We introduce a method called multi-scale local shape analysis, or MLSA, for extracting features that describe the local structure of points within a dataset. The method uses both geometric and topological features at multiple levels of granularity to capture diverse types of local information for subsequent machine learning algorithms operating on the dataset. Using synthetic and real dataset examples, we demonstrate significant performance improvement of classification algorithms constructed for these datasets with correspondingly augmented features.
Workshop Summary of the 1st International Workshop on Requirements and Testing (RET'14)
Venue: arXiv cs.SE 2014
Year: 2014

The main objective of the RET workshop was to explore the interaction of Requirements Engineering (RE) and Testing, i.e. RET, in research and industry, and the challenges that result from this interaction. While much work has been done in the respective fields of requirements engineering and testing, there exists much more than can be done to understand the connection between the processes of RE and of testing.
Heterogeneous High Throughput Scientific Computing with APM X-Gene and Intel Xeon Phi
Venue: arXiv cs.DC 2014
Year: 2014

Electrical power requirements will be a constraint on the future growth of Distributed High Throughput Computing (DHTC) as used by High Energy Physics. Performance-per-watt is a critical metric for the evaluation of computer architectures for cost- efficient computing. Additionally, future performance growth will come from heterogeneous, many-core, and high computing density platforms with specialized processors. In this paper, we examine the Intel Xeon Phi Many Integrated Cores (MIC) co-processor and Applied Micro X-Gene ARMv8 64-bit low-power server system-on-a-chip (SoC) solutions for scientific computing applications. We report our experience on software porting, performance and energy efficiency and evaluate the potential for use of such technologies in the context of distributed computing systems such as the Worldwide LHC Computing Grid (WLCG).