OpenRaiser/Intern-Atlas huggingface dataset:
Modeling IEEE 802.15.4 Networks over Fading Channels
Venue: arXiv cs.NI 2013
Year: 2013

Although the performance of the medium access control (MAC) of the IEEE 802.15.4 has been investigated under the assumption of ideal wireless channel, the understanding of the cross-layer dynamics between MAC and physical layer is an open problem when the wireless channel exhibits path loss, multi-path fading, and shadowing. The analysis of MAC and wireless channel interaction is essential for consistent performance prediction, correct design and optimization of the protocols. In this paper, a novel approach to analytical modeling of these interactions is proposed. The analysis considers simultaneously a composite channel fading, interference generated by multiple terminals, the effects induced by hidden terminals, and the MAC reduced carrier sensing capabilities. Depending on the MAC parameters and physical layer thresholds, it is shown that the MAC performance indicators over fading channels can be far from those derived under ideal channel assumptions. As novel results, we show to what extent the presence of fading may be beneficial for the overall network performance by reducing the multiple access interference, and how this can be used to drive joint selection of MAC and physical layer parameters.
QuickHeapsort: Modifications and improved analysis
Venue: arXiv cs.DS 2013
Year: 2013

We present a new analysis for QuickHeapsort splitting it into the analysis of the partition-phases and the analysis of the heap-phases. This enables us to consider samples of non-constant size for the pivot selection and leads to better theoretical bounds for the algorithm. Furthermore we introduce some modifications of QuickHeapsort, both in-place and using n extra bits. We show that on every input the expected number of comparisons is n lg n - 0.03n + o(n) (in-place) respectively n lg n -0.997 n+ o (n). Both estimates improve the previously known best results. (It is conjectured in Wegener93 that the in-place algorithm Bottom-Up-Heapsort uses at most n lg n + 0.4 n on average and for Weak-Heapsort which uses n extra-bits the average number of comparisons is at most n lg n -0.42n in EdelkampS02.) Moreover, our non-in-place variant can even compete with index based Heapsort variants (e.g. Rank-Heapsort in WangW07) and Relaxed-Weak-Heapsort (n lg n -0.9 n+ o (n) comparisons in the worst case) for which no O(n)-bound on the number of extra bits is known.
Joint User Grouping and Linear Virtual Beamforming: Complexity, Algorithms and Approximation Bounds
Venue: arXiv cs.IT 2013
Year: 2013

In a wireless system with a large number of distributed nodes, the quality of communication can be greatly improved by pooling the nodes to perform joint transmission/reception. In this paper, we consider the problem of optimally selecting a subset of nodes from potentially a large number of candidates to form a virtual multi-antenna system, while at the same time designing their joint linear transmission strategies. We focus on two specific application scenarios: 1) multiple single antenna transmitters cooperatively transmit to a receiver; 2) a single transmitter transmits to a receiver with the help of a number of cooperative relays. We formulate the joint node selection and beamforming problems as cardinality constrained optimization problems with both discrete variables (used for selecting cooperative nodes) and continuous variables (used for designing beamformers). For each application scenario, we first characterize the computational complexity of the joint optimization problem, and then propose novel semi-definite relaxation (SDR) techniques to obtain approximate solutions. We show that the new SDR algorithms have a guaranteed approximation performance in terms of the gap to global optimality, regardless of channel realizations. The effectiveness of the proposed algorithms is demonstrated via numerical experiments.
Geometric simulation of locally optimal tool paths in three-axis milling
Venue: arXiv cs.CG 2013
Year: 2013

