OpenRaiser/Intern-Atlas huggingface dataset:
ARQ with Adaptive Feedback for Energy Harvesting Receivers
Venue: arXiv cs.IT 2016
Year: 2016

Automatic repeat request (ARQ) is widely used in modern communication systems to improve transmission reliability. In conventional ARQ protocols developed for systems with energy-unconstrained receivers, an acknowledgement/negative-acknowledgement (ACK/NACK) message is fed back when decoding succeeds/fails. Such kind of non-adaptive feedback consumes significant amount of energy, and thus will limit the performance of systems with energy harvesting (EH) receivers. In order to overcome this limitation and to utilize the harvested energy more efficiently, we propose a novel ARQ protocol for EH receivers, where the ACK feedback can be adapted based upon the receiver's EH state. Two conventional ARQ protocols are also considered. By adopting the packet drop probability (PDP) as the performance metric, we formulate the throughput constrained PDP minimization problem for a communication link with a non-EH transmitter and an EH receiver. Optimal reception policies including the sampling, decoding and feedback strategies, are developed for different ARQ protocols. Simulation results will show that the proposed ARQ protocol not only outperforms the conventional ARQs in terms of PDP, but can also achieve a higher throughput.
Tangles and Connectivity in Graphs
Venue: arXiv cs.DM 2016
Year: 2016

This paper is a short introduction to the theory of tangles, both in graphs and general connectivity systems. An emphasis is put on the correspondence between tangles of order k and k-connected components. In particular, we prove that there is a one-to-one correspondence between the triconnected components of a graph and its tangles of order 3.
Preference Elicitation in Matching Markets via Interviews: A Study of Offline Benchmarks
Venue: arXiv cs.GT 2016
Year: 2016

The stable marriage problem and its extensions have been extensively studied, with much of the work in the literature assuming that agents fully know their own preferences over alternatives. This assumption however is not always practical (especially in large markets) and agents usually need to go through some costly deliberation process in order to learn their preferences. In this paper we assume that such deliberations are carried out via interviews, where an interview involves a man and a woman, each of whom learns information about the other as a consequence. If everybody interviews everyone else, then clearly agents can fully learn their preferences. But interviews are costly, and we may wish to minimize their use. It is often the case, especially in practical settings, that due to correlation between agents' preferences, it is unnecessary for all potential interviews to be carried out in order to obtain a stable matching. Thus the problem is to find a good strategy for interviews to be carried out in order to minimize their use, whilst leading to a stable matching. One way to evaluate the performance of an interview strategy is to compare it against a naive algorithm that conducts all interviews. We argue however that a more meaningful comparison would be against an optimal offline algorithm that has access to agents' preference orderings under complete information. We show that, unless P=NP, no offline algorithm can compute the optimal interview strategy in polynomial time. If we are additionally aiming for a particular stable matching (perhaps one with certain desirable properties), we provide restricted settings under which efficient optimal offline algorithms exist.
Information Diffusion of Topic Propagation in Social Media
Venue: arXiv cs.SI 2016
Year: 2016

Real-world social and/or operational networks consist of agents with associated states, whose connectivity forms complex topologies. This complexity is further compounded by interconnected information layers, consisting, for instance, documents/resources of the agents which mutually share topical similarities. Our goal in this work is to predict the specific states of the agents, as their observed resources evolve in time and get updated. The information diffusion among the agents and the publications themselves effectively result in a dynamic process which we capture by an interconnected system of networks (i.e. layered). More specifically, we use a notion of a supra-Laplacian matrix to address such a generalized diffusion of an interconnected network starting with the classical "graph Laplacian". The auxiliary and external input update is modeled by a multidimensional Brownian process, yielding two contributions to the variations in the states of the agents: one that is due to the intrinsic interactions in the network system, and the other due to the external inputs or innovations. A variation on this theme, a priori knowledge of a fraction of the agents' states is shown to lead to a Kalman predictor problem. This helps us refine the predicted states exploiting the error in estimating the states of agents. Three real-world datasets are used to evaluate and validate the information diffusion process in this novel layered network approach. Our results demonstrate a lower prediction error when using the interconnected network rather than the single connectivity layer between the agents. The prediction error is further improved by using the estimated diffusion connection and by applying the Kalman approach with partial observations.
A Stochastic Performance Model for Pipelined Krylov Methods
Venue: arXiv cs.DC 2016
Year: 2016

