OpenRaiser/Intern-Atlas huggingface dataset:
NOMA: An Information Theoretic Perspective
Venue: arXiv cs.IT 2015
Year: 2015

In this letter, the performance of non-orthogonal multiple access (NOMA) is investigated from an information theoretic perspective. The relationships among the capacity region of broadcast channels and two rate regions achieved by NOMA and time-division multiple access (TDMA) are illustrated first. Then, the performance of NOMA is evaluated by considering TDMA as the benchmark, where both the sum rate and the individual user rates are used as the criteria. In a wireless downlink scenario with user pairing, the developed analytical results show that NOMA can outperform TDMA not only for the sum rate but also for each user's individual rate, particularly when the difference between the users' channels is large.
Luzzu Quality Metric Language -- A DSL for Linked Data Quality Assessment
Venue: arXiv cs.DB 2015
Year: 2015

The steadily growing number of linked open datasets brought about a number of reservations amongst data consumers with regard to the datasets' quality. Quality assessment requires significant effort and consideration, including the definition of data quality metrics and a process to assess datasets based on these definitions. Luzzu is a quality assessment framework for linked data that allows domain-specific metrics to be plugged in. LQML offers notations, abstractions and expressive power, focusing on the representation of quality metrics. It provides expressive power for defining sophisticated quality metrics. Its integration with Luzzu enables their efficient processing and execution and thus the comprehensive assessment of extremely large datasets in a streaming way. We also describe a novel ontology that enables the reuse, sharing and querying of such definitions. Finally, we evaluate the proposed DSL against the cognitive dimensions of notation framework.
Planning for Optimal Feedback Control in the Volume of Free Space
Venue: arXiv cs.RO 2015
Year: 2015

The problem of optimal feedback planning among obstacles in d-dimensional configuration spaces is considered. We present a sampling-based, asymptotically optimal feedback planning method. Our method combines an incremental construction of the Delaunay triangulation, volumetric collision-detection module, and a modified Fast Marching Method to compute a converging sequence of feedback functions. The convergence and asymptotic runtime are proven theoretically and investigated during numerical experiments, in which the proposed method is compared with the state-of-the-art asymptotically optimal path planners. The results show that our method is competitive with the previous algorithms. Unlike the shortest trajectory computed by many path planning algorithms, the resulting feedback functions can be used directly for robot navigation in our case. Finally, we present a straightforward extension of our method that handles dynamic environments where obstacles can appear, disappear, or move.
Differential Calculus on Cayley Graphs
Venue: arXiv cs.DM 2015
Year: 2015

We conservatively extend classical elementary differential calculus to the Cartesian closed category of convergence spaces. By specializing results about the convergence space representation of directed graphs, we use Cayley graphs to obtain a differential calculus on groups, from which we then extract a Boolean differential calculus, in which both linearity and the product rule, also called the Leibniz identity, are satisfied.
The Dual and the Gray Image of Codes over $\mathbb{F}_{q}+v\mathbb{F}_{q}+v^{2}\mathbb{F}_{q}$
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we study the linear codes over the commutative ring $R=\F_{q}+v\F_{q}+v^{2}\F_{q}$ and their Gray images, where $v^{3}=v$. We define the Lee weight of the elements of $R$, we give a Gray map from $R^{n}$ to $\F^{3n}_{q}$ and we give the relation between the dual and the Gray image of a code. This allows us to investigate the structure and properties of self-dual cyclic, formally self-dual and the Gray image of formally self-dual codes over $R$. Further, we give several constructions of formally self-dual codes over $R
TreatJS: Higher-Order Contracts for JavaScript
Venue: arXiv cs.PL 2015
Year: 2015