The most important aim in tool path generation methods is to increase the machining efficiency by minimizing the total length of tool paths while the error is kept under a prescribed tolerance. This can be achieved by determining the moving direction of the cutting tool such that the machined stripe is the widest. From a technical point of view it is recommended that the angle between the tool axis and the surface normal does not change too much along the tool path in order to ensure even abrasion of the tool. In this paper a mathematical method for tool path generation in 3-axis milling is presented, which considers these requirements by combining the features of isophotic curves and principal curvatures. It calculates the proposed moving direction of the tool at each point of the surface. The proposed direction depends on the measurement of the tool and on the curvature values of the surface. For triangulated surfaces a new local offset computation method is presented, which is suitable also for detecting tool collision with the target surface and self intersection in the offset mesh.
A proposal to first principles electronic structure calculation: Symbolic-Numeric method
Venue: arXiv cs.SC 2013
Year: 2013

This study proposes an approach toward the first principles electronic structure calculation with the aid of symbolic-numeric solving. The symbolic computation enables us to express the Hartree-Fock-Roothaan equation and the molecular integrals in analytic forms and approximate them as a set of polynomial equations. By use of the Grobner bases technique, the polynomial equations are transformed into other ones which have identical roots. The converted equations take more convenient forms which will simplify numerical procedures, from which we can derive necessary physical properties in order, in an a la carte way. This method enables us to solve the electronic structure calculation, the optimization of any kind, or the inverse problem as a forward problem in a unified way, in which there is no need for iterative self-consistent procedures with trials and errors.
Approximate Two-Party Privacy-Preserving String Matching with Linear Complexity
Venue: arXiv cs.CR 2013
Year: 2013

Consider two parties who want to compare their strings, e.g., genomes, but do not want to reveal them to each other. We present a system for privacy-preserving matching of strings, which differs from existing systems by providing a deterministic approximation instead of an exact distance. It is efficient (linear complexity), non-interactive and does not involve a third party which makes it particularly suitable for cloud computing. We extend our protocol, such that it mitigates iterated differential attacks proposed by Goodrich. Further an implementation of the system is evaluated and compared against current privacy-preserving string matching algorithms.
Design of APSK Constellations for Coherent Optical Channels with Nonlinear Phase Noise
Venue: arXiv cs.IT 2013
Year: 2013

We study the design of amplitude phase-shift keying (APSK) constellations for a coherent fiber-optical communication system where nonlinear phase noise (NLPN) is the main system impairment. APSK constellations can be regarded as a union of phase-shift keying (PSK) signal sets with different amplitude levels. A practical two-stage (TS) detection scheme is analyzed, which performs close to optimal detection for high enough input power. We optimize APSK constellations with 4, 8, and 16 points in terms of symbol error probability (SEP) under TS detection for several combinations of input power and fiber length. Our results show that APSK is a promising modulation format in order to cope with NLPN. As an example, for 16 points, performance gains of 3.2 dB can be achieved at a SEP of 10^-2 compared to 16-QAM by choosing an optimized APSK constellation. We also demonstrate that in the presence of severe nonlinear distortions, it may become beneficial to sacrifice a constellation point or an entire constellation ring to reduce the average SEP. Finally, we discuss the problem of selecting a good binary labeling for the found constellations. For the class of rectangular APSK a labeling design method is proposed, resulting in near-optimal bit error probability.
Bounds on the Average Sensitivity of Nested Canalizing Functions
Venue: arXiv cs.IT 2013
Year: 2013

Nested canalizing Boolean (NCF) functions play an important role in biological motivated regulative networks and in signal processing, in particular describing stack filters. It has been conjectured that NCFs have a stabilizing effect on the network dynamics. It is well known that the average sensitivity plays a central role for the stability of (random) Boolean networks. Here we provide a tight upper bound on the average sensitivity for NCFs as a function of the number of relevant input variables. As conjectured in literature this bound is smaller than 4/3 This shows that a large number of functions appearing in biological networks belong to a class that has very low average sensitivity, which is even close to a tight lower bound.
Gene selection with guided regularized random forest
Venue: arXiv cs.LG 2013
Year: 2013