Pipelined Krylov methods seek to ameliorate the latency due to inner products necessary for projection by overlapping it with the computation associated with sparse matrix-vector multiplication. We clarify a folk theorem that this can only result in a speedup of $2\times$ over the naive implementation. Examining many repeated runs, we show that stochastic noise also contributes to the latency, and we model this using an analytical probability distribution. Our analysis shows that speedups greater than $2\times$ are possible with these algorithms.
Universal Systems of Oblivious Mobile Robots
Venue: arXiv cs.DC 2016
Year: 2016

An oblivious mobile robot is a stateless computational entity located in a spatial universe, capable of moving in that universe. When activated, the robot observes the universe and the location of the other robots, chooses a destination, and moves there. The computation of the destination is made by executing an algorithm, the same for all robots, whose sole input is the current observation. No memory of all these actions is retained after the move. When the universe is a graph, distributed computations by oblivious mobile robots have been intensively studied focusing on the conditions for feasibility of basic problems (e.g., gathering, exploration) in specific classes of graphs under different schedulers. In this paper, we embark on a different, more general, type of investigation. With their movements from vertices to neighboring vertices, the robots make the system transition from one configuration to another. Viewing this transition as the computation of an abstract function, we ask which functions are computed by which systems. Our main interest is on identifying sets of systems that are "universal", in the sense that they can collectively compute all finite functions. We are able to identify several such classes of fully synchronous systems. In particular, among other results, we prove the universality of the set of all graphs with at least one robot, of any set of graphs with at least two robots whose quotient graphs contain arbitrarily long paths, and of any set of graphs with at least three robots and arbitrarily large finite girths. We then focus on the minimum size that a network must have for the robots to be able to compute all functions on a given finite set. We are able to approximate the minimum size of such a network up to a factor that tends to 2 as $n$ goes to infinity.
Generalized minimum dominating set and application in automatic text summarization
Venue: arXiv cs.IR 2016
Year: 2016

For a graph formed by vertices and weighted edges, a generalized minimum dominating set (MDS) is a vertex set of smallest cardinality such that the summed weight of edges from each outside vertex to vertices in this set is equal to or larger than certain threshold value. This generalized MDS problem reduces to the conventional MDS problem in the limiting case of all the edge weights being equal to the threshold value. We treat the generalized MDS problem in the present paper by a replica-symmetric spin glass theory and derive a set of belief-propagation equations. As a practical application we consider the problem of extracting a set of sentences that best summarize a given input text document. We carry out a preliminary test of the statistical physics-inspired method to this automatic text summarization problem.
Strong Backdoors for Linear Temporal Logic
Venue: arXiv cs.LO 2016
Year: 2016

In the present paper we introduce the notion of strong backdoors into the field of temporal logic for the CNF-fragment of linear temporal logic introduced by Fisher. We study the parameterised complexity of the satisfiability problem parameterised by the size of the backdoor. We distinguish between backdoor detection and evaluation of backdoors into the fragments of horn and krom formulas. Here we classify the operator fragments of globally-operators for past or future, and the combination of both. Detection is shown to be in FPT whereas the complexity of evaluation behaves different. We show that for krom formulas the problem is paraNP-complete. For horn formulas the complexity is shown to be either fixed parameter tractable or paraNP-complete depending on the considered operator fragment.
Encoding Distortion Modeling For DWT-Based Wireless EEG Monitoring System
Venue: arXiv cs.OH 2016
Year: 2016

