OpenRaiser/Intern-Atlas huggingface dataset:
On Modeling Geometric Joint Sink Mobility with Delay-Tolerant Cluster-less Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

Moving Sink (MS) in Wireless Sensor Networks (WSNs) has appeared as a blessing because it collects data directly from the nodes where the concept of relay nodes is becomes obsolete. There are, however, a few challenges to be taken care of, like data delay tolerance and trajectory of MS which is NP-hard. In our proposed scheme, we divide the square field in small squares. Middle point of the partitioned area is the sojourn location of the sink, and nodes around MS are in its transmission range, which send directly the sensed data in a delay-tolerant fashion. Two sinks are moving simultaneously; one inside and having four sojourn locations and other in outer trajectory having twelve sojourn locations. Introduction of the joint mobility enhances network life and ultimately throughput. As the MS comes under the NP-hard problem, we convert it into a geometric problem and define it as, Geometric Sink Movement (GSM). A set of linear programming equations has also been given in support of GSM which prolongs network life time.
Enacting Social Argumentative Machines in Semantic Wikipedia
Venue: arXiv cs.AI 2013
Year: 2013

This research advocates the idea of combining argumentation theory with the social web technology, aiming to enact large scale or mass argumentation. The proposed framework allows mass-collaborative editing of structured arguments in the style of semantic wikipedia. The long term goal is to apply the abstract machinery of argumentation theory to more practical applications based on human generated arguments, such as deliberative democracy, business negotiation, or self-care. The ARGNET system was developed based on ther Semantic MediaWiki framework and on the Argument Interchange Format (AIF) ontology.
A Markov Model for Ontology Alignment
Venue: arXiv cs.DB 2013
Year: 2013

The explosion of available data along with the need to integrate and utilize that data has led to a pressing interest in data integration techniques. In terms of Semantic Web technologies, Ontology Alignment is a key step in the process of integrating heterogeneous knowledge bases. In this paper, we present the Edge Confidence technique, a modification and improvement over the popular Similarity Flooding technique for Ontology Alignment.
Dew Point modelling using GEP based multi objective optimization
Venue: arXiv cs.NE 2013
Year: 2013

Different techniques are used to model the relationship between temperatures, dew point and relative humidity. Gene expression programming is capable of modelling complex realities with great accuracy, allowing at the same time, the extraction of knowledge from the evolved models compared to other learning algorithms. We aim to use Gene Expression Programming for modelling of dew point. Generally, accuracy of the model is the only objective used by selection mechanism of GEP. This will evolve large size models with low training error. To avoid this situation, use of multiple objectives, like accuracy and size of the model are preferred by Genetic Programming practitioners. Solution to a multi-objective problem is a set of solutions which satisfies the objectives given by decision maker. Multi objective based GEP will be used to evolve simple models. Various algorithms widely used for multi objective optimization, like NSGA II and SPEA 2, are tested on different test problems. The results obtained thereafter gives idea that SPEA 2 is better than NSGA II based on the features like execution time, number of solutions obtained and convergence rate. We selected SPEA 2 for dew point prediction. The multi-objective base GEP produces accurate and simpler (smaller) solutions compared to solutions produced by plain GEP for dew point predictions. Thus multi objective base GEP produces better solutions by considering the dual objectives of fitness and size of the solution. These simple models can be used to predict future values of dew point.
Fit and Vulnerable: Attacks and Defenses for a Health Monitoring Device
Venue: arXiv cs.CR 2013
Year: 2013

The fusion of social networks and wearable sensors is becoming increasingly popular, with systems like Fitbit automating the process of reporting and sharing user fitness data. In this paper we show that while compelling, the integration of health data into social networks is fraught with privacy and security vulnerabilities. Case in point, by reverse engineering the communication protocol, storage details and operation codes, we identified several vulnerabilities in Fitbit. We have built FitBite, a suite of tools that exploit these vulnerabilities to launch a wide range of attacks against Fitbit. Besides eavesdropping, injection and denial of service, several attacks can lead to rewards and financial gains. We have built FitLock, a lightweight defense system that protects Fitbit while imposing only a small overhead. Our experiments on BeagleBoard and Xperia devices show that FitLock's end-to-end overhead over Fitbit is only 2.4%.
Efficiency or fairness: managing applications with different delay sensitivities in heterogeneous wireless networks
Venue: arXiv cs.NI 2013
Year: 2013

