OpenRaiser/Intern-Atlas huggingface dataset:
Benchmarking Practical RRM Algorithms for D2D Communications in LTE Advanced
Venue: arXiv cs.IT 2013
Year: 2013

Device-to-device (D2D) communication integrated into cellular networks is a means to take advantage of the proximity of devices and allow for reusing cellular resources and thereby to increase the user bitrates and the system capacity. However, when D2D (in the 3rd Generation Partnership Project also called Long Term Evolution (LTE) Direct) communication in cellular spectrum is supported, there is a need to revisit and modify the existing radio resource management (RRM) and power control (PC) techniques to realize the potential of the proximity and reuse gains and to limit the interference at the cellular layer. In this paper, we examine the performance of the flexible LTE PC tool box and benchmark it against a utility optimal iterative scheme. We find that the open loop PC scheme of LTE performs well for cellular users both in terms of the used transmit power levels and the achieved signal-to-interference-and-noise-ratio (SINR) distribution. However, the performance of the D2D users as well as the overall system throughput can be boosted by the utility optimal scheme, because the utility maximizing scheme takes better advantage of both the proximity and the reuse gains. Therefore, in this paper we propose a hybrid PC scheme, in which cellular users employ the open loop path compensation method of LTE, while D2D users use the utility optimizing distributed PC scheme. In order to protect the cellular layer, the hybrid scheme allows for limiting the interference caused by the D2D layer at the cost of having a small impact on the performance of the D2D layer. To ensure feasibility, we limit the number of iterations to a practically feasible level. We make the point that the hybrid scheme is not only near optimal, but it also allows for a distributed implementation for the D2D users, while preserving the LTE PC scheme for the cellular users.
Cognitive Interpretation of Everyday Activities: Toward Perceptual Narrative Based Visuo-Spatial Scene Interpretation
Venue: arXiv cs.AI 2013
Year: 2013

We position a narrative-centred computational model for high-level knowledge representation and reasoning in the context of a range of assistive technologies concerned with "visuo-spatial perception and cognition" tasks. Our proposed narrative model encompasses aspects such as \emph{space, events, actions, change, and interaction} from the viewpoint of commonsense reasoning and learning in large-scale cognitive systems. The broad focus of this paper is on the domain of "human-activity interpretation" in smart environments, ambient intelligence etc. In the backdrop of a "smart meeting cinematography" domain, we position the proposed narrative model, preliminary work on perceptual narrativisation, and the immediate outlook on constructing general-purpose open-source tools for perceptual narrativisation. ACM Classification: I.2 Artificial Intelligence: I.2.0 General -- Cognitive Simulation, I.2.4 Knowledge Representation Formalisms and Methods, I.2.10 Vision and Scene Understanding: Architecture and control structures, Motion, Perceptual reasoning, Shape, Video analysis General keywords: cognitive systems; human-computer interaction; spatial cognition and computation; commonsense reasoning; spatial and temporal reasoning; assistive technologies
Cryptanalysis of a non-commutative key exchange protocol
Venue: arXiv cs.IT 2013
Year: 2013

In the papers by Alvarez et al. and Pathak and Sanghi a non-commutative based public key exchange is described. A similiar version of it has also been patented (US7184551). In this paper we present a polynomial time attack that breaks the variants of the protocol presented in the two papers. Moreover we show that breaking the patented cryptosystem US7184551 can be easily reduced to factoring. We also give some examples to show how efficiently the attack works.
Thresholds of Random Quasi-Abelian Codes
Venue: arXiv cs.IT 2013
Year: 2013

For a random quasi-abelian code of rate $r$, it is shown that the GV-bound is a threshold point: if $r$ is less than the GV-bound at $δ$, then the probability of the relative distance of the random code being greater than $δ$ is almost 1; whereas, if $r$ is bigger than the GV-bound at $δ$, then the probability is almost 0. As a consequence, there exist many asymptotically good quasi-abelian codes with any parameters attaining the GV-bound.
P-HGRMS: A Parallel Hypergraph Based Root Mean Square Algorithm for Image Denoising
Venue: arXiv cs.DC 2013
Year: 2013

This paper presents a parallel Salt and Pepper (SP) noise removal algorithm in a grey level digital image based on the Hypergraph Based Root Mean Square (HGRMS) approach. HGRMS is generic algorithm for identifying noisy pixels in any digital image using a two level hierarchical serial approach. However, for SP noise removal, we reduce this algorithm to a parallel model by introducing a cardinality matrix and an iteration factor, k, which helps us reduce the dependencies in the existing approach. We also observe that the performance of the serial implementation is better on smaller images, but once the threshold is achieved in terms of image resolution, its computational complexity increases drastically. We test P-HGRMS using standard images from the Berkeley Segmentation dataset on NVIDIAs Compute Unified Device Architecture (CUDA) for noise identification and attenuation. We also compare the noise removal efficiency of the proposed algorithm using Peak Signal to Noise Ratio (PSNR) to the existing approach. P-HGRMS maintains the noise removal efficiency and outperforms its sequential counterpart by 6 to 18 times (6x - 18x) in computational efficiency.
Extrinsically adaptable systems
Venue: arXiv cs.CY 2013
Year: 2013

