OpenRaiser/Intern-Atlas huggingface dataset:
A Message-Passing Approach to Combating Hidden Terminals in Wireless Networks
Venue: arXiv cs.NI 2014
Year: 2014

Collisions with hidden terminals is a major cause of performance degradation in 802.11 and likewise wireless networks. Carrier sense multiple access with collision avoidance (CSMA/CA) is utilized to avoid collisions at the cost of spatial reuse. This report studies receiver design to mitigate interference from hidden terminals. A wireless channel model with correlated fading in time is assumed. A message-passing approach is proposed, in which a receiver can successfully receive and decode partially overlapping transmissions from two sources rather than treating undesired one as thermal noise. Numerical results of both coded and uncoded systems show the advantage of the receiver over conventional receivers.
Channel Estimation and Hybrid Precoding for Millimeter Wave Cellular Systems
Venue: arXiv cs.IT 2014
Year: 2014

Millimeter wave (mmWave) cellular systems will enable gigabit-per-second data rates thanks to the large bandwidth available at mmWave frequencies. To realize sufficient link margin, mmWave systems will employ directional beamforming with large antenna arrays at both the transmitter and receiver. Due to the high cost and power consumption of gigasample mixed-signal devices, mmWave precoding will likely be divided among the analog and digital domains. The large number of antennas and the presence of analog beamforming requires the development of mmWave-specific channel estimation and precoding algorithms. This paper develops an adaptive algorithm to estimate the mmWave channel parameters that exploits the poor scattering nature of the channel. To enable the efficient operation of this algorithm, a novel hierarchical multi-resolution codebook is designed to construct training beamforming vectors with different beamwidths. For single-path channels, an upper bound on the estimation error probability using the proposed algorithm is derived, and some insights into the efficient allocation of the training power among the adaptive stages of the algorithm are obtained. The adaptive channel estimation algorithm is then extended to the multi-path case relying on the sparse nature of the channel. Using the estimated channel, this paper proposes a new hybrid analog/digital precoding algorithm that overcomes the hardware constraints on the analog-only beamforming, and approaches the performance of digital solutions. Simulation results show that the proposed low-complexity channel estimation algorithm achieves comparable precoding gains compared to exhaustive channel training algorithms. The results also illustrate that the proposed algorithms can approach the coverage probability achieved by perfect channel knowledge even in the presence of interference.
Propagators and Violation Functions for Geometric and Workload Constraints Arising in Airspace Sectorisation
Venue: arXiv cs.AI 2014
Year: 2014

Airspace sectorisation provides a partition of a given airspace into sectors, subject to geometric constraints and workload constraints, so that some cost metric is minimised. We make a study of the constraints that arise in airspace sectorisation. For each constraint, we give an analysis of what algorithms and properties are required under systematic search and stochastic local search.
Superimposed Codes and Threshold Group Testing
Venue: arXiv cs.IT 2014
Year: 2014

We will discuss superimposed codes and non-adaptive group testing designs arising from the potentialities of compressed genotyping models in molecular biology. The given paper was motivated by the 30th anniversary of D'yachkov-Rykov recurrent upper bound on the rate of superimposed codes published in 1982. We were also inspired by recent results obtained for non-adaptive threshold group testing which develop the theory of superimposed codes
RES: Regularized Stochastic BFGS Algorithm
Venue: arXiv cs.LG 2014
Year: 2014

RES, a regularized stochastic version of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) quasi-Newton method is proposed to solve convex optimization problems with stochastic objectives. The use of stochastic gradient descent algorithms is widespread, but the number of iterations required to approximate optimal arguments can be prohibitive in high dimensional problems. Application of second order methods, on the other hand, is impracticable because computation of objective function Hessian inverses incurs excessive computational cost. BFGS modifies gradient descent by introducing a Hessian approximation matrix computed from finite gradient differences. RES utilizes stochastic gradients in lieu of deterministic gradients for both, the determination of descent directions and the approximation of the objective function's curvature. Since stochastic gradients can be computed at manageable computational cost RES is realizable and retains the convergence rate advantages of its deterministic counterparts. Convergence results show that lower and upper bounds on the Hessian egeinvalues of the sample functions are sufficient to guarantee convergence to optimal arguments. Numerical experiments showcase reductions in convergence time relative to stochastic gradient descent algorithms and non-regularized stochastic versions of BFGS. An application of RES to the implementation of support vector machines is developed.
Video Compressive Sensing for Dynamic MRI
Venue: arXiv cs.CV 2014
Year: 2014