TreatJS is a language embedded, higher-order contract system for JavaScript which enforces contracts by run-time monitoring. Beyond providing the standard abstractions for building higher-order contracts (base, function, and object contracts), TreatJS's novel contributions are its guarantee of non-interfering contract execution, its systematic approach to blame assignment, its support for contracts in the style of union and intersection types, and its notion of a parameterized contract scope, which is the building block for composable run-time generated contracts that generalize dependent function contracts. TreatJS is implemented as a library so that all aspects of a contract can be specified using the full JavaScript language. The library relies on JavaScript proxies to guarantee full interposition for contracts. It further exploits JavaScript's reflective features to run contracts in a sandbox environment, which guarantees that the execution of contract code does not modify the application state. No source code transformation or change in the JavaScript run-time system is required. The impact of contracts on execution speed is evaluated using the Google Octane benchmark.
Online survey for collective clustering of computer generated architectural floor plans
Venue: arXiv cs.HC 2015
Year: 2015

The aim of this study is to understand what are the collective actions of architecture practitioners when grouping floor plan designs. The understanding of how professionals and students solve this complex problem may help to develop specific programmes for the teaching of architecture. In addition, the findings of this study can help in the development of query mechanisms for database retrieval of floor plans and the implementation of clustering mechanisms to aggregate floor plans resulting from generative design methods. The study aims to capture how practitioners define similarity between floor plans from a pool of available designs. A hybrid evolutionary strategy is used, which takes into account the building's functional program to generate alternative floor plan designs. The first step of this methodology consisted in an online survey to gather information on how the respondents would perform a clustering task. Online surveys have been used in several applications and are a method of data collection that conveys several advantages. When properly developed and implemented, a survey portrays the characteristics of large groups of respondents on a specific topic and allows assessing its representation. Several types of surveys are available; e.g. questionnaire and interview formats, phone survey, and online surveys, which can be coupled with inference engines that act and direct the survey according to respondents' answers. In the present study, the survey was posed as an online exercise in which respondents had to perform a pre-defined task, which makes it similar to running an experiment in an online environment. The experiment aimed to understand the perception and criteria of the target population to perform the clustering task by comparing the results with the respondents' answers to a questionnaire presented at the end of the exercise.
On the Required Number of Antennas in a Point-to-Point Large-but-Finite MIMO System: Outage-Limited Scenario
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates the performance of the point-to-point multiple-input-multiple-output (MIMO) systems in the presence of a large but finite numbers of antennas at the transmitters and/or receivers. Considering the cases with and without hybrid automatic repeat request (HARQ) feedback, we determine the minimum numbers of the transmit/receive antennas which are required to satisfy different outage probability constraints. Our results are obtained for different fading conditions and the effect of the power amplifiers efficiency on the performance of the MIMO-HARQ systems is analyzed. Moreover, we derive closed-form expressions for the asymptotic performance of the MIMO-HARQ systems when the number of antennas increases. Our analytical and numerical results show that different outage requirements can be satisfied with relatively few transmit/receive antennas.
A shortcut to (sun)flowers: Kernels in logarithmic space or linear time
Venue: arXiv cs.DS 2015
Year: 2015

We investigate whether kernelization results can be obtained if we restrict kernelization algorithms to run in logarithmic space. This restriction for kernelization is motivated by the question of what results are attainable for preprocessing via simple and/or local reduction rules. We find kernelizations for d-Hitting Set(k), d-Set Packing(k), Edge Dominating Set(k) and a number of hitting and packing problems in graphs, each running in logspace. Additionally, we return to the question of linear-time kernelization. For d-Hitting Set(k) a linear-time kernelization was given by van Bevern [Algorithmica (2014)]. We give a simpler procedure and save a large constant factor in the size bound. Furthermore, we show that we can obtain a linear-time kernel for d-Set Packing(k) as well.
Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm
Venue: arXiv cs.DS 2015
Year: 2015

