OpenRaiser/Intern-Atlas huggingface dataset:
Lattice Index Coding
Venue: arXiv cs.IT 2015
Year: 2015

The index coding problem involves a sender with K messages to be transmitted across a broadcast channel, and a set of receivers each of which demands a subset of the K messages while having prior knowledge of a different subset as side information. We consider the specific case of noisy index coding where the broadcast channel is Gaussian and every receiver demands all the messages from the source. Instances of this communication problem arise in wireless relay networks, sensor networks, and retransmissions in broadcast channels. We construct 'lattice index codes' for this channel by encoding the K messages individually using K modulo lattice constellations and transmitting their sum modulo a coarse lattice. We introduce a design metric called 'side information gain' that measures the advantage of a code in utilizing the side information at the receivers, and hence its goodness as an index code. Based on the Chinese remainder theorem, we then construct lattice index codes with large side information gains using lattices over the following principal ideal domains: rational integers, Gaussian integers, Eisenstein integers, and the Hurwitz quaternions. Among all lattice index codes constructed using any densest lattice of a given dimension, our codes achieve the maximum side information gain. Finally, using an example, we illustrate how the proposed lattice index codes can benefit Gaussian broadcast channels with more general message demands.
A Van Benthem Theorem for Modal Team Semantics
Venue: arXiv cs.LO 2015
Year: 2015

The famous van Benthem theorem states that modal logic corresponds exactly to the fragment of first-order logic that is invariant under bisimulation. In this article we prove an exact analogue of this theorem in the framework of modal dependence logic MDL and team semantics. We show that modal team logic MTL, extending MDL by classical negation, captures exactly the FO-definable bisimulation invariant properties of Kripke structures and teams. We also compare the expressive power of MTL to most of the variants and extensions of MDL recently studied in the area.
The Karlskrona manifesto for sustainability design
Venue: arXiv cs.SE 2015
Year: 2015

Sustainability is a central concern for our society, and software systems increasingly play a central role in it. As designers of software technology, we cause change and are responsible for the effects of our design choices. We recognize that there is a rapidly increasing awareness of the fundamental need and desire for a more sustainable world, and there is a lot of genuine goodwill. However, this alone will be ineffective unless we come to understand and address our persistent misperceptions. The Karlskrona Manifesto for Sustainability Design aims to initiate a much needed conversation in and beyond the software community by highlighting such perceptions and proposing a set of fundamental principles for sustainability design.
Scheduling Trees of Malleable Tasks for Sparse Linear Algebra
Venue: arXiv cs.DC 2015
Year: 2015

Scientific workloads are often described as directed acyclic task graphs. In this paper, we focus on the multifrontal factorization of sparse matrices, whose task graph is structured as a tree of parallel tasks. Among the existing models for parallel tasks, the concept of malleable tasks is especially powerful as it allows each task to be processed on a time-varying number of processors. Following the model advocated by Prasanna and Musicus for matrix computations, we consider malleable tasks whose speedup is $p^α$, where $p$ is the fractional share of processors on which a task executes, and $α$ ($0 < α\leq 1$) is a parameter which does not depend on the task. We first motivate the relevance of this model for our application with actual experiments on multicore platforms. Then, we study the optimal allocation proposed by Prasanna and Musicus for makespan minimization using optimal control theory. We largely simplify their proofs by resorting only to pure scheduling arguments. Building on the insight gained thanks to these new proofs, we extend the study to distributed multicore platforms. There, a task cannot be distributed among several distributed nodes. In such a distributed setting (homogeneous or heterogeneous), we prove the NP-completeness of the corresponding scheduling problem, and propose some approximation algorithms. We finally assess the relevance of our approach by simulations on realistic trees. We show that the average performance gain of our allocations with respect to existing solutions (that are thus unaware of the actual speedup functions) is up to 16% for $α=0.9$ (the value observed in the real experiments).
Capacity Analysis of One-Bit Quantized MIMO Systems with Transmitter Channel State Information
Venue: arXiv cs.IT 2015
Year: 2015