Recent advances in wireless body area sensor net- works leverage wireless and mobile communication technologies to facilitate development of innovative medical applications that can significantly enhance healthcare services and improve quality of life. Specifically, Electroencephalography (EEG)-based applications lie at the heart of these promising technologies. However, the design and operation of such applications is challenging. Power consumption requirements of the sensor nodes may turn some of these applications impractical. Hence, implementing efficient encoding schemes are essential to reduce power consumption in such applications. In this paper, we propose an analytical distortion model for the EEG-based encoding systems. Using this model, the encoder can effectively reconfigure its complexity by adjusting its control parameters to satisfy application constraints while maintaining reconstruction accuracy at the receiver side. The simulation results illustrate that the main parameters that affect the distortion are compression ratio and filter length of the considered DWT-based encoder. Furthermore, it is found that the wireless channel variations have a significant influence on the estimated distortion at the receiver side.
Data Science at Udemy: Agile Experimentation with Algorithms
Venue: arXiv cs.CY 2016
Year: 2016

In this paper, we describe the data science framework at Udemy, which currently supports the recommender and search system. We explain the motivations behind the framework and review the approach, which allows multiple individual data scientists to all become 'full stack', taking control of their own destinies from the exploration and research phase, through algorithm development, experiment setup, and deep experiment analytics. We describe algorithms tested and deployed in 2015, as well as some key insights obtained from experiments leading to the launch of the new recommender system at Udemy. Finally, we outline the current areas of research, which include search, personalization, and algorithmic topic generation.
Applied Logic in Engineering
Venue: arXiv cs.CY 2016
Year: 2016

Logic not only helps to solve complicated and safety-critical problems, but also disciplines the mind and helps to develop abstract thinking, which is very important for any area of Engineering. In this technical report, we present an overview of common challenges in teaching of formal methods and discuss our experiences from the course Applied Logic in Engineering. This course was taught at TU Munich, Germany, in Winter Semester 2012/2013.
Perceptual Vector Quantization For Video Coding
Venue: arXiv cs.MM 2016
Year: 2016

This paper applies energy conservation principles to the Daala video codec using gain-shape vector quantization to encode a vector of AC coefficients as a length (gain) and direction (shape). The technique originates from the CELT mode of the Opus audio codec, where it is used to conserve the spectral envelope of an audio signal. Conserving energy in video has the potential to preserve textures rather than low-passing them. Explicitly quantizing a gain allows a simple contrast masking model with no signaling cost. Vector quantizing the shape keeps the number of degrees of freedom the same as scalar quantization, avoiding redundancy in the representation. We demonstrate how to predict the vector by transforming the space it is encoded in, rather than subtracting off the predictor, which would make energy conservation impossible. We also derive an encoding of the vector-quantized codewords that takes advantage of their non-uniform distribution. We show that the resulting technique outperforms scalar quantization by an average of 0.90 dB on still images, equivalent to a 24.8% reduction in bitrate at equal quality, while for videos, the improvement averages 0.83 dB, equivalent to a 13.7% reduction in bitrate.
Generalized Jensen Inequalities with Application to Stability Analysis of Systems with Distributed Delays over Infinite Time-Horizons
Venue: arXiv cs.SY 2016
Year: 2016

The Jensen inequality has been recognized as a powerful tool to deal with the stability of time-delay systems. Recently, a new inequality that encompasses the Jensen inequality was proposed for the stability analysis of systems with finite delays. In this paper, we first present a generalized integral inequality and its double integral extension. It is shown how these inequalities can be applied to improve the stability result for linear continuous-time systems with gamma-distributed delays. Then, for the discrete-time counterpart we provide an extended Jensen summation inequality with infinite sequences, which leads to less conservative stability conditions for linear discrete-time systems with poisson-distributed delays. The improvements obtained thanks to the introduced generalized inequalities are demonstrated by examples.
Hedonic Games with Graph-restricted Communication
Venue: arXiv cs.GT 2016
Year: 2016