Are there qualitative and quantitative traits of system design that contribute to the ability of people to further innovate? We propose that extrinsic adaptability, the ability given to secondary parties to change a system to match new requirements not envisioned by the primary provider, is such a trait. "Extrinsic adaptation" encompasses the popular concepts of "workaround", "fast prototype extension" or "hack", and extrinsic adaptability is thus a measure of how friendly a system is to tinkering by curious minds. In this report, we give "hackability" or "hacker-friendliness" scientific credentials by formulating and studying a generalization of the concept. During this exercise, we find that system changes by secondary parties fall on a subjective gradient of acceptability, with extrinsic adaptations on one side which confidently preserve existing system features, and invasive modifications on the other side which are perceived to be disruptive to existing system features. Where a change is positioned on this gradient is dependent on how an external observer perceives component boundaries within the changed system. We also find that the existence of objective cost functions can alleviate but not fully eliminate this subjectiveness. The study also enables us to formulate an ethical imperative for system designers to promote extrinsic adaptability.
Combinatorial method of polynomial expansion of symmetric Boolean functions
Venue: arXiv cs.DM 2013
Year: 2013

A novel polynomial expansion method of symmetric Boolean functions is described. The method is efficient for symmetric Boolean function with small set of valued numbers and has the linear complexity for elementary symmetric Boolean functions, while the complexity of the known methods for this class of functions is quadratic. The proposed method is based on the consequence of the combinatorial Lucas theorem.
Modifying the Entity relationship modelling notation: towards high quality relational databases from better notated ER models
Venue: arXiv cs.DB 2013
Year: 2013

The entity relationship modelling using the original ER notation has been applauded providing a natural view of data in conceptual modelling of information systems. However, the current ER to relational model transformation algorithm is known to be insufficient in providing a complete and accurate representation of the ER model undertaken for transformation. In an effort to derive better transformations from ER models, we have understood that modifications should be introduced to both of the existing transformation algorithm as well as to the ER notation. Introducing some new concepts, we have adapted the original ER notation and developed a new transformation algorithm based on the existing one. This paper presents the modified ER notation with an ER diagram drawn based on the new notation.
Modeling The Stable Operating Envelope For Partially Stable Combustion Engines Using Class Imbalance Learning
Venue: arXiv cs.NE 2013
Year: 2013

Advanced combustion technologies such as homogeneous charge compression ignition (HCCI) engines have a narrow stable operating region defined by complex control strategies such as exhaust gas recirculation (EGR) and variable valve timing among others. For such systems, it is important to identify the operating envelope or the boundary of stable operation for diagnostics and control purposes. Obtaining a good model of the operating envelope using physics becomes intractable owing to engine transient effects. In this paper, a machine learning based approach is employed to identify the stable operating boundary of HCCI combustion directly from experimental data. Owing to imbalance in class proportions in the data, two approaches are considered. A re-sampling (under-sampling, over-sampling) based approach is used to develop models using existing algorithms while a cost-sensitive approach is used to modify the learning algorithm without modifying the data set. Support vector machines and recently developed extreme learning machines are used for model development and results compared against linear classification methods show that cost-sensitive versions of ELM and SVM algorithms are well suited to model the HCCI operating envelope. The prediction results indicate that the models have the potential to be used for predicting HCCI instability based on sensor measurement history.
Communication Steps for Parallel Query Processing
Venue: arXiv cs.DB 2013
Year: 2013

We consider the problem of computing a relational query $q$ on a large input database of size $n$, using a large number $p$ of servers. The computation is performed in rounds, and each server can receive only $O(n/p^{1-\varepsilon})$ bits of data, where $\varepsilon \in [0,1]$ is a parameter that controls replication. We examine how many global communication steps are needed to compute $q$. We establish both lower and upper bounds, in two settings. For a single round of communication, we give lower bounds in the strongest possible model, where arbitrary bits may be exchanged; we show that any algorithm requires $\varepsilon \geq 1-1/τ^*$, where $τ^*$ is the fractional vertex cover of the hypergraph of $q$. We also give an algorithm that matches the lower bound for a specific class of databases. For multiple rounds of communication, we present lower bounds in a model where routing decisions for a tuple are tuple-based. We show that for the class of tree-like queries there exists a tradeoff between the number of rounds and the space exponent $\varepsilon$. The lower bounds for multiple rounds are the first of their kind. Our results also imply that transitive closure cannot be computed in O(1) rounds of communication.
DNA Reservoir Computing: A Novel Molecular Computing Approach
Venue: arXiv cs.NE 2013
Year: 2013