With bandwidths on the order of a gigahertz in emerging wireless systems, high-resolution analog-to-digital convertors (ADCs) become a power consumption bottleneck. One solution is to employ low resolution one-bit ADCs. In this paper, we analyze the flat fading multiple-input multiple-output (MIMO) channel with one-bit ADCs. Channel state information is assumed to be known at both the transmitter and receiver. For the multiple-input single-output channel, we derive the exact channel capacity. For the single-input multiple-output and MIMO channel, the capacity at infinite signal-to-noise ratio (SNR) is found. We also derive upper bound at finite SNR, which is tight when the channel has full row rank. In addition, we propose an efficient method to design the input symbols to approach the capacity achieving solution. We incorporate millimeter wave channel characteristics and find the bounds on the infinite SNR capacity. The results show how the number of paths and number of receive antennas impact the capacity.
Throughput Optimization in Multi-Channel Cognitive Radios with Hard Deadline Constraints
Venue: arXiv cs.IT 2015
Year: 2015

In a cognitive radio scenario we consider a single secondary user (SU) accessing a multi-channel system. The SU senses the channels sequentially to detect if a primary user (PU) is occupying the channels, and stops its search to access a channel if it offers a significantly high throughput. The optimal stopping rule and power control problem is considered. The problem is formulated as a SU's throughput-maximization problem under a power, interference and packet delay constraints. We first show the effect of the optimal stopping rule on the packet delay, then solve this optimization problem for both the overlay system where the SU transmits only at the spectrum holes as well as the underlay system where tolerable interference (or tolerable collision probability) is allowed. We provide closed-form expressions for the optimal stopping rule, and show that the optimal power control strategy for this multi-channel problem is a modified water-filling approach. We extend the work to multiple SU scenario and show that when the number of SUs is large the complexity of the solution becomes smaller than that of the single SU case. We discuss the application of this problem in typical networks where packets arrive simultaneously and have the same departure deadline. We further propose an online adaptation policy to the optimal stopping rule that meets the packets' hard-deadline constraint and, at the same time, gives higher throughput than the offline policy.
Generalized Product of Experts for Automatic and Principled Fusion of Gaussian Process Predictions
Venue: arXiv cs.LG 2015
Year: 2015

In this work, we propose a generalized product of experts (gPoE) framework for combining the predictions of multiple probabilistic models. We identify four desirable properties that are important for scalability, expressiveness and robustness, when learning and inferring with a combination of multiple models. Through analysis and experiments, we show that gPoE of Gaussian processes (GP) have these qualities, while no other existing combination schemes satisfy all of them at the same time. The resulting GP-gPoE is highly scalable as individual GP experts can be independently learned in parallel; very expressive as the way experts are combined depends on the input rather than fixed; the combined prediction is still a valid probabilistic model with natural interpretation; and finally robust to unreliable predictions from individual experts.
Approximate Safety Verification and Control of Partially Observable Stochastic Hybrid Systems
Venue: arXiv cs.SY 2015
Year: 2015

Assuring safety in discrete time stochastic hybrid systems is particularly difficult when only noisy or incomplete observations of the state are available. We first review a formulation of the probabilistic safety problem under noisy hybrid observations as a dynamic program over an equivalent information state. Two methods for approximately solving the dynamic program are presented. The first method approximates the hybrid system as an equivalent finite state Markov decision process, so that the information state is a probability mass function. The second approach approximates an indicator function over the safe region using radial basis functions, to represent the information state as a Gaussian mixture. In both cases, we discretize the hybrid observation process and generate a sampled set of information states, then use point-based value iteration to under-approximate the safety probability and synthesize a suboptimal control policy. We obtain error bounds and convergence results in both cases, assuming switched affine dynamics and additive Gaussian noise on the continuous states and observations. We compare the performance of the finite state and Gaussian mixture approaches on a simple numerical example.
Almost Cover-Free Codes and Designs
Venue: arXiv cs.IT 2015
Year: 2015

