OpenRaiser/Intern-Atlas huggingface dataset:
Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication
Venue: arXiv cs.CC 2012
Year: 2012

In this paper we study quantum nondeterminism in multiparty communication. There are three (possibly) different types of nondeterminism in quantum computation: i) strong, ii) weak with classical proofs, and iii) weak with quantum proofs. Here we focus on the first one. A strong quantum nondeterministic protocol accepts a correct input with positive probability, and rejects an incorrect input with probability 1. In this work we relate strong quantum nondeterministic multiparty communication complexity to the rank of the communication tensor in the Number-On-Forehead and Number-In-Hand models. In particular, by extending the definition proposed by de Wolf to {\it nondeterministic tensor-rank} ($nrank$), we show that for any boolean function $f$ when there is no prior shared entanglement between the players, 1) in the Number-On-Forehead model, the cost is upper-bounded by the logarithm of $nrank(f)$; 2) in the Number-In-Hand model, the cost is lower-bounded by the logarithm of $nrank(f)$. Furthermore, we show that when the number of players is $o(\log\log n)$ we have that $NQP\nsubseteq BQP$ for Number-On-Forehead communication.
Principal Component Pursuit with Reduced Linear Measurements
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we study the problem of decomposing a superposition of a low-rank matrix and a sparse matrix when a relatively few linear measurements are available. This problem arises in many data processing tasks such as aligning multiple images or rectifying regular texture, where the goal is to recover a low-rank matrix with a large fraction of corrupted entries in the presence of nonlinear domain transformation. We consider a natural convex heuristic to this problem which is a variant to the recently proposed Principal Component Pursuit. We prove that under suitable conditions, this convex program guarantees to recover the correct low-rank and sparse components despite reduced measurements. Our analysis covers both random and deterministic measurement models.
Outage Constrained Secrecy Rate Maximization Using Cooperative Jamming
Venue: arXiv cs.IT 2012
Year: 2012

We consider a Gaussian MISO wiretap channel, where a multi-antenna source communicates with a single-antenna destination in the presence of a single-antenna eavesdropper. The communication is assisted by multi-antenna helpers that act as jammers to the eavesdropper. Each helper independently transmits noise which lies in the null space of the channel to the destination, thus creates no interference to the destination. Under the assumption that there is eavesdropper channel uncertainty, we derive the optimal covariance matrix for the source signal so that the secrecy rate is maximized subject to probability of outage and power constraints. Assuming that the eavesdropper channels follow zero-mean Gaussian model with known covariances, we derive the outage probability in a closed form. Simulation results in support of the analysis are provided.
Towards an Integrated Visualization Of Semantically Enriched 3D City Models: An Ontology of 3D Visualization Techniques
Venue: arXiv cs.AI 2012
Year: 2012

3D city models - which represent in 3 dimensions the geometric elements of a city - are increasingly used for an intended wide range of applications. Such uses are made possible by using semantically enriched 3D city models and by presenting such enriched 3D city models in a way that allows decision-making processes to be carried out from the best choices among sets of objectives, and across issues and scales. In order to help in such a decision-making process we have defined a framework to find the best visualization technique(s) for a set of potentially heterogeneous data that have to be visualized within the same 3D city model, in order to perform a given task in a specific context. We have chosen an ontology-based approach. This approach and the specification and use of the resulting ontology of 3D visualization techniques are described in this paper.
Aspects of SOA: An Entry Point for Starters
Venue: arXiv cs.SE 2012
Year: 2012

Because Service-Oriented Architecture (SOA) is one of the hottest topics that is currently gaining momentum, and the number of its adopters (both business and IT executives) is increasing in a tremendous manner, it is really a must to enlist important aspects related to it in order to allow these adopters to better understand the role that it can play in both software and business markets. These aspects varies from the definition of SOA and key components of it, different forms of support given by elite software vendors to it, its evolution history, the relationship between it and web services, the future expectations about its uses and benefits in different organizations, the relationship between SOA and Enterprise Application Integration (EAI), and various applications that can use it to overcome limitations related to other traditional methods. Moreover, challenges that face SOA in software market should be addressed and discussed in order to be able to see the big picture and to look for better solutions for them.
Deterministic parameterized connected vertex cover
Venue: arXiv cs.DS 2012
Year: 2012