The minimum-cost flow (MCF) problem is a fundamental optimization problem with many applications and seems to be well understood. Over the last half century many algorithms have been developed to solve the MCF problem and these algorithms have varying worst-case bounds on their running time. However, these worst-case bounds are not always a good indication of the algorithms' performance in practice. The Network Simplex (NS) algorithm needs an exponential number of iterations for some instances, but it is considered the best algorithm in practice and performs best in experimental studies. On the other hand, the Minimum-Mean Cycle Canceling (MMCC) algorithm is strongly polynomial, but performs badly in experimental studies. To explain these differences in performance in practice we apply the framework of smoothed analysis. We show an upper bound of $O(mn^2\log(n)\log(ϕ))$ for the number of iterations of the MMCC algorithm. Here $n$ is the number of nodes, $m$ is the number of edges, and $ϕ$ is a parameter limiting the degree to which the edge costs are perturbed. We also show a lower bound of $Ω(m\log(ϕ))$ for the number of iterations of the MMCC algorithm, which can be strengthened to $Ω(mn)$ when $ϕ=Θ(n^2)$. For the number of iterations of the NS algorithm we show a smoothed lower bound of $Ω(m \cdot \min \{ n, ϕ\} \cdot ϕ)$.
Comparative Analysis of Classic Garbage-Collection Algorithms for a Lisp-like Language
Venue: arXiv cs.PL 2015
Year: 2015

In this paper, we demonstrate the effectiveness of Cheney's Copy Algorithm for a Lisp-like system and experimentally show the infeasability of developing an optimal garbage collector for general use. We summarize and compare several garbage-collection algorithms including Cheney's Algorithm, the canonical Mark and Sweep Algorithm, and Knuth's Classical Lisp 2 Algorithm. We implement and analyze these three algorithms in the context of a custom MicroLisp environment. We conclude and present the core considerations behind the development of a garbage collector---specifically for Lisp---and make an attempt to investigate these issues in depth. We also discuss experimental results that imply the effectiveness of Cheney's algorithm over Mark-Sweep for Lisp-like languages.
Compositional Distributional Semantics with Compact Closed Categories and Frobenius Algebras
Venue: arXiv cs.CL 2015
Year: 2015

This thesis contributes to ongoing research related to the categorical compositional model for natural language of Coecke, Sadrzadeh and Clark in three ways: Firstly, I propose a concrete instantiation of the abstract framework based on Frobenius algebras (joint work with Sadrzadeh). The theory improves shortcomings of previous proposals, extends the coverage of the language, and is supported by experimental work that improves existing results. The proposed framework describes a new class of compositional models that find intuitive interpretations for a number of linguistic phenomena. Secondly, I propose and evaluate in practice a new compositional methodology which explicitly deals with the different levels of lexical ambiguity (joint work with Pulman). A concrete algorithm is presented, based on the separation of vector disambiguation from composition in an explicit prior step. Extensive experimental work shows that the proposed methodology indeed results in more accurate composite representations for the framework of Coecke et al. in particular and every other class of compositional models in general. As a last contribution, I formalize the explicit treatment of lexical ambiguity in the context of the categorical framework by resorting to categorical quantum mechanics (joint work with Coecke). In the proposed extension, the concept of a distributional vector is replaced with that of a density matrix, which compactly represents a probability distribution over the potential different meanings of the specific word. Composition takes the form of quantum measurements, leading to interesting analogies between quantum physics and linguistics.
An Algorithmic Framework for Labeling Network Maps
Venue: arXiv cs.CG 2015
Year: 2015

Drawing network maps automatically comprises two challenging steps, namely laying out the map and placing non-overlapping labels. In this paper we tackle the problem of labeling an already existing network map considering the application of metro maps. We present a flexible and versatile labeling model. Despite its simplicity, we prove that it is NP-complete to label a single line of the network. For a restricted variant of that model, we then introduce an efficient algorithm that optimally labels a single line with respect to a given weighting function. Based on that algorithm, we present a general and sophisticated workflow for multiple metro lines, which is experimentally evaluated on real-world metro maps.
Molecular Communications with Longitudinal Carrier Waves: Baseband to Passband Modulation
Venue: arXiv cs.ET 2015
Year: 2015