An $s$-subset of codewords of a binary code $X$ is said to be an {\em $(s,\ell)$-bad} in $X$ if the code $X$ contains a subset of other $\ell$ codewords such that the conjunction of the $\ell$ codewords is covered by the disjunctive sum of the $s$ codewords. Otherwise, the $s$-subset of codewords of $X$ is said to be an {\em $(s,\ell)$-good} in~$X$.mA binary code $X$ is said to be a cover-free $(s,\ell)$-code if the code $X$ does not contain $(s,\ell)$-bad subsets. In this paper, we introduce a natural {\em probabilistic} generalization of cover-free $(s,\ell)$-codes, namely: a binary code is said to be an almost cover-free $(s,\ell)$-code if {\em almost all} $s$-subsets of its codewords are $(s,\ell)$-good. We discuss the concept of almost cover-free $(s,\ell)$-codes arising in combinatorial group testing problems connected with the nonadaptive search of defective supersets (complexes). We develop a random coding method based on the ensemble of binary constant weight codes to obtain lower bounds on the capacity of such codes.
On the read-once property of branching programs and CNFs of bounded treewidth
Venue: arXiv cs.CC 2015
Year: 2015

In this paper we prove a space lower bound of $n^{Ω(k)}$ for non-deterministic (syntactic) read-once branching programs ({\sc nrobp}s) on functions expressible as {\sc cnf}s with treewidth at most $k$ of their primal graphs. This lower bound rules out the possibility of fixed-parameter space complexity of {\sc nrobp}s parameterized by $k$. We use lower bound for {\sc nrobp}s to obtain a quasi-polynomial separation between Free Binary Decision Diagrams and Decision Decomposable Negation Normal Forms, essentially matching the existing upper bound introduced by Beame et al. and thus proving the tightness of the latter.
Approximate Counting in SMT and Value Estimation for Probabilistic Programs
Venue: arXiv cs.LO 2015
Year: 2015

#SMT, or model counting for logical theories, is a well-known hard problem that generalizes such tasks as counting the number of satisfying assignments to a Boolean formula and computing the volume of a polytope. In the realm of satisfiability modulo theories (SMT) there is a growing need for model counting solvers, coming from several application domains (quantitative information flow, static analysis of probabilistic programs). In this paper, we show a reduction from an approximate version of #SMT to SMT. We focus on the theories of integer arithmetic and linear real arithmetic. We propose model counting algorithms that provide approximate solutions with formal bounds on the approximation error. They run in polynomial time and make a polynomial number of queries to the SMT solver for the underlying theory, exploiting "for free" the sophisticated heuristics implemented within modern SMT solvers. We have implemented the algorithms and used them to solve the value problem for a model of loop-free probabilistic programs with nondeterminism.
On the push&pull protocol for rumour spreading
Venue: arXiv cs.DC 2015
Year: 2015

The asynchronous push&pull protocol, a randomized distributed algorithm for spreading a rumour in a graph $G$, works as follows. Independent Poisson clocks of rate 1 are associated with the vertices of $G$. Initially, one vertex of $G$ knows the rumour. Whenever the clock of a vertex $x$ rings, it calls a random neighbour $y$: if $x$ knows the rumour and $y$ does not, then $x$ tells $y$ the rumour (a push operation), and if $x$ does not know the rumour and $y$ knows it, $y$ tells $x$ the rumour (a pull operation). The average spread time of $G$ is the expected time it takes for all vertices to know the rumour, and the guaranteed spread time of $G$ is the smallest time $t$ such that with probability at least $1-1/n$, after time $t$ all vertices know the rumour. The synchronous variant of this protocol, in which each clock rings precisely at times $1,2,\dots$, has been studied extensively. We prove the following results for any $n$-vertex graph: In either version, the average spread time is at most linear even if only the pull operation is used, and the guaranteed spread time is within a logarithmic factor of the average spread time, so it is $O(n\log n)$. In the asynchronous version, both the average and guaranteed spread times are $Ω(\log n)$. We give examples of graphs illustrating that these bounds are best possible up to constant factors. We also prove theoretical relationships between the guaranteed spread times in the two versions. Firstly, in all graphs the guaranteed spread time in the asynchronous version is within an $O(\log n)$ factor of that in the synchronous version, and this is tight. Next, we find examples of graphs whose asynchronous spread times are logarithmic, but the synchronous versions are polynomially large. Finally, we show for any graph that the ratio of the synchronous spread time to the asynchronous spread time is $O(n^{2/3})$.
Modeling Transitivity in Complex Networks
Venue: arXiv cs.SI 2015
Year: 2015