We present a video compressive sensing framework, termed kt-CSLDS, to accelerate the image acquisition process of dynamic magnetic resonance imaging (MRI). We are inspired by a state-of-the-art model for video compressive sensing that utilizes a linear dynamical system (LDS) to model the motion manifold. Given compressive measurements, the state sequence of an LDS can be first estimated using system identification techniques. We then reconstruct the observation matrix using a joint structured sparsity assumption. In particular, we minimize an objective function with a mixture of wavelet sparsity and joint sparsity within the observation matrix. We derive an efficient convex optimization algorithm through alternating direction method of multipliers (ADMM), and provide a theoretical guarantee for global convergence. We demonstrate the performance of our approach for video compressive sensing, in terms of reconstruction accuracy. We also investigate the impact of various sampling strategies. We apply this framework to accelerate the acquisition process of dynamic MRI and show it achieves the best reconstruction accuracy with the least computational time compared with existing algorithms in the literature.
Feedback Control of Negative-Imaginary Systems: Large Flexible structures with colocated actuators and sensors
Venue: arXiv cs.SY 2014
Year: 2014

This paper presents a survey of recent results on the theory of negative imaginary systems. This theory can be applied to the robust control of large flexible structures with colocated force actuators and position sensors.
The result for the grundy number on p4 classes
Venue: arXiv cs.DM 2014
Year: 2014

Our work becomes integrated into the general problem of the stability of the network ad hoc. Some, works attacked (affected) this problem. Among these works, we find the modelling of the network ad hoc in the form of a graph. We can resume the problem of coherence of the network ad hoc of a problem of allocation of frequency We study a new class of graphs, the fat-extended P4 graphs, and we give a polynomial time algorithm to calculate the Grundy number of the graphs in this class. This result implies that the Grundy number can be found in polynomial time for many graphs
Synchronizing Rankings via Interactive Communication
Venue: arXiv cs.IT 2014
Year: 2014

We consider the problem of exact synchronization of two rankings at remote locations connected by a two-way channel. Such synchronization problems arise when items in the data are distinguishable, as is the case for playlists, tasklists, crowdvotes and recommender systems rankings. Our model accounts for different constraints on the communication throughput of the forward and feedback links, resulting in different anchoring, syndrome and checksum computation strategies. Information editing is assumed of the form of deletions, insertions, block deletions/insertions, translocations and transpositions. The protocols developed under the given model are order-optimal with respect to genie aided lower bounds.
Hallucinating optimal high-dimensional subspaces
Venue: arXiv cs.CV 2014
Year: 2014

Linear subspace representations of appearance variation are pervasive in computer vision. This paper addresses the problem of robustly matching such subspaces (computing the similarity between them) when they are used to describe the scope of variations within sets of images of different (possibly greatly so) scales. A naive solution of projecting the low-scale subspace into the high-scale image space is described first and subsequently shown to be inadequate, especially at large scale discrepancies. A successful approach is proposed instead. It consists of (i) an interpolated projection of the low-scale subspace into the high-scale space, which is followed by (ii) a rotation of this initial estimate within the bounds of the imposed ``downsampling constraint''. The optimal rotation is found in the closed-form which best aligns the high-scale reconstruction of the low-scale subspace with the reference it is compared to. The method is evaluated on the problem of matching sets of (i) face appearances under varying illumination and (ii) object appearances under varying viewpoint, using two large data sets. In comparison to the naive matching, the proposed algorithm is shown to greatly increase the separation of between-class and within-class similarities, as well as produce far more meaningful modes of common appearance on which the match score is based.
Novel Integrated Approach of Software Development and Design Pattern with X-CM
Venue: arXiv cs.SE 2014
Year: 2014

Expert evaluation in software life cycle is playing a vital role. In this paper, we have discussed about the formal framework for selecting the best model with some enhanced features. In our work we have introduced a novel algorithm X Chain Model X-CM. Here XCM overcomes the limitation of Vmodel. In XCM, we have concentrated on hierarchy of multiple independent sub-projects in project development phase. XCM merges through the subprojects binding them at their Integration Testing Phases. Hence combining binary modules at each stage into a new module through chains of X till the final level in the hierarchy is implemented. X-CM results in reducing the time and effort for software developer. In addition to this, X-CM also rules out the dependency errors between the modules at each stage of combination. Here we have tested our proposed X-CM with Unit Testing and Integrating test. Finally, we proved that X-CM Model works better than Spiral, Prototype and V-Model.
Modeling TCP Throughput with Random Packet Drops
Venue: arXiv cs.NI 2014
Year: 2014