Traditional molecular communications via diffusion (MCvD) systems have used baseband modulation techniques by varying properties of molecular pulses such as the amplitude, the frequency of the transversal wave of the pulse, and the time delay between subsequent pulses. In this letter, we propose and implement passband modulation with molecules that exhibit longitudinal carrier wave properties. This is achieved through the oscillation of the transmitter. Frequency division multiplexing is employed to allow different molecular information streams to co-exist in the same space and time channel, creating an effective bandwidth for MCvD.
Discussion of various models related to cloud performance
Venue: arXiv cs.DC 2015
Year: 2015

This paper discusses the various models related to cloud computing. Knowing the metrics related to infrastructure is very critical to enhance the performance of cloud services. Various metrics related to clouds such as pageview response time, admission control and enforcing elasticity to cloud infrastructure are very crucial in analyzing the characteristics of the cloud to enhance the cloud performance.
Generating Primes Using Partitions
Venue: arXiv cs.CR 2015
Year: 2015

This paper presents a new technique of generating large prime numbers using a smaller one by employing Goldbach partitions. Experiments are presented showing how this method produces candidate prime numbers that are subsequently tested using either Miller Rabin or AKS primality tests.
Achievable Rates of Multi-User Millimeter Wave Systems with Hybrid Precoding
Venue: arXiv cs.IT 2015
Year: 2015

Millimeter wave (mmWave) systems will likely employ large antenna arrays at both the transmitters and receivers. A natural application of antenna arrays is simultaneous transmission to multiple users, which requires multi-user precoding at the transmitter. Hardware constraints, however, make it difficult to apply conventional lower frequency MIMO precoding techniques at mmWave. This paper proposes and analyzes a low complexity hybrid analog/digital beamforming algorithm for downlink multi-user mmWave systems. Hybrid precoding involves a combination of analog and digital processing that is motivated by the requirement to reduce the power consumption of the complete radio frequency and mixed signal hardware. The proposed algorithm configures hybrid precoders at the transmitter and analog combiners at multiple receivers with a small training and feedback overhead. For this algorithm, we derive a lower bound on the achievable rate for the case of single-path channels, show its asymptotic optimality at large numbers of antennas, and make useful insights for more general cases. Simulation results show that the proposed algorithm offers higher sum rates compared with analog-only beamforming, and approaches the performance of the unconstrained digital precoding solutions.
Combining Existential Rules and Description Logics (Extended Version)
Venue: arXiv cs.DB 2015
Year: 2015

Query answering under existential rules -- implications with existential quantifiers in the head -- is known to be decidable when imposing restrictions on the rule bodies such as frontier-guardedness [BLM10, BLMS11]. Query answering is also decidable for description logics [Baa03], which further allow disjunction and functionality constraints (assert that certain relations are functions), however, they are focused on ER-type schemas, where relations have arity two. This work investigates how to get the best of both worlds: having decidable existential rules on arbitrary arity relations, while allowing rich description logics, including functionality constraints, on arity-two relations. We first show negative results on combining such decidable languages. Second, we introduce an expressive set of existential rules (frontier-one rules with a certain restriction) which can be combined with powerful constraints on arity-two relations (e.g. GC 2, ALCQIb) while retaining decidable query answering. Further, we provide conditions to add functionality constraints on the higher-arity relations.
Fireflies: New software for interactively exploring dynamical systems using GPU computing
Venue: arXiv cs.MS 2015
Year: 2015