In the Connected Vertex Cover problem we are given an undirected graph G together with an integer k and we are to find a subset of vertices X of size at most k, such that X contains at least one end-point of each edge and moreover X induces a connected subgraph. For this problem we present a deterministic algorithm running in O(2^k n^O(1)) time and polynomial space, improving over previously best O(2.4882^k n^O(1)) deterministic algorithm and O(2^k n^O(1)) randomized algorithm. Furthermore, when usage of exponential space is allowed, we present an O(2^k k(n+m)) time algorithm that solves a more general variant with arbitrary real weights. Finally, we show that in O(2k k(n + m)) time and O(2^k k) space one can count the number of connected vertex covers of size at most k, which can not be improved to O((2 - eps)^k nO(1)) for any eps > 0 under the Strong Exponential Time Hypothesis, as shown by Cygan et al. [CCC'12].
Independent signaling achieves the capacity region of the Gaussian interference channel with common information to within one bit
Venue: arXiv cs.IT 2012
Year: 2012

The interference channel with common information (IC-CI) consists of two transmit-receive pairs that communicate over a common noisy medium. Each transmitter has an individual message for its paired receiver, and additionally, both transmitters have a common message to deliver to both receivers. In this paper, through explicit inner and outer bounds on the capacity region, we establish the capacity region of the Gaussian IC-CI to within a bounded gap of one bit, independently of the values of all channel parameters. Using this constant-gap characterization, the generalized degrees of freedom (GDoF) region is determined. It is shown that the introduction of the common message leads to an increase in the GDoF over that achievable over the Gaussian interference channel without a common message, and hence to an unbounded improvement in the achievable rate. A surprising feature of the capacity-within-one-bit result is that most of the available benefit (i.e., to within one bit of capacity) due to the common message is achieved through a simple and explicit coding scheme that involves independent signaling at the two transmitters so that, in effect, this scheme forgoes the opportunity for transmitter cooperation that is inherently available due to shared knowledge of the common message at both transmitters.
Dense Subgraph Maintenance under Streaming Edge Weight Updates for Real-time Story Identification
Venue: arXiv cs.DB 2012
Year: 2012

Recent years have witnessed an unprecedented proliferation of social media. People around the globe author, every day, millions of blog posts, social network status updates, etc. This rich stream of information can be used to identify, on an ongoing basis, emerging stories, and events that capture popular attention. Stories can be identified via groups of tightly-coupled real-world entities, namely the people, locations, products, etc., that are involved in the story. The sheer scale, and rapid evolution of the data involved necessitate highly efficient techniques for identifying important stories at every point of time. The main challenge in real-time story identification is the maintenance of dense subgraphs (corresponding to groups of tightly-coupled entities) under streaming edge weight updates (resulting from a stream of user-generated content). This is the first work to study the efficient maintenance of dense subgraphs under such streaming edge weight updates. For a wide range of definitions of density, we derive theoretical results regarding the magnitude of change that a single edge weight update can cause. Based on these, we propose a novel algorithm, DYNDENS, which outperforms adaptations of existing techniques to this setting, and yields meaningful results. Our approach is validated by a thorough experimental evaluation on large-scale real and synthetic datasets.
Cake Cutting Mechanisms
Venue: arXiv cs.GT 2012
Year: 2012

We examine the history of cake cutting mechanisms and discuss the efficiency of their allocations. In the case of piecewise uniform preferences, we define a game that in the presence of strategic agents has equilibria that are not dominated by the allocations of any mechanism. We identify that the equilibria of this game coincide with the allocations of an existing cake cutting mechanism.
Optimal Mix of Incentive Strategies for Product Marketing on Social Networks
Venue: arXiv cs.SI 2012
Year: 2012

We consider the problem of devising incentive strategies for viral marketing of a product. In particular, we assume that the seller can influence penetration of the product by offering two incentive programs: a) direct incentives to potential buyers (influence) and b) referral rewards for customers who influence potential buyers to make the purchase (exploit connections). The problem is to determine the optimal timing of these programs over a finite time horizon. In contrast to algorithmic perspective popular in the literature, we take a mean-field approach and formulate the problem as a continuous-time deterministic optimal control problem. We show that the optimal strategy for the seller has a simple structure and can take both forms, namely, influence-and-exploit and exploit-and-influence. We also show that in some cases it may optimal for the seller to deploy incentive programs mostly for low degree nodes. We support our theoretical results through numerical studies and provide practical insights by analyzing various scenarios.
An Interface using SOA Framework For Mediclaim Provider
Venue: arXiv cs.SE 2012
Year: 2012

SOA brought new opportunities for the long expected agility, reuse and the adaptive capability of information technology to the ever changing business requirements and environments. The purpose of this paper is to describe the implementation of Medical Insurance Claim Process Model using SOA. We adopt Service Oriented Architecture (SOA) to reduce the complexity among systems and solve data consistency problems among services. We choose n-tier and Service-Oriented Architecture (SOA) as our system environment. This model can also establish a potentially new innovative market branch for the insurance industry.
Sleep Deprivation Attack Detection in Wireless Sensor Network
Venue: arXiv cs.NI 2012
Year: 2012