The regularized random forest (RRF) was recently proposed for feature selection by building only one ensemble. In RRF the features are evaluated on a part of the training data at each tree node. We derive an upper bound for the number of distinct Gini information gain values in a node, and show that many features can share the same information gain at a node with a small number of instances and a large number of features. Therefore, in a node with a small number of instances, RRF is likely to select a feature not strongly relevant. Here an enhanced RRF, referred to as the guided RRF (GRRF), is proposed. In GRRF, the importance scores from an ordinary random forest (RF) are used to guide the feature selection process in RRF. Experiments on 10 gene data sets show that the accuracy performance of GRRF is, in general, more robust than RRF when their parameters change. GRRF is computationally efficient, can select compact feature subsets, and has competitive accuracy performance, compared to RRF, varSelRF and LASSO logistic regression (with evaluations from an RF classifier). Also, RF applied to the features selected by RRF with the minimal regularization outperforms RF applied to all the features for most of the data sets considered here. Therefore, if accuracy is considered more important than the size of the feature subset, RRF with the minimal regularization may be considered. We use the accuracy performance of RF, a strong classifier, to evaluate feature selection methods, and illustrate that weak classifiers are less capable of capturing the information contained in a feature subset. Both RRF and GRRF were implemented in the "RRF" R package available at CRAN, the official R package archive.
Parameterizations of Test Cover with Bounded Test Sizes
Venue: arXiv cs.DS 2013
Year: 2013

In the {\sc Test Cover} problem we are given a hypergraph $H=(V, \mathcal{E})$ with $|V|=n, |\mathcal{E}|=m$, and we assume that $\mathcal{E}$ is a test cover, i.e. for every pair of vertices $x_i, x_j$, there exists an edge $e \in \mathcal{E}$ such that $|{x_i,x_j}\cap e|=1$. The objective is to find a minimum subset of $\mathcal{E}$ which is a test cover. The problem is used for identification across many areas, and is NP-complete. From a parameterized complexity standpoint, many natural parameterizations of {\sc Test Cover} are either $W[1]$-complete or have no polynomial kernel unless $coNP\subseteq NP/poly$, and thus are unlikely to be solveable efficiently. However, in practice the size of the edges is often bounded. In this paper we study the parameterized complexity of {\sc Test-$r$-Cover}, the restriction of {\sc Test Cover} in which each edge contains at most $r \ge 2$ vertices. In contrast to the unbounded case, we show that the following below-bound parameterizations of {\sc Test-$r$-Cover} are fixed-parameter tractable with a polynomial kernel: (1) Decide whether there exists a test cover of size $n-k$, and (2) decide whether there exists a test cover of size $m-k$, where $k$ is the parameter. In addition, we prove a new lower bound $\lceil \frac{2(n-1)}{r+1} \rceil$ on the minimum size of a test cover when the size of each edge is bounded by $r$. {\sc Test-$r$-Cover} parameterized above this bound is unlikely to be fixed-parameter tractable; in fact, we show that it is para-NP-complete, as it is NP-hard to decide whether an instance of {\sc Test-$r$-Cover} has a test cover of size exactly $\frac{2(n-1)}{r+1}$.
Testing MapReduce-Based Systems
Venue: arXiv cs.DC 2013
Year: 2013

MapReduce (MR) is the most popular solution to build applications for large-scale data processing. These applications are often deployed on large clusters of commodity machines, where failures happen constantly due to bugs, hardware problems, and outages. Testing MR-based systems is hard, since it is needed a great effort of test harness to execute distributed test cases upon failures. In this paper, we present a novel testing solution to tackle this issue called HadoopTest. This solution is based on a scalable harness approach, where distributed tester components are hung around each map and reduce worker (i.e., node). Testers are allowed to stimulate each worker to inject failures on them, monitor their behavior, and validate testing results. HadoopTest was used to test two applications bundled into Hadoop, the Apache open source MapReduce implementation. Our initial implementation demonstrates promising results, with HadoopTest coordinating test cases across distributed MapReduce workers, and finding bugs.
Compute-and-Forward Strategies for Cooperative Distributed Antenna Systems
Venue: arXiv cs.IT 2013
Year: 2013