In the current intensively changing technological environment, wireless network operators try to manage the increase of global traffic, optimizing the use of the available resources. This involves associating each user to one of its reachable wireless networks; a decision that can be made on the user side, in which case inefficiencies stem from user selfishness. This paper aims at correcting that efficiency loss through the use of a one-dimensional incentive signal, interpreted as a price. While the so-called Pigovian taxes allow to deal with homogeneous users, we consider here two classes with different sensitivities to the Quality of Service, reflecting the dichotomy between delay-sensitive and delay-insensitive applications. We consider a geographic area covered by two wireless networks, among which users choose based on a trade-off between the quality of service and the price to pay. Using a non-atomic routing game model, we study analytically the case of constant demand levels. We show that when properly designed, the incentives elicit efficient user-network associations. Moreover, those optimal incentives can be simply computed by the wireless operator, using only some information that is easily available. Finally, the performance of the incentive scheme under dynamic demand (users opening and closing connections over time) are investigated through simulations, our incentive scheme also yielding significant improvements in that case.
A Unified Approach to Joint and Iterative Adaptive Interference Cancellation and Parameter Estimation for CDMA Systems in Multipath Channels
Venue: arXiv cs.IT 2013
Year: 2013

This paper proposes a unified approach to joint adaptive parameter estimation and interference cancellation (IC) for direct sequence code-division-multiple-access (DS-CDMA) systems in multipath channels. A unified framework is presented in which the IC problem is formulated as an optimization problem with extra degrees of freedom of an IC parameter vector for each stage and user. We propose a joint optimization method for estimating the IC parameter vector, the linear receiver filter front-end, and the channel along with minimum mean squared error (MMSE) expressions for the estimators. Based on the proposed joint optimization approach, we derive low-complexity stochastic gradient (SG) algorithms for estimating the desired parameters. Simulation results for the uplink of a synchronous DS-CDMA system show that the proposed methods significantly outperform the best known IC receivers.
Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs
Venue: arXiv cs.DS 2013
Year: 2013

Bhawalkar, Kleinberg, Lewi, Roughgarden, and Sharma [ICALP 2012] introduced the Anchored k-Core problem, where the task is for a given graph G and integers b, k, and p to find an induced subgraph H with at least p vertices (the core) such that all but at most b vertices (called anchors) of H are of degree at least k. In this paper, we extend the notion of k-core to directed graphs and provide a number of new algorithmic and complexity results for the directed version of the problem. We show that - The decision version of the problem is NP-complete for every k>=1 even if the input graph is restricted to be a planar directed acyclic graph of maximum degree at most k+2. - The problem is fixed parameter tractable (FPT) parameterized by the size of the core p for k=1, and W[1]-hard for k>=2. - When the maximum degree of the graph is at most Δ, the problem is FPT parameterized by p+Δif k>= Δ/2.
Bayesian crack detection in ultra high resolution multimodal images of paintings
Venue: arXiv cs.CV 2013
Year: 2013