The present report deals with the modeling of the long-term throughput, a.k.a., send rate, of the Transmission Control Protocol (TCP) under the following assumptions. (i) We consider a single 'infinite source' using a network path from sender to receiver. (ii) Each TCP packet is randomly dropped with probability p; independently of previous drops or any other event/parameter. (iii) The - never changing - receiver window limits the amount of outstanding data. (iv) The receiver acknowledges every packet. (v) The TCP modeled here conforms to the publicly available standards (RFCs) as concerns congestion control. We validate and determine the limits of the different models proposed here using packet-level simulations. The contributions of the present work are the following: (a) We determine three regimes, and their conditions of applicability, depending on p: Linear law regime, square root law regime, and timeout regime. (b) As concerns the relationship between the linear and square root regimes, we give additional insights relatively to previously published work. (c) We give the exact equations governing the TCP send rate in any regime. (d) From the exact equation and under the further condition that the path is not saturated, we give and discuss approximations for the send rate of the NewReno variant of TCP. A by-product of these calculations is the distribution of the sender window, independently of any timing or saturation consideration. (e) These approximations give results that are accurate to a few percent when compared to simulation results. Detailed comparison and sources of errors between theory and simulations are also discussed.
Decode-and-Forward Relay Beamforming with Secret and Non-Secret Messages
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we study beamforming in decode-and-forward (DF) relaying using multiple relays, where the source node sends a secret message as well as a non-secret message to the destination node in the presence of multiple non-colluding eavesdroppers. The non-secret message is transmitted at a fixed rate $R_{0}$ and requires no protection from the eavesdroppers, whereas the secret message needs to be protected from the eavesdroppers. The source and relays operate under a total power constraint. We find the optimum source powers and weights of the relays for both secret and non-secret messages which maximize the worst case secrecy rate for the secret message as well as meet the information rate constraint $R_{0}$ for the non-secret message. We solve this problem for the cases when ($i$) perfect channel state information (CSI) of all links is known, and ($ii$) only the statistical CSI of the eavesdroppers links and perfect CSI of other links are known.
On Classification of Toric Surface Codes of Low Dimension
Venue: arXiv cs.IT 2014
Year: 2014

This work is a natural continuation of our previous work \cite{yz}. In this paper, we give a complete classification of toric surface codes of dimension less than or equal to 6, except a special pair, $C_{P_6^{(4)}}$ and $C_{P_6^{(5)}}$ over $\mathbb{F}_8$. Also, we give an example, $C_{P_6^{(5)}}$ and $C_{P_6^{(6)}}$ over $\mathbb{F}_7$, to illustrate that two monomially equivalent toric codes can be constructed from two lattice non-equivalent polygons.
Exact Common Information
Venue: arXiv cs.IT 2014
Year: 2014

This paper introduces the notion of exact common information, which is the minimum description length of the common randomness needed for the exact distributed generation of two correlated random variables $(X,Y)$. We introduce the quantity $G(X;Y)=\min_{X\to W \to Y} H(W)$ as a natural bound on the exact common information and study its properties and computation. We then introduce the exact common information rate, which is the minimum description rate of the common randomness for the exact generation of a 2-DMS $(X,Y)$. We give a multiletter characterization for it as the limit $\bar{G}(X;Y)=\lim_{n\to \infty}(1/n)G(X^n;Y^n)$. While in general $\bar{G}(X;Y)$ is greater than or equal to the Wyner common information, we show that they are equal for the Symmetric Binary Erasure Source. We do not know, however, if the exact common information rate has a single letter characterization in general.
On the Decision Number of Graphs
Venue: arXiv cs.DM 2014
Year: 2014

Let $G$ be a graph. A good function is a function $f:V(G)\rightarrow \{-1,1\}$, satisfying $f(N(v))\geq 1$, for each $v\in V(G)$, where $ N(v)=\{u\in V(G)\, |\, uv\in E(G) \} $ and $f(S) = \sum_{u\in S} f(u)$ for every $S \subseteq V(G) $. For every cubic graph $G$ of order $ n, $ we prove that $ γ(G) \leq \frac{5n}{7} $ and show that this inequality is sharp. A function $f:V(G)\rightarrow \{-1,1\}$ is called a nice function, if $f(N[v])\le1$, for each $v\in V(G)$, where $ N[v]=\{v\} \cup N(v) $. Define $\overlineβ(G)=max\{f(V(G))\}$, where $f$ is a nice function for $G$. We show that $\overlineβ(G)\ge -\frac{3n}{7}$ for every cubic graph $G$ of order $n$, which improves the best known bound $-\frac{n}{2}$.
Probabilistic Model Validation for Uncertain Nonlinear Systems
Venue: arXiv cs.SY 2014
Year: 2014

This paper presents a probabilistic model validation methodology for nonlinear systems in time-domain. The proposed formulation is simple, intuitive, and accounts both deterministic and stochastic nonlinear systems with parametric and nonparametric uncertainties. Instead of hard invalidation methods available in the literature, a relaxed notion of validation in probability is introduced. To guarantee provably correct inference, algorithm for constructing probabilistically robust validation certificate is given along with computational complexities. Several examples are worked out to illustrate its use.
Remarks on AKS Primality Testing Algorithm and A Flaw in the Definition of P
Venue: arXiv cs.CC 2014
Year: 2014