We propose a novel molecular computing approach based on reservoir computing. In reservoir computing, a dynamical core, called a reservoir, is perturbed with an external input signal while a readout layer maps the reservoir dynamics to a target output. Computation takes place as a transformation from the input space to a high-dimensional spatiotemporal feature space created by the transient dynamics of the reservoir. The readout layer then combines these features to produce the target output. We show that coupled deoxyribozyme oscillators can act as the reservoir. We show that despite using only three coupled oscillators, a molecular reservoir computer could achieve 90% accuracy on a benchmark temporal problem.
A Simulator for Data-Intensive Job Scheduling
Venue: arXiv cs.DC 2013
Year: 2013

Despite the fact that size-based schedulers can give excellent results in terms of both average response times and fairness, data-intensive computing execution engines generally do not employ size-based schedulers, mainly because of the fact that job size is not known a priori. In this work, we perform a simulation-based analysis of the performance of size-based schedulers when they are employed with the workload of typical data-intensive schedules and with approximated size estimations. We show results that are very promising: even when size estimation is very imprecise, response times of size-based schedulers can be definitely smaller than those of simple scheduling techniques such as processor sharing or FIFO.
(Un)Decidability Results for Word Equations with Length and Regular Expression Constraints
Venue: arXiv cs.LO 2013
Year: 2013

We prove several decidability and undecidability results for the satisfiability and validity problems for languages that can express solutions to word equations with length constraints. The atomic formulas over this language are equality over string terms (word equations), linear inequality over the length function (length constraints), and membership in regular sets. These questions are important in logic, program analysis, and formal verification. Variants of these questions have been studied for many decades by mathematicians. More recently, practical satisfiability procedures (aka SMT solvers) for these formulas have become increasingly important in the context of security analysis for string-manipulating programs such as web applications. We prove three main theorems. First, we give a new proof of undecidability for the validity problem for the set of sentences written as a forall-exists quantifier alternation applied to positive word equations. A corollary of this undecidability result is that this set is undecidable even with sentences with at most two occurrences of a string variable. Second, we consider Boolean combinations of quantifier-free formulas constructed out of word equations and length constraints. We show that if word equations can be converted to a solved form, a form relevant in practice, then the satisfiability problem for Boolean combinations of word equations and length constraints is decidable. Third, we show that the satisfiability problem for quantifier-free formulas over word equations in regular solved form, length constraints, and the membership predicate over regular expressions is also decidable.
A maximal-information color to gray conversion method for document images: Toward an optimal grayscale representation for document image binarization
Venue: arXiv cs.CV 2013
Year: 2013

A novel method to convert color/multi-spectral images to gray-level images is introduced to increase the performance of document binarization methods. The method uses the distribution of the pixel data of the input document image in a color space to find a transformation, called the dual transform, which balances the amount of information on all color channels. Furthermore, in order to reduce the intensity variations on the gray output, a color reduction preprocessing step is applied. Then, a channel is selected as the gray value representation of the document image based on the homogeneity criterion on the text regions. In this way, the proposed method can provide a luminance-independent contrast enhancement. The performance of the method is evaluated against various images from two databases, the ICDAR'03 Robust Reading, the KAIST and the DIBCO'09 datasets, subjectively and objectively with promising results. The ground truth images for the images from the ICDAR'03 Robust Reading dataset have been created manually by the authors.
Scaling Up Robust MDPs by Reinforcement Learning
Venue: arXiv cs.LG 2013
Year: 2013

We consider large-scale Markov decision processes (MDPs) with parameter uncertainty, under the robust MDP paradigm. Previous studies showed that robust MDPs, based on a minimax approach to handle uncertainty, can be solved using dynamic programming for small to medium sized problems. However, due to the "curse of dimensionality", MDPs that model real-life problems are typically prohibitively large for such approaches. In this work we employ a reinforcement learning approach to tackle this planning problem: we develop a robust approximate dynamic programming method based on a projected fixed point equation to approximately solve large scale robust MDPs. We show that the proposed method provably succeeds under certain technical conditions, and demonstrate its effectiveness through simulation of an option pricing problem. To the best of our knowledge, this is the first attempt to scale up the robust MDPs paradigm.
Information Spectrum Approach to the Source Channel Separation Theorem
Venue: arXiv cs.IT 2013
Year: 2013