The preservation of our cultural heritage is of paramount importance. Thanks to recent developments in digital acquisition techniques, powerful image analysis algorithms are developed which can be useful non-invasive tools to assist in the restoration and preservation of art. In this paper we propose a semi-supervised crack detection method that can be used for high-dimensional acquisitions of paintings coming from different modalities. Our dataset consists of a recently acquired collection of images of the Ghent Altarpiece (1432), one of Northern Europe's most important art masterpieces. Our goal is to build a classifier that is able to discern crack pixels from the background consisting of non-crack pixels, making optimal use of the information that is provided by each modality. To accomplish this we employ a recently developed non-parametric Bayesian classifier, that uses tensor factorizations to characterize any conditional probability. A prior is placed on the parameters of the factorization such that every possible interaction between predictors is allowed while still identifying a sparse subset among these predictors. The proposed Bayesian classifier, which we will refer to as conditional Bayesian tensor factorization or CBTF, is assessed by visually comparing classification results with the Random Forest (RF) algorithm.
On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
Venue: arXiv cs.CC 2013
Year: 2013

Assuming the Generalised Riemann Hypothesis (GRH), we show that for all k, there exist polynomials with coefficients in $\MA$ having no arithmetic circuits of size O(n^k) over the complex field (allowing any complex constant). We also build a family of polynomials that can be evaluated in AM having no arithmetic circuits of size O(n^k). Then we investigate the link between fixed-polynomial size circuit bounds in the Boolean and arithmetic settings. In characteristic zero, it is proved that $\NP \not\subset \size(n^k)$, or $\MA \subset \size(n^k)$, or NP=MA imply lower bounds on the circuit size of uniform polynomials in n variables from the class VNP over the complex field, assuming GRH. In positive characteristic p, uniform polynomials in VNP have circuits of fixed-polynomial size if and only if both VP=VNP over F_p and Mod_pP has circuits of fixed-polynomial size.
Backdoors to Abduction
Venue: arXiv cs.AI 2013
Year: 2013

Abductive reasoning (or Abduction, for short) is among the most fundamental AI reasoning methods, with a broad range of applications, including fault diagnosis, belief revision, and automated planning. Unfortunately, Abduction is of high computational complexity; even propositional Abduction is Σ_2^P-complete and thus harder than NP and coNP. This complexity barrier rules out the existence of a polynomial transformation to propositional satisfiability (SAT). In this work we use structural properties of the Abduction instance to break this complexity barrier. We utilize the problem structure in terms of small backdoor sets. We present fixed-parameter tractable transformations from Abduction to SAT, which make the power of today's SAT solvers available to Abduction.
SW# - GPU enabled exact alignments on genome scale
Venue: arXiv cs.DC 2013
Year: 2013

Sequence alignment is one of the oldest and the most famous problems in bioinformatics. Even after 45 years, for one reason or another, this problem is still actual; current solutions are trade-offs between execution time, memory consumption and accuracy. We purpose SW#, a new CUDA GPU enabled and memory efficient implementation of dynamic programming algorithms for local alignment. In this implementation indels are treated using the affine gap model. Although there are other GPU implementations of the Smith-Waterman algorithm, SW# is the only publicly available implementation that can produce sequence alignments on genome-wide scale. For long sequences, our implementation is at least a few hundred times faster than a CPU version of the same algorithm.
Three Generalizations of the FOCUS Constraint
Venue: arXiv cs.AI 2013
Year: 2013

The FOCUS constraint expresses the notion that solutions are concentrated. In practice, this constraint suffers from the rigidity of its semantics. To tackle this issue, we propose three generalizations of the FOCUS constraint. We provide for each one a complete filtering algorithm as well as discussing decompositions.
Robust Polyhedral Regularization
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we establish robustness to noise perturbations of polyhedral regularization of linear inverse problems. We provide a sufficient condition that ensures that the polyhedral face associated to the true vector is equal to that of the recovered one. This criterion also implies that the $\ell^2$ recovery error is proportional to the noise level for a range of parameter. Our criterion is expressed in terms of the hyperplanes supporting the faces of the unit polyhedral ball of the regularization. This generalizes to an arbitrary polyhedral regularization results that are known to hold for sparse synthesis and analysis $\ell^1$ regularization which are encompassed in this framework. As a byproduct, we obtain recovery guarantees for $\ell^\infty$ and $\ell^1-\ell^\infty$ regularization.
Network Coding-Based Link Failure Recovery over Large Arbitrary Networks
Venue: arXiv cs.NI 2013
Year: 2013