We study hedonic coalition formation games in which cooperation among the players is restricted by a graph structure: a subset of players can form a coalition if and only if they are connected in the given graph. We investigate the complexity of finding stable outcomes in such games, for several notions of stability. In particular, we provide an efficient algorithm that finds an individually stable partition for an arbitrary hedonic game on an acyclic graph. We also introduce a new stability concept -in-neighbor stability- which is tailored for our setting. We show that the problem of finding an in-neighbor stable outcome admits a polynomial-time algorithm if the underlying graph is a path, but is NP-hard for arbitrary trees even for additively separable hedonic games; for symmetric additively separable games we obtain a PLS-hardness result.
A Specification of Open Transactional Memory for Haskell
Venue: arXiv cs.PL 2016
Year: 2016

Transactional memory (TM) has emerged as a promising abstraction for concurrent programming alternative to lock-based synchronizations. However, most TM models admit only isolated transactions, which are not adequate in multi-threaded programming where transactions have to interact via shared data before committing. In this paper, we present Open Transactional Memory (OTM), a programming abstraction supporting safe, data-driven interactions between composable memory transactions. This is achieved by relaxing isolation between transactions, still ensuring atomicity: threads of different transactions can interact by accessing shared variables, but then their transactions have to commit together-actually, these transactions are transparently merged. This model allows for loosely-coupled interactions since transaction merging is driven only by accesses to shared data, with no need to specify participants beforehand. In this paper we provide a specification of the OTM in the setting of Concurrent Haskell, showing that it is a conservative extension of current STM abstraction. In particular, we provide a formal semantics, which allows us to prove that OTM satisfies the \emph{opacity} criterion.
11 x 11 Domineering is Solved: The first player wins
Venue: arXiv cs.AI 2016
Year: 2016

We have developed a program called MUDoS (Maastricht University Domineering Solver) that solves Domineering positions in a very efficient way. This enables the solution of known positions so far (up to the 10 x 10 board) much quicker (measured in number of investigated nodes). More importantly, it enables the solution of the 11 x 11 Domineering board, a board up till now far out of reach of previous Domineering solvers. The solution needed the investigation of 259,689,994,008 nodes, using almost half a year of computation time on a single simple desktop computer. The results show that under optimal play the first player wins the 11 x 11 Domineering game, irrespective if Vertical or Horizontal starts the game. In addition, several other boards hitherto unsolved were solved. Using the convention that Vertical starts, the 8 x 15, 11 x 9, 12 x 8, 12 x 15, 14 x 8, and 17 x 6 boards are all won by Vertical, whereas the 6 x 17, 8 x 12, 9 x 11, and 11 x 10 boards are all won by Horizontal.
Cell segmentation with random ferns and graph-cuts
Venue: arXiv cs.CV 2016
Year: 2016

The progress in imaging techniques have allowed the study of various aspect of cellular mechanisms. To isolate individual cells in live imaging data, we introduce an elegant image segmentation framework that effectively extracts cell boundaries, even in the presence of poor edge details. Our approach works in two stages. First, we estimate pixel interior/border/exterior class probabilities using random ferns. Then, we use an energy minimization framework to compute boundaries whose localization is compliant with the pixel class probabilities. We validate our approach on a manually annotated dataset.
Pilot Length Optimization for Spatially Correlated Multi-User MIMO Channel Estimation
Venue: arXiv cs.IT 2016
Year: 2016

We address the design of pilot sequences for channel estimation in the context of multiple-user Massive MIMO; considering the presence of channel correlation, and assuming that the statistics are known, we seek to exploit the spatial correlation of the channels to minimize the length of the pilot sequences, and specifically the fact that the users can be separated either through their spatial signature (low-rank channel covariance matrices), or through the use of different training sequences. We introduce an algorithm to design short training sequences for a given set of user covariance matrices. The obtained pilot sequences are in general non-orthogonal, however they ensure that the channel estimation error variance is uniformly upper-bounded by a chosen constant over all channel dimensions. We show through simulations using a realistic scenario based on the one-ring channel model that the proposed technique can yield pilot sequences of length significantly smaller than the number of users in the system.
Joint Transmit and Receive Beamforming for Multi-Relay MIMO-OFDMA Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