In non-linear systems, where explicit analytic solutions usually can't be found, visualisation is a powerful approach which can give insights into the dynamical behaviour of models; it is also crucial for teaching this area of mathematics. In this paper we present new software, Fireflies, which exploits the power of graphical processing unit (GPU) computing to produce spectacular interactive visualisations of arbitrary systems of ordinary differential equations. In contrast to typical phase portraits, Fireflies draws the current position of trajectories (projected onto 2D or 3D space) as single points of light, which move as the system is simulated. Due to the massively parallel nature of GPU hardware, Fireflies is able to simulate millions of trajectories in parallel (even on standard desktop computer hardware), producing "swarms" of particles that move around the screen in real-time according to the equations of the system. Particles that move forwards in time reveal stable attractors (e.g. fixed points and limit cycles), while the option of integrating another group of trajectories backwards in time can reveal unstable objects (repellers). Fireflies allows the user to change the parameters of the system as it is running, in order to see the effect that they have on the dynamics and to observe bifurcations. We demonstrate the capabilities of the software with three examples: a two-dimensional "mean field" model of neuronal activity, the classical Lorenz system, and a 15-dimensional model of three interacting biologically realistic neurons.
Tracking Many Solution Paths of a Polynomial Homotopy on a Graphics Processing Unit
Venue: arXiv cs.MS 2015
Year: 2015

Polynomial systems occur in many areas of science and engineering. Unlike general nonlinear systems, the algebraic structure enables to compute all solutions of a polynomial system. We describe our massive parallel predictor-corrector algorithms to track many solution paths of a polynomial homotopy. The data parallelism that provides the speedups stems from the evaluation and differentiation of the monomials in the same polynomial system at different data points, which are the points on the solution paths. Polynomial homotopies that have tens of thousands of solution paths can keep a sufficiently large amount of threads occupied. Our accelerated code combines the reverse mode of algorithmic differentiation with double double and quad double precision to compute more accurate results faster.
High-Dimensional CSI Acquisition in Massive MIMO: Sparsity-Inspired Approaches
Venue: arXiv cs.IT 2015
Year: 2015

Massive MIMO has been regarded as one of the key technologies for 5G wireless networks, as it can significantly improve both the spectral efficiency and energy efficiency. The availability of high-dimensional channel side information (CSI) is critical for its promised performance gains, but the overhead of acquiring CSI may potentially deplete the available radio resources. Fortunately, it has recently been discovered that harnessing various sparsity structures in massive MIMO channels can lead to significant overhead reduction, and thus improve the system performance. This paper presents and discusses the use of sparsity-inspired CSI acquisition techniques for massive MIMO, as well as the underlying mathematical theory. Sparsity-inspired approaches for both frequency-division duplexing and time-division duplexing massive MIMO systems will be examined and compared from an overall system perspective, including the design trade-offs between the two duplexing modes, computational complexity of acquisition algorithms, and applicability of sparsity structures. Meanwhile, some future prospects for research on high-dimensional CSI acquisition to meet practical demands will be identified.
Opportunistic Spectrum Allocation for Max-Min Rate in NC-OFDMA
Venue: arXiv cs.NI 2015
Year: 2015

We envision a scenario of opportunistic spectrum access among multiple links when the available spectrum is not contiguous due to the presence of external interference sources. Non-contiguous Orthogonal Frequency Division Multiplexing (NC-OFDM) is a promising technique to utilize such disjoint frequency bands in an efficient manner. In this paper we study the problem of fair spectrum allocation across multiple NCOFDM-enabled point-to-point cognitive radio links under certain practical considerations that arise from such non-contiguous access. When using NC-OFDMA, the channels allocated to a cognitive link are spread across several disjoint frequency bands leading to a large spectral span for that link. Increased spectral span requires higher sampling rates, leading to increased power consumption in the ADC/DAC of the transmit/receive nodes. In this context, this paper proposes a spectrum allocation that maximizes the minimum rate achieved by the cognitive radio links, under a constraint on the maximum permissible spectral span. Under constant transmit powers and orthogonal spectrum allocation, such an optimization is a mixed-integer linear program and can be solved efficiently. There exists a clear trade-off between the max-min rate achieved and the maximum permissible spectral span. The spectral allocation obtained from the proposed optimization framework is shown to be close to the tradeoff boundary, thus showing the effectiveness of the proposed technique. We find that it is possible to limit the spectrum span without incurring a significant penalty on the max-min rate under different interference environments. We also discuss an experimental evaluation of the techniques developed here using the Universal Software Radio Peripheral (USRP) enabled ORBIT radio network testbed.