Network coding-based link failure recovery techniques provide near-hitless recovery and offer high capacity efficiency. Diversity coding is the first technique to incorporate coding in this field and is easy to implement over small arbitrary networks. However, its capacity efficiency is restricted by its systematic coding and high design complexity even though it has lower complexity than the other coding-based recovery techniques. Alternative techniques mitigate some of these limitations, but they are difficult to implement over arbitrary networks. In this paper, we propose a novel non-systematic coding technique and a simple design algorithm to implement the diversity coding-based (or network coding-based) recovery over arbitrary networks. The design framework consists of two parts. An ILP formulation for each part is developed. The simulation results suggest that both the novel coding structure and the novel design algorithm lead to higher capacity efficiency for near-hitless recovery. The new design algorithm is able to achieve optimal results in large arbitrary networks.
Outage Probability in Arbitrarily-Shaped Finite Wireless Networks
Venue: arXiv cs.IT 2013
Year: 2013

This paper analyzes the outage performance in finite wireless networks. Unlike most prior works, which either assumed a specific network shape or considered a special location of the reference receiver, we propose two general frameworks for analytically computing the outage probability at any arbitrary location of an arbitrarily-shaped finite wireless network: (i) a moment generating function-based framework which is based on the numerical inversion of the Laplace transform of a cumulative distribution and (ii) a reference link power gain-based framework which exploits the distribution of the fading power gain between the reference transmitter and receiver. The outage probability is spatially averaged over both the fading distribution and the possible locations of the interferers. The boundary effects are accurately accounted for using the probability distribution function of the distance of a random node from the reference receiver. For the case of the node locations modeled by a Binomial point process and Nakagami-$m$ fading channel, we demonstrate the use of the proposed frameworks to evaluate the outage probability at any location inside either a disk or polygon region. The analysis illustrates the location dependent performance in finite wireless networks and highlights the importance of accurately modeling the boundary effects.
Interprocedural Data Flow Analysis in Soot using Value Contexts
Venue: arXiv cs.PL 2013
Year: 2013

An interprocedural analysis is precise if it is flow sensitive and fully context-sensitive even in the presence of recursion. Many methods of interprocedural analysis sacrifice precision for scalability while some are precise but limited to only a certain class of problems. Soot currently supports interprocedural analysis of Java programs using graph reachability. However, this approach is restricted to IFDS/IDE problems, and is not suitable for general data flow frameworks such as heap reference analysis and points-to analysis which have non-distributive flow functions. We describe a general-purpose interprocedural analysis framework for Soot using data flow values for context-sensitivity. This framework is not restricted to problems with distributive flow functions, although the lattice must be finite. It combines the key ideas of the tabulation method of the functional approach and the technique of value-based termination of call string construction. The efficiency and precision of interprocedural analyses is heavily affected by the precision of the underlying call graph. This is especially important for object-oriented languages like Java where virtual method invocations cause an explosion of spurious call edges if the call graph is constructed naively. We have instantiated our framework with a flow and context-sensitive points-to analysis in Soot, which enables the construction of call graphs that are far more precise than those constructed by Soot's SPARK engine.
Learning Visual Symbols for Parsing Human Poses in Images
Venue: arXiv cs.CV 2013
Year: 2013

Parsing human poses in images is fundamental in extracting critical visual information for artificial intelligent agents. Our goal is to learn self-contained body part representations from images, which we call visual symbols, and their symbol-wise geometric contexts in this parsing process. Each symbol is individually learned by categorizing visual features leveraged by geometric information. In the categorization, we use Latent Support Vector Machine followed by an efficient cross validation procedure to learn visual symbols. Then, these symbols naturally define geometric contexts of body parts in a fine granularity. When the structure of the compositional parts is a tree, we derive an efficient approach to estimating human poses in images. Experiments on two large datasets suggest our approach outperforms state of the art methods.
Unifying and generalizing known lower bounds via geometric complexity theory
Venue: arXiv cs.CC 2013
Year: 2013