An important source of high clustering coefficient in real-world networks is transitivity. However, existing approaches for modeling transitivity suffer from at least one of the following problems: i) they produce graphs from a specific class like bipartite graphs, ii) they do not give an analytical argument for the high clustering coefficient of the model, and iii) their clustering coefficient is still significantly lower than real-world networks. In this paper, we propose a new model for complex networks which is based on adding transitivity to scale-free models. We theoretically analyze the model and provide analytical arguments for its different properties. In particular, we calculate a lower bound on the clustering coefficient of the model which is independent of the network size, as seen in real-world networks. More than theoretical analysis, the main properties of the model are evaluated empirically and it is shown that the model can precisely simulate real-world networks from different domains with and different specifications.
Reservoir computing with a single time-delay autonomous Boolean node
Venue: arXiv cs.ET 2015
Year: 2015

We demonstrate reservoir computing with a physical system using a single autonomous Boolean logic element with time-delay feedback. The system generates a chaotic transient with a window of consistency lasting between 30 and 300 ns, which we show is sufficient for reservoir computing. We then characterize the dependence of computational performance on system parameters to find the best operating point of the reservoir. When the best parameters are chosen, the reservoir is able to classify short input patterns with performance that decreases over time. In particular, we show that four distinct input patterns can be classified for 70 ns, even though the inputs are only provided to the reservoir for 7.5 ns.
Julia: A Fresh Approach to Numerical Computing
Venue: arXiv cs.MS 2015
Year: 2015

Bridging cultures that have often been distant, Julia combines expertise from the diverse fields of computer science and computational science to create a new approach to numerical computing. Julia is designed to be easy and fast. Julia questions notions generally held as "laws of nature" by practitioners of numerical computing: 1. High-level dynamic programs have to be slow. 2. One must prototype in one language and then rewrite in another language for speed or deployment, and 3. There are parts of a system for the programmer, and other parts best left untouched as they are built by the experts. We introduce the Julia programming language and its design --- a dance between specialization and abstraction. Specialization allows for custom treatment. Multiple dispatch, a technique from computer science, picks the right algorithm for the right circumstance. Abstraction, what good computation is really about, recognizes what remains the same after differences are stripped away. Abstractions in mathematics are captured as code through another technique from computer science, generic programming. Julia shows that one can have machine performance without sacrificing human convenience.
Checkpointing as a Service in Heterogeneous Cloud Environments
Venue: arXiv cs.DC 2015
Year: 2015

A non-invasive, cloud-agnostic approach is demonstrated for extending existing cloud platforms to include checkpoint-restart capability. Most cloud platforms currently rely on each application to provide its own fault tolerance. A uniform mechanism within the cloud itself serves two purposes: (a) direct support for long-running jobs, which would otherwise require a custom fault-tolerant mechanism for each application; and (b) the administrative capability to manage an over-subscribed cloud by temporarily swapping out jobs when higher priority jobs arrive. An advantage of this uniform approach is that it also supports parallel and distributed computations, over both TCP and InfiniBand, thus allowing traditional HPC applications to take advantage of an existing cloud infrastructure. Additionally, an integrated health-monitoring mechanism detects when long-running jobs either fail or incur exceptionally low performance, perhaps due to resource starvation, and proactively suspends the job. The cloud-agnostic feature is demonstrated by applying the implementation to two very different cloud platforms: Snooze and OpenStack. The use of a cloud-agnostic architecture also enables, for the first time, migration of applications from one cloud platform to another.
Algorithmic Energy Saving for Parallel Cholesky, LU, and QR Factorizations
Venue: arXiv cs.DC 2015
Year: 2015