We study a distributed antenna system where $L$ antenna terminals (ATs) are connected to a Central Processor (CP) via digital error-free links of finite capacity $R_0$, and serve $K$ user terminals (UTs). We contribute to the subject in the following ways: 1) for the uplink, we apply the "Compute and Forward" (CoF) approach and examine the corresponding system optimization at finite SNR; 2) For the downlink, we propose a novel precoding scheme nicknamed "Reverse Compute and Forward" (RCoF); 3) In both cases, we present low-complexity versions of CoF and RCoF based on standard scalar quantization at the receivers, that lead to discrete-input discrete-output symmetric memoryless channel models for which near-optimal performance can be achieved by standard single-user linear coding; 4) For the case of large $R_0$, we propose a novel "Integer Forcing Beamforming" (IFB) scheme that generalizes the popular zero-forcing beamforming and achieves sum rate performance close to the optimal Gaussian Dirty-Paper Coding. The proposed uplink and downlink system optimization focuses specifically on the ATs and UTs selection problem. We present low-complexity ATs and UTs selection schemes and demonstrate, through Monte Carlo simulation in a realistic environment with fading and shadowing, that the proposed schemes essentially eliminate the problem of rank deficiency of the system matrix and greatly mitigate the non-integer penalty affecting CoF/RCoF at high SNR. Comparison with other state-of-the art information theoretic schemes, such as "Quantize reMap and Forward" for the uplink and "Compressed Dirty Paper Coding" for the downlink, show competitive performance of the proposed approaches with significantly lower complexity.
Blending Learning and Inference in Structured Prediction
Venue: arXiv cs.LG 2013
Year: 2013

In this paper we derive an efficient algorithm to learn the parameters of structured predictors in general graphical models. This algorithm blends the learning and inference tasks, which results in a significant speedup over traditional approaches, such as conditional random fields and structured support vector machines. For this purpose we utilize the structures of the predictors to describe a low dimensional structured prediction task which encourages local consistencies within the different structures while learning the parameters of the model. Convexity of the learning task provides the means to enforce the consistencies between the different parts. The inference-learning blending algorithm that we propose is guaranteed to converge to the optimum of the low dimensional primal and dual programs. Unlike many of the existing approaches, the inference-learning blending allows us to learn efficiently high-order graphical models, over regions of any size, and very large number of parameters. We demonstrate the effectiveness of our approach, while presenting state-of-the-art results in stereo estimation, semantic segmentation, shape reconstruction, and indoor scene understanding.
Enhanced Community Structure Detection in Complex Networks with Partial Background Information
Venue: arXiv cs.SI 2013
Year: 2013

Community structure detection in complex networks is important since it can help better understand the network topology and how the network works. However, there is still not a clear and widely-accepted definition of community structure, and in practice, different models may give very different results of communities, making it hard to explain the results. In this paper, different from the traditional methodologies, we design an enhanced semi-supervised learning framework for community detection, which can effectively incorporate the available prior information to guide the detection process and can make the results more explainable. By logical inference, the prior information is more fully utilized. The experiments on both the synthetic and the real-world networks confirm the effectiveness of the framework.
Semi-Quantitative Group Testing: A Unifying Framework for Group Testing with Applications in Genotyping
Venue: arXiv cs.IT 2013
Year: 2013