We show that most arithmetic circuit lower bounds and relations between lower bounds naturally fit into the representation-theoretic framework suggested by geometric complexity theory (GCT), including: the partial derivatives technique (Nisan-Wigderson), the results of Razborov and Smolensky on $AC^0[p]$, multilinear formula and circuit size lower bounds (Raz et al.), the degree bound (Strassen, Baur-Strassen), the connected components technique (Ben-Or), depth 3 arithmetic circuit lower bounds over finite fields (Grigoriev-Karpinski), lower bounds on permanent versus determinant (Mignon-Ressayre, Landsberg-Manivel-Ressayre), lower bounds on matrix multiplication (Bürgisser-Ikenmeyer) (these last two were already known to fit into GCT), the chasms at depth 3 and 4 (Gupta-Kayal-Kamath-Saptharishi; Agrawal-Vinay; Koiran), matrix rigidity (Valiant) and others. That is, the original proofs, with what is often just a little extra work, already provide representation-theoretic obstructions in the sense of GCT for their respective lower bounds. This enables us to expose a new viewpoint on GCT, whereby it is a natural unification and broad generalization of known results. It also shows that the framework of GCT is at least as powerful as known methods, and gives many new proofs-of-concept that GCT can indeed provide significant asymptotic lower bounds. This new viewpoint also opens up the possibility of fruitful two-way interactions between previous results and the new methods of GCT; we provide several concrete suggestions of such interactions. For example, the representation-theoretic viewpoint of GCT naturally provides new properties to consider in the search for new lower bounds.
On independence domination
Venue: arXiv cs.DM 2013
Year: 2013

Let G be a graph. The independence-domination number is the maximum over all independent sets I in G of the minimal number of vertices needed to dominate I. In this paper we investigate the computational complexity of independence domination for graphs in several graph classes related to cographs. We present an exact exponential algorithm. We also present a PTAS for planar graphs.
Secure On-Off Transmission Design with Channel Estimation Errors
Venue: arXiv cs.IT 2013
Year: 2013

Physical layer security has recently been regarded as an emerging technique to complement and improve the communication security in future wireless networks. The current research and development in physical layer security is often based on the ideal assumption of perfect channel knowledge or the capability of variable-rate transmissions. In this work, we study the secure transmission design in more practical scenarios by considering channel estimation errors at the receiver and investigating both fixed-rate and variable-rate transmissions. Assuming quasi-static fading channels, we design secure on-off transmission schemes to maximize the throughput subject to a constraint on secrecy outage probability. For systems with given and fixed encoding rates, we show how the optimal on-off transmission thresholds and the achievable throughput vary with the amount of knowledge on the eavesdropper's channel. In particular, our design covers the interesting case where the eavesdropper also uses the pilots sent from the transmitter to obtain imperfect channel estimation. An interesting observation is that using too much pilot power can harm the throughput of secure transmission if both the legitimate receiver and the eavesdropper have channel estimation errors, while the secure transmission always benefits from increasing pilot power when only the legitimate receiver has channel estimation errors but not the eavesdropper. When the encoding rates are controllable parameters to design, we further derive both a non-adaptive and an adaptive rate transmission schemes by jointly optimizing the encoding rates and the on-off transmission thresholds to maximize the throughput of secure transmissions.
Can P2P Networks be Super-Scalable?
Venue: arXiv cs.NI 2013
Year: 2013

We propose a new model for peer-to-peer networking which takes the network bottlenecks into account beyond the access. This model can cope with key features of P2P networking like degree or locality constraints together with the fact that distant peers often have a smaller rate than nearby peers. Using a network model based on rate functions, we give a closed form expression of peers download performance in the system's fluid limit, as well as approximations for the other cases. Our results show the existence of realistic settings for which the average download time is a decreasing function of the load, a phenomenon that we call super-scalability.