A novel transmission protocol is conceived for a multi-user, multi-relay, multiple-input--multiple-output orthogonal frequency-division multiple-access (MIMO-OFDMA) cellular network based on joint transmit and receive beamforming. More specifically, the network's MIMO channels are mathematically decomposed into several effective multiple-input--single-output (MISO) channels, which are spatially multiplexed for transmission. For the sake of improving the attainable capacity, these MISO channels are grouped using a pair of novel grouping algorithms, which are then evaluated in terms of their performance versus complexity trade-off\footnote{This paper concisely focuses on the transmission protocol proposed in our previous work [1]. For more details, please refer to [1].}.
Packet Error Rate Performance of IEEE802.11g under Bluetooth Interface
Venue: arXiv cs.NI 2016
Year: 2016

This study approaches the issues concerning the coexistence of the IEEE 802.11g wireless networks and the adhoc Bluetooth networks that operate within the same 2.4 GHz band. The performance of 802.11g is evaluated by simulating the PER (Packet Error Rate) parameter and coverage area. The simulation experiments are based on the worst case scenario presumption, which entails the transmission of HV1 packet which HV1 link requires transmission on 100% of the Bluetooth (BT) time slots using the maximum hop rate of 1600 hops per sec. The paper suggests a practical approach to mitigate the interference using symbol erasures technique through the assessment of the PER parameter at various Eb/No values. The results show that the symbol erasures can effectively mitigate the interference and enhance the performance of the 802.11g.
The Golay Code Outperforms the Extended Golay Code Under Hard-Decision Decoding
Venue: arXiv cs.IT 2016
Year: 2016

We show that the binary Golay code is slightly more power efficient than the extended binary Golay code under maximum-likelihood (ML), hard-decision decoding. In fact, if a codeword from the extended code is transmitted, one cannot achieve a higher probability of correct decoding than by simply ignoring the 24th symbol and using an ML decoder for the non-extended code on the first 23 symbols. This is so, despite the fact that using that last symbol would allow one to sometimes correct error patterns with weight four. To our knowledge the worse performance of the extended Golay code has not been previously noted, but it is noteworthy considering that it is the extended version of the code that has been preferred in many deployments.
Human-Data Interaction in Healthcare
Venue: arXiv cs.HC 2016
Year: 2016

In this paper, we focus on an emerging strand of IT-oriented research, namely Human-Data Interaction (HDI) and how this can be applied to healthcare. HDI regards both how humans create and use data by means of interactive systems, which can both assist and constrain them, as well as to passively collect and proactively generate data. Healthcare provides a challenging arena to test the potential of HDI to provide a new, user-centered perspective on how data work should be supported and assessed, especially in the light of the fact that data are becoming increasingly big and that many tools are now available for the lay people, including doctors and nurses, to interact with health-related data.
Character Values of the Sidelnikov-Lempel-Cohn-Eastman Sequences
Venue: arXiv cs.IT 2016
Year: 2016

Binary sequences with good autocorrelation properties and large linear complexity are useful in stream cipher cryptography. The Sidelnikov-Lempel-Cohn-Eastman (SLCE) sequences have nearly optimal autocorrelation. However, the problem of determining the linear complexity of the SLCE sequences is still open. Our approach is to exploit the fact that character values associated with the SLCE sequences can be expressed in terms of a certain type of Jacobi sum. By making use of known evaluations of Gauss and Jacobi sums in the "pure" and "small index" cases, we are able to obtain new insight into the linear complexity of the SLCE sequences.