The pressing demands of improving energy efficiency for high performance scientific computing have motivated a large body of software-controlled hard- ware solutions using Dynamic Voltage and Frequency Scaling (DVFS) that strategically switch processors to low-power states, when the peak processor performance is not necessary. Although OS level solutions have demonstrated the effectiveness of saving energy in a black-box fashion, for applications with variable execution characteristics, the optimal energy efficiency can be blundered away due to defective prediction mechanism and untapped load imbalance. In this paper, we propose TX, a library level race-to-halt DVFS scheduling approach that analyzes Task Dependency Set of each task in parallel Cholesky, LU, and QR factorizations to achieve substantial energy savings OS level solutions cannot fulfill. Partially giving up the generality of OS level solutions per requiring library level source modification, TX lever- ages algorithmic characteristics of the applications to gain greater energy savings. Experimental results on two power-aware clusters indicate that TX can save up to 17.8% more energy than state-of-the-art OS level solutions with negligible 3.5% on average performance loss.
Interference and SINR coverage in spatial non-slotted Aloha networks
Venue: arXiv cs.NI 2015
Year: 2015

In this paper we propose two analytically tractable stochastic-geometric models of interference in ad-hoc networks using pure (non-slotted) Aloha as the medium access. In contrast the slotted model, the interference in pure Aloha may vary during the transmission of a tagged packet. We develop closed form expressions for the Laplace transform of the empirical average of the interference experienced during the transmission of a typical packet. Both models assume a power-law path-loss function with arbitrarily distributed fading and feature configurations of transmitters randomly located in the Euclidean plane according to a Poisson point process. Depending on the model, these configurations vary over time or are static. We apply our analysis of the interference to study the Signal-to-Interference-and-Noise Ratio (SINR) outage probability for a typical transmission in pure Aloha. The results are used to compare the performance of non-slotted Aloha to the slotted one, which has almost exclusively been previously studied in the same context of mobile ad-hoc networks.
Second Workshop on Sustainable Software for Science: Practice and Experiences (WSSSPE2): Submission, Peer-Review and Sorting Process, and Results
Venue: arXiv cs.SE 2015
Year: 2015

This technical report discusses the submission and peer-review process used by the Second Workshop on Sustainable Software for Science: Practice and Experiences (WSSSPE2) and the results of that process. It is intended to record both the alternative submission and program organization model used by WSSSPE2 as well as the papers associated with the workshop that resulted from that process.
Derandomized Graph Product Results using the Low Degree Long Code
Venue: arXiv cs.CC 2015
Year: 2015

In this paper, we address the question of whether the recent derandomization results obtained by the use of the low-degree long code can be extended to other product settings. We consider two settings: (1) the graph product results of Alon, Dinur, Friedgut and Sudakov [GAFA, 2004] and (2) the "majority is stablest" type of result obtained by Dinur, Mossel and Regev [SICOMP, 2009] and Dinur and Shinkar [In Proc. APPROX, 2010] while studying the hardness of approximate graph coloring. In our first result, we show that there exists a considerably smaller subgraph of $K_3^{\otimes R}$ which exhibits the following property (shown for $K_3^{\otimes R}$ by Alon et al.): independent sets close in size to the maximum independent set are well approximated by dictators. The "majority is stablest" type of result of Dinur et al. and Dinur and Shinkar shows that if there exist two sets of vertices $A$ and $B$ in $K_3^{\otimes R}$ with very few edges with one endpoint in $A$ and another in $B$, then it must be the case that the two sets $A$ and $B$ share a single influential coordinate. In our second result, we show that a similar "majority is stablest" statement holds good for a considerably smaller subgraph of $K_3^{\otimes R}$. Furthermore using this result, we give a more efficient reduction from Unique Games to the graph coloring problem, leading to improved hardness of approximation results for coloring.