We propose a novel group testing method, termed semi-quantitative group testing, motivated by a class of problems arising in genome screening experiments. Semi-quantitative group testing (SQGT) is a (possibly) non-binary pooling scheme that may be viewed as a concatenation of an adder channel and an integer-valued quantizer. In its full generality, SQGT may be viewed as a unifying framework for group testing, in the sense that most group testing models are special instances of SQGT. For the new testing scheme, we define the notion of SQ-disjunct and SQ-separable codes, representing generalizations of classical disjunct and separable codes. We describe several combinatorial and probabilistic constructions for such codes. While for most of these constructions we assume that the number of defectives is much smaller than total number of test subjects, we also consider the case in which there is no restriction on the number of defectives and they may be as large as the total number of subjects. For the codes constructed in this paper, we describe a number of efficient decoding algorithms. In addition, we describe a belief propagation decoder for sparse SQGT codes for which no other efficient decoder is currently known. Finally, we define the notion of capacity of SQGT and evaluate it for some special choices of parameters using information theoretic methods.
Enabling Reusability in Agile Software Development
Venue: arXiv cs.SE 2013
Year: 2013

Software Engineering Discipline is constantly achieving momentum from past two decades. In last decade, remarkable progress has been observed. New process models that are introduced from time to time in order to keep pace with multidimensional demands of the industry. New software development paradigms are finding its place in industry such as Agile Software Development, Reuse based Development and Component based Development. But different software development models fail to satisfy many needs of software industry. As aim of all the process models is same, i.e., to get quality product, reduce time of development, productivity improvement and reduction in cost. Still, no single process model is complete in itself. Software industry is moving towards Agile Software Development. Agile development does not obviously fit well for building reusable artifacts. However, with careful attention, and important modifications made to agile processes, it may be possible to successfully adapt and put on agile methods to development of reusable objects. The model being proposed here combines the features of Agile Software Development and reusability.
Sublinear Bounds for Randomized Leader Election
Venue: arXiv cs.DS 2013
Year: 2013

This paper concerns {\em randomized} leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete $n$-node networks that runs in O(1) rounds and (with high probability) uses only $O(\sqrt{n}\log^{3/2} n)$ messages to elect a unique leader (with high probability). When considering the "explicit" variant of leader election where eventually every node knows the identity of the leader, our algorithm yields the asymptotically optimal bounds of O(1) rounds and O(n) messages. This algorithm is then extended to one solving leader election on any connected non-bipartite $n$-node graph $G$ in $O(τ(G))$ time and $O(τ(G)\sqrt{n}\log^{3/2} n)$ messages, where $τ(G)$ is the mixing time of a random walk on $G$. The above result implies highly efficient (sublinear running time and messages) leader election algorithms for networks with small mixing times, such as expanders and hypercubes. In contrast, previous leader election algorithms had at least linear message complexity even in complete graphs. Moreover, super-linear message lower bounds are known for time-efficient {\em deterministic} leader election algorithms. Finally, we present an almost matching lower bound for randomized leader election, showing that $Ω(\sqrt n)$ messages are needed for any leader election algorithm that succeeds with probability at least $1/e + \eps$, for any small constant $\eps > 0$. We view our results as a step towards understanding the randomized complexity ofleader election in distributed networks.
Living is information processing: from molecules to global systems
Venue: arXiv cs.IT 2013
Year: 2013

We extend the concept that life is an informational phenomenon, at every level of organisation, from molecules to the global ecological system. According to this thesis: (a) living is information processing, in which memory is maintained by both molecular states and ecological states as well as the more obvious nucleic acid coding; (b) this information processing has one overall function - to perpetuate itself; and (c) the processing method is filtration (cognition) of, and synthesis of, information at lower levels to appear at higher levels in complex systems (emergence). We show how information patterns, are united by the creation of mutual context, generating persistent consequences, to result in `functional information'. This constructive process forms arbitrarily large complexes of information, the combined effects of which include the functions of life. Molecules and simple organisms have already been measured in terms of functional information content; we show how quantification may be extended to each level of organisation up to the ecological. In terms of a computer analogy, life is both the data and the program and its biochemical structure is the way the information is embodied. This idea supports the seamless integration of life at all scales with the physical universe. The innovation reported here is essentially to integrate these ideas, basing information on the `general definition' of information, rather than simply the statistics of information, thereby explaining how functional information operates throughout life.