Deployment of sensor network in hostile environment makes it mainly vulnerable to battery drainage attacks because it is impossible to recharge or replace the battery power of sensor nodes. Among different types of security threats, low power sensor nodes are immensely affected by the attacks which cause random drainage of the energy level of sensors, leading to death of the nodes. The most dangerous type of attack in this category is sleep deprivation, where target of the intruder is to maximize the power consumption of sensor nodes, so that their lifetime is minimized. Most of the existing works on sleep deprivation attack detection involve a lot of overhead, leading to poor throughput. The need of the day is to design a model for detecting intrusions accurately in an energy efficient manner. This paper proposes a hierarchical framework based on distributed collaborative mechanism for detecting sleep deprivation torture in wireless sensor network efficiently. Proposed model uses anomaly detection technique in two steps to reduce the probability of false intrusion.
A Survey of Recent Intrusion Detection Systems for Wireless Sensor Network
Venue: arXiv cs.NI 2012
Year: 2012

Security of Wireless sensor network (WSN) becomes a very important issue with the rapid development of WSN that is vulnerable to a wide range of attacks due to deployment in the hostile environment and having limited resources. Intrusion detection system is one of the major and efficient defensive methods against attacks in WSN. A particularly devastating attack is the sleep deprivation attack, where a malicious node forces legitimate nodes to waste their energy by resisting the sensor nodes from going into low power sleep mode. The goal of this attack is to maximize the power consumption of the target node, thereby decreasing its battery life. Existing works on sleep deprivation attack have mainly focused on mitigation using MAC based protocols, such as S-MAC, T-MAC, B-MAC, etc. In this article, a brief review of some of the recent intrusion detection systems in wireless sensor network environment is presented. Finally, we propose a framework of cluster based layered countermeasure that can efficiently mitigate sleep deprivation attack in WSN. Simulation results on MATLAB exhibit the effectiveness of the proposed model in detecting sleep-deprivation attacks.
On Compositional Reasoning for Guaranteeing Probabilistic Properties
Venue: arXiv cs.SE 2012
Year: 2012

We present a framework to formally describe probabilistic system behavior and symbolically reason about it. In particular we aim at reasoning about possible failures and fault tolerance. We regard systems which are composed of different units: sensors, computational parts and actuators. Considering worst-case failure behavior of system components, our framework is most suited to derive reliability guarantees for composed systems. The behavior of system components is modeled using monad like constructs that serve as an abstract representation for system behavior. We introduce rules to reason about these representations and derive results like guaranteed upper bounds for system failure. Our approach is characterized by the fact that we do not just map a certain component to a failure probability, but regard distributions of error behavior and their evolvement over system runs. This serves as basis for deriving probabilities of events, in particular failure probabilities. The work presented in this paper slightly extends a complete framework and a case study which has been previously published. One focus of this report is a more detailed explanation of definitions and a more comprehensive description of examples.
"openness of search engine": A critical flaw in search systems; a case study on google, yahoo and bing
Venue: arXiv cs.CY 2012
Year: 2012

There is no doubt that Search Engines are playing a great role in Internet usage. But all the top search engines Google, Yahoo and Bing are having a critical flaw called "Openness of a Search Engine". An Internet user should be allowed to get the search results only when requested through Search engine's web page but the user must not be allowed to get the search results when requested through any web page that does not belong to the Search Engine. Only results of a search engine should be available to the Internet user but not the Search Engine. This paper explains the critical flaw called "Openness of Search Engine" with a case study on top 3 search engines 'Google', 'Yahoo' and 'Bing'. This paper conducts an attack based test using J2EE framework and proves that 'Google' passed the test and it strongly protects its Critical Search System, where 'Yahoo' and 'Bing' are failed to protect their Search Engines. But previously 'Google' also had other high severity issues with the Openness of search engine; this paper reveals those issues also. Finally this paper appeals strongly to the all top Search Engines to fix their critical flaws of "Openness of Search Engine".
Multi-Level Feature Descriptor for Robust Texture Classification via Locality-Constrained Collaborative Strategy
Venue: arXiv cs.CV 2012
Year: 2012