A source-channel separation theorem for a general channel has recently been shown by Aggrawal et. al. This theorem states that if there exist a coding scheme that achieves a maximum distortion level d_{max} over a general channel W, then reliable communication can be accomplished over this channel at rates less then R(d_{max}), where R(.) is the rate distortion function of the source. The source, however, is essentially constrained to be discrete and memoryless (DMS). In this work we prove a stronger claim where the source is general, satisfying only a "sphere packing optimality" feature, and the channel is completely general. Furthermore, we show that if the channel satisfies the strong converse property as define by Han & verdu, then the same statement can be made with d_{avg}, the average distortion level, replacing d_{max}. Unlike the proofs there, we use information spectrum methods to prove the statements and the results can be quite easily extended to other situations.
Metaheuristics in Flood Disaster Management and Risk Assessment
Venue: arXiv cs.AI 2013
Year: 2013

A conceptual area is divided into units or barangays, each was allowed to evolve under a physical constraint. A risk assessment method was then used to identify the flood risk in each community using the following risk factors: the area's urbanized area ratio, literacy rate, mortality rate, poverty incidence, radio/TV penetration, and state of structural and non-structural measures. Vulnerability is defined as a weighted-sum of these components. A penalty was imposed for reduced vulnerability. Optimization comparison was done with MatLab's Genetic Algorithms and Simulated Annealing; results showed 'extreme' solutions and realistic designs, for simulated annealing and genetic algorithm, respectively.
A Temporal Logic for Hyperproperties
Venue: arXiv cs.LO 2013
Year: 2013

Hyperproperties, as introduced by Clarkson and Schneider, characterize the correctness of a computer program as a condition on its set of computation paths. Standard temporal logics can only refer to a single path at a time, and therefore cannot express many hyperproperties of interest, including noninterference and other important properties in security and coding theory. In this paper, we investigate an extension of temporal logic with explicit path variables. We show that the quantification over paths naturally subsumes other extensions of temporal logic with operators for information flow and knowledge. The model checking problem for temporal logic with path quantification is decidable. For alternation depth 1, the complexity is PSPACE in the length of the formula and NLOGSPACE in the size of the system, as for linear-time temporal logic.
Millimeter Wave Beamforming for Wireless Backhaul and Access in Small Cell Networks
Venue: arXiv cs.IT 2013
Year: 2013

Recently, there has been considerable interest in new tiered network cellular architectures, which would likely use many more cell sites than found today. Two major challenges will be i) providing backhaul to all of these cells and ii) finding efficient techniques to leverage higher frequency bands for mobile access and backhaul. This paper proposes the use of outdoor millimeter wave communications for backhaul networking between cells and mobile access within a cell. To overcome the outdoor impairments found in millimeter wave propagation, this paper studies beamforming using large arrays. However, such systems will require narrow beams, increasing sensitivity to movement caused by pole sway and other environmental concerns. To overcome this, we propose an efficient beam alignment technique using adaptive subspace sampling and hierarchical beam codebooks. A wind sway analysis is presented to establish a notion of beam coherence time. This highlights a previously unexplored tradeoff between array size and wind-induced movement. Generally, it is not possible to use larger arrays without risking a corresponding performance loss from wind-induced beam misalignment. The performance of the proposed alignment technique is analyzed and compared with other search and alignment methods. The results show significant performance improvement with reduced search time.
Extended Subspace Error Localization for Rate-Adaptive Distributed Source Coding
Venue: arXiv cs.IT 2013
Year: 2013

A subspace-based approach for rate-adaptive distributed source coding (DSC) based on discrete Fourier transform (DFT) codes is developed. Punctured DFT codes can be used to implement rate-adaptive source coding, however they perform poorly after even moderate puncturing since the performance of the subspace error localization degrades severely. The proposed subspace-based error localization extends and improves the existing one, based on additional syndrome, and is naturally suitable for rate-adaptive distributed source coding architecture.
MITHYS: Mind The Hand You Shake - Protecting mobile devices from SSL usage vulnerabilities
Venue: arXiv cs.CR 2013
Year: 2013

Recent studies have shown that a significant number of mobile applications, often handling sensitive data such as bank accounts and login credentials, suffers from SSL vulnerabilities. Most of the time, these vulnerabilities are due to improper use of the SSL protocol (in particular, in its \emph{handshake} phase), resulting in applications exposed to man-in-the-middle attacks. In this paper, we present MITHYS, a system able to: (i) detect applications vulnerable to man-in-the-middle attacks, and (ii) protect them against these attacks. We demonstrate the feasibility of our proposal by means of a prototype implementation in Android, named MITHYSApp. A thorough set of experiments assesses the validity of our solution in detecting and protecting mobile applications from man-in-the-middle attacks, without introducing significant overheads. Finally, MITHYSApp does not require any special permissions nor OS modifications, as it operates at the application level. These features make MITHYSApp immediately deployable on a large user base.