We remark that the AKS primality testing algorithm [Annals of Mathematics 160 (2), 2004] needs about 1,000,000,000 G (gigabyte) storage space for a number of 1024 bits. The requirement is very hard to meet. The complexity class P which contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, is generally believed to be ``easy". We point out that the time is estimated only in terms of the amount of arithmetic operations. It does not comprise the time for reading and writing data on the tape in a Turing machine. The flaw makes some deterministic polynomial time algorithms impractical, and humbles the importance of P=NP question.
Classification of Complex Networks Based on Topological Properties
Venue: arXiv cs.SI 2014
Year: 2014

Complex networks are a powerful modeling tool, allowing the study of countless real-world systems. They have been used in very different domains such as computer science, biology, sociology, management, etc. Authors have been trying to characterize them using various measures such as degree distribution, transitivity or average distance. Their goal is to detect certain properties such as the small-world or scale-free properties. Previous works have shown some of these properties are present in many different systems, while others are characteristic of certain types of systems only. However, each one of these studies generally focuses on a very small number of topological measures and networks. In this work, we aim at using a more systematic approach. We first constitute a dataset of 152 publicly available networks, spanning over 7 different domains. We then process 14 different topological measures to characterize them in the most possible complete way. Finally, we apply standard data mining tools to analyze these data. A cluster analysis reveals it is possible to obtain two significantly distinct clusters of networks, corresponding roughly to a bisection of the domains modeled by the networks. On these data, the most discriminant measures are density, modularity, average degree and transitivity, and at a lesser extent, closeness and edgebetweenness centralities.Abstract--Complex networks are a powerful modeling tool, allowing the study of countless real-world systems. They have been used in very different domains such as computer science, biology, sociology, management, etc. Authors have been trying to characterize them using various measures such as degree distribution, transitivity or average distance. Their goal is to detect certain properties such as the small-world or scale-free properties. Previous works have shown some of these properties are present in many different systems, while others are characteristic of certain types of systems only. However, each one of these studies generally focuses on a very small number of topological measures and networks. In this work, we aim at using a more systematic approach. We first constitute a dataset of 152 publicly available networks, spanning over 7 different domains. We then process 14 different topological measures to characterize them in the most possible complete way. Finally, we apply standard data mining tools to analyze these data. A cluster analysis reveals it is possible to obtain two significantly distinct clusters of networks, corresponding roughly to a bisection of the domains modeled by the networks. On these data, the most discriminant measures are density, modularity, average degree and transitivity, and at a lesser extent, closeness and edgebetweenness centralities.
A Many-core Machine Model for Designing Algorithms with Minimum Parallelism Overheads
Venue: arXiv cs.DC 2014
Year: 2014

We present a model of multithreaded computation, combining fork-join and single-instruction-multiple-data parallelisms, with an emphasis on estimating parallelism overheads of programs written for modern many-core architectures. We establish a Graham-Brent theorem for this model so as to estimate execution time of programs running on a given number of streaming multiprocessors. We evaluate the benefits of our model with four fundamental algorithms from scientific computing. In each case, our model is used to minimize parallelism overheads by determining an appropriate value range for a given program parameter; moreover experimentation confirms the model's prediction.
Short and Long Supports for Constraint Propagation
Venue: arXiv cs.AI 2014
Year: 2014

Special-purpose constraint propagation algorithms frequently make implicit use of short supports -- by examining a subset of the variables, they can infer support (a justification that a variable-value pair may still form part of an assignment that satisfies the constraint) for all other variables and values and save substantial work -- but short supports have not been studied in their own right. The two main contributions of this paper are the identification of short supports as important for constraint propagation, and the introduction of HaggisGAC, an efficient and effective general purpose propagation algorithm for exploiting short supports. Given the complexity of HaggisGAC, we present it as an optimised version of a simpler algorithm ShortGAC. Although experiments demonstrate the efficiency of ShortGAC compared with other general-purpose propagation algorithms where a compact set of short supports is available, we show theoretically and experimentally that HaggisGAC is even better. We also find that HaggisGAC performs better than GAC-Schema on full-length supports. We also introduce a variant algorithm HaggisGAC-Stable, which is adapted to avoid work on backtracking and in some cases can be faster and have significant reductions in memory use. All the proposed algorithms are excellent for propagating disjunctions of constraints. In all experiments with disjunctions we found our algorithms to be faster than Constructive Or and GAC-Schema by at least an order of magnitude, and up to three orders of magnitude.