This paper introduces a simple but highly efficient ensemble for robust texture classification, which can effectively deal with translation, scale and changes of significant viewpoint problems. The proposed method first inherits the spirit of spatial pyramid matching model (SPM), which is popular for encoding spatial distribution of local features, but in a flexible way, partitioning the original image into different levels and incorporating different overlapping patterns of each level. This flexible setup helps capture the informative features and produces sufficient local feature codes by some well-chosen aggregation statistics or pooling operations within each partitioned region, even when only a few sample images are available for training. Then each texture image is represented by several orderless feature codes and thereby all the training data form a reliable feature pond. Finally, to take full advantage of this feature pond, we develop a collaborative representation-based strategy with locality constraint (LC-CRC) for the final classification, and experimental results on three well-known public texture datasets demonstrate the proposed approach is very competitive and even outperforms several state-of-the-art methods. Particularly, when only a few samples of each category are available for training, our approach still achieves very high classification performance.
Multiservice Telecommunication Systems Parametrical Synthesis by using of Multilayer Graph Mathematical Model
Venue: arXiv cs.NI 2012
Year: 2012

This study is devoted to the problem of parametric synthesis of multi-service telecommunication sys-tems. The main characteristics of telecommunication systems, which are brought to account in an article, are multilayer structure formed by the overlayed networks and presence flows with self-similarity effect. For accounting these features of modern telecommunications systems is proposed to use a multi-layered graph for describing the system structure, and self-similar processes model for modeling flows in a network. Solution of parametric synthesis problem is reduced to a nonlinear programming problem which is solved by using gradient descent method.
Establishing linguistic conventions in task-oriented primeval dialogue
Venue: arXiv cs.CL 2012
Year: 2012

In this paper, we claim that language is likely to have emerged as a mechanism for coordinating the solution of complex tasks. To confirm this thesis, computer simulations are performed based on the coordination task presented by Garrod & Anderson (1987). The role of success in task-oriented dialogue is analytically evaluated with the help of performance measurements and a thorough lexical analysis of the emergent communication system. Simulation results confirm a strong effect of success mattering on both reliability and dispersion of linguistic conventions.
Describing and Modeling of Video-on-Demand Service with the Usage of Multi-Layer Graph
Venue: arXiv cs.NI 2012
Year: 2012

Considered in this paper is the method of describingc of telecommunications systems providing VoD service using multi-layer graph. The paper describes the relations between the structural elements at each hierarchical level of the multi-layer graph. Transfer of video is a resource consuming task, and it requires an optimal configuration of the studied system. The usage of the multi-layer graph makes it possible to consider the telecommunication system as a whole and avoid falling in the local optimums when solving optimization problems.
Expressing Preferences using Preference Set Constraint Atoms
Venue: arXiv cs.LO 2012
Year: 2012

This paper introduces an extension of Answer Set Programming called Preference Set Constraint Programming which is a convenient and general formalism to reason with preferences. PSC programming extends Set Constraint Programming introduced by Marek and Remmel (Marek and Remmel 2004) by introducing two types of preference set constraint atoms, measure preference set constraint atoms and pre-ordered preference set constraint atoms, which are extensions of set constraint atoms. We show that the question of whether a PSC program has a preferred stable model is CoNP-complete. We give examples of the uses of the preference set constraint atoms and show that Answer Set Optimization (Brewka, Niemelä, and Truszczynski 2003) and General Preference (Son and Pontelli 2006) can be expressed using preference set constraint atoms.
Contribution of Case Based Reasoning (CBR) in the Exploitation of Return of Experience. Application to Accident Scenarii in Railroad Transport
Venue: arXiv cs.AI 2012
Year: 2012

The study is from a base of accident scenarii in rail transport (feedback) in order to develop a tool to share build and sustain knowledge and safety and secondly to exploit the knowledge stored to prevent the reproduction of accidents / incidents. This tool should ultimately lead to the proposal of prevention and protection measures to minimize the risk level of a new transport system and thus to improve safety. The approach to achieving this goal largely depends on the use of artificial intelligence techniques and rarely the use of a method of automatic learning in order to develop a feasibility model of a software tool based on case based reasoning (CBR) to exploit stored knowledge in order to create know-how that can help stimulate domain experts in the task of analysis, evaluation and certification of a new system.
Cooperative Compute-and-Forward
Venue: arXiv cs.IT 2012
Year: 2012

We examine the benefits of user cooperation under compute-and-forward. Much like in network coding, receivers in a compute-and-forward network recover finite-field linear combinations of transmitters' messages. Recovery is enabled by linear codes: transmitters map messages to a linear codebook, and receivers attempt to decode the incoming superposition of signals to an integer combination of codewords. However, the achievable computation rates are low if channel gains do not correspond to a suitable linear combination. In response to this challenge, we propose a cooperative approach to compute-and-forward. We devise a lattice-coding approach to block Markov encoding with which we construct a decode-and-forward style computation strategy. Transmitters broadcast lattice codewords, decode each other's messages, and then cooperatively transmit resolution information to aid receivers in decoding the integer combinations. Using our strategy, we show that cooperation offers a significant improvement both in the achievable computation rate and in the diversity-multiplexing tradeoff.