OpenRaiser/Intern-Atlas huggingface dataset:
Cyber-Insurance in Internet Security: A Dig into the Information Asymmetry Problem
Venue: arXiv cs.CR 2012
Year: 2012

Internet users such as individuals and organizations are subject to different types of epidemic risks such as worms, viruses, spams, and botnets. To reduce the probability of risk, an Internet user generally invests in traditional security mechanisms like anti-virus and anti-spam software, sometimes also known as \emph{self-defense} mechanisms. However, according to security experts, such software (and their subsequent advancements) will not completely eliminate risk. Recent research efforts have considered the problem of residual risk elimination by proposing the idea of \emph{cyber-insurance}. In this regard, an important research problem is resolving information asymmetry issues associated with cyber-insurance contracts. In this paper we propose \emph{three} mechanisms to resolve information asymmetry in cyber-insurance. Our mechanisms are based on the \emph{Principal-Agent} (PA) model in microeconomic theory. We show that (1) optimal cyber-insurance contracts induced by our mechanisms only provide partial coverage to the insureds. This ensures greater self-defense efforts on the part of the latter to protect their computing systems, which in turn increases overall network security, (2) the level of deductible per network user contract increases in a concave manner with the topological degree of the user, and (3) a market for cyber-insurance can be made to exist in the presence of monopolistic insurers under effective mechanism design. Our methodology is applicable to any distributed network scenario in which a framework for cyber-insurance can be implemented.
Toroidal maps : Schnyder woods, orthogonal surfaces and straight-line representations
Venue: arXiv cs.DM 2012
Year: 2012

A Schnyder wood is an orientation and coloring of the edges of a planar map satisfying a simple local property. We propose a generalization of Schnyder woods to graphs embedded on the torus with application to graph drawing. We prove several properties on this new object. Among all we prove that a graph embedded on the torus admits such a Schnyder wood if and only if it is an essentially 3-connected toroidal map. We show that these Schnyder woods can be used to embed the universal cover of an essentially 3-connected toroidal map on an infinite and periodic orthogonal surface. Finally we use this embedding to obtain a straight-line flat torus representation of any toroidal map in a polynomial size grid.
Type-elimination-based reasoning for the description logic SHIQbs using decision diagrams and disjunctive datalog
Venue: arXiv cs.LO 2012
Year: 2012

We propose a novel, type-elimination-based method for reasoning in the description logic SHIQbs including DL-safe rules. To this end, we first establish a knowledge compilation method converting the terminological part of an ALCIb knowledge base into an ordered binary decision diagram (OBDD) which represents a canonical model. This OBDD can in turn be transformed into disjunctive Datalog and merged with the assertional part of the knowledge base in order to perform combined reasoning. In order to leverage our technique for full SHIQbs, we provide a stepwise reduction from SHIQbs to ALCIb that preserves satisfiability and entailment of positive and negative ground facts. The proposed technique is shown to be worst case optimal w.r.t. combined and data complexity and easily admits extensions with ground conjunctive queries.
The weighted words collector
Venue: arXiv cs.DM 2012
Year: 2012

Motivated by applications in bioinformatics, we consider the word collector problem, i.e. the expected number of calls to a random weighted generator of words of length $n$ before the full collection is obtained. The originality of this instance of the non-uniform coupon collector lies in the, potentially large, multiplicity of the words/coupons of a given probability/composition. We obtain a general theorem that gives an asymptotic equivalent for the expected waiting time of a general version of the Coupon Collector. This theorem is especially well-suited for classes of coupons featuring high multiplicities. Its application to a given language essentially necessitates some knowledge on the number of words of a given composition/probability. We illustrate the application of our theorem, in a step-by-step fashion, on three exemplary languages, revealing asymptotic regimes in $Θ(μ(n)\cdot n)$ and $Θ(μ(n)\cdot \log n)$, where $μ(n)$ is the sum of weights over words of length $n$.
OWL: Yet to arrive on the Web of Data?
Venue: arXiv cs.DL 2012
Year: 2012

Seven years on from OWL becoming a W3C recommendation, and two years on from the more recent OWL 2 W3C recommendation, OWL has still experienced only patchy uptake on the Web. Although certain OWL features (like owl:sameAs) are very popular, other features of OWL are largely neglected by publishers in the Linked Data world. This may suggest that despite the promise of easy implementations and the proposal of tractable profiles suggested in OWL's second version, there is still no "right" standard fragment for the Linked Data community. In this paper, we (1) analyse uptake of OWL on the Web of Data, (2) gain insights into the OWL fragment that is actually used/usable on the Web, where we arrive at the conclusion that this fragment is likely to be a simplified profile based on OWL RL, (3) propose and discuss such a new fragment, which we call OWL LD (for Linked Data).
Considering a resource-light approach to learning verb valencies
Venue: arXiv cs.CL 2012
Year: 2012

Here we describe work on learning the subcategories of verbs in a morphologically rich language using only minimal linguistic resources. Our goal is to learn verb subcategorizations for Quechua, an under-resourced morphologically rich language, from an unannotated corpus. We compare results from applying this approach to an unannotated Arabic corpus with those achieved by processing the same text in treebank form. The original plan was to use only a morphological analyzer and an unannotated corpus, but experiments suggest that this approach by itself will not be effective for learning the combinatorial potential of Arabic verbs in general. The lower bound on resources for acquiring this information is somewhat higher, apparently requiring a a part-of-speech tagger and chunker for most languages, and a morphological disambiguater for Arabic.
Causal graph dynamics
Venue: arXiv cs.DM 2012
Year: 2012

We extend the theory of Cellular Automata to arbitrary, time-varying graphs. In other words we formalize, and prove theorems about, the intuitive idea of a labelled graph which evolves in time - but under the natural constraint that information can only ever be transmitted at a bounded speed, with respect to the distance given by the graph. The notion of translation-invariance is also generalized. The definition we provide for these "causal graph dynamics" is simple and axiomatic. The theorems we provide also show that it is robust. For instance, causal graph dynamics are stable under composition and under restriction to radius one. In the finite case some fundamental facts of Cellular Automata theory carry through: causal graph dynamics admit a characterization as continuous functions, and they are stable under inversion. The provided examples suggest a wide range of applications of this mathematical object, from complex systems science to theoretical physics. KEYWORDS: Dynamical networks, Boolean networks, Generative networks automata, Cayley cellular automata, Graph Automata, Graph rewriting automata, Parallel graph transformations, Amalgamated graph transformations, Time-varying graphs, Regge calculus, Local, No-signalling.
Optimum Power Allocations for Fading Decode-and-Forward Relay Channel
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, for a fading decode-and-forward full-duplex relay channel, we analytically derive optimum power allocations. Individual power constraints for the source and the relay are assumed and the related optimization problem is analyzed for two scenarios. First, optimization is taken over the source power, the relay power, and the correlation coefficient between the transmitted signals of the source and the relay. Then, for a fixed value of correlation coefficient, the optimization problem is analyzed. It is also proven that the optimization problems are convex for these two scenarios. Finally, implications of theoretical results are discussed through simulations for each scenario.
Regular Languages are Church-Rosser Congruential
Venue: arXiv cs.FL 2012
Year: 2012

This paper proves a long standing conjecture in formal language theory. It shows that all regular languages are Church-Rosser congruential. The class of Church-Rosser congruential languages was introduced by McNaughton, Narendran, and Otto in 1988. A language L is Church-Rosser congruential, if there exists a finite confluent, and length-reducing semi-Thue system S such that L is a finite union of congruence classes modulo S. It was known that there are deterministic linear context-free languages which are not Church-Rosser congruential, but on the other hand it was strongly believed that all regular language are of this form. Actually, this paper proves a more general result.
Wyner-Ziv Type Versus Noisy Network Coding For a State-Dependent MAC
Venue: arXiv cs.IT 2012
Year: 2012

We consider a two-user state-dependent multiaccess channel in which the states of the channel are known non-causally to one of the encoders and only strictly causally to the other encoder. Both encoders transmit a common message and, in addition, the encoder that knows the states non-causally transmits an individual message. We find explicit characterizations of the capacity region of this communication model in both discrete memoryless and memoryless Gaussian cases. The analysis also reveals optimal ways of exploiting the knowledge of the state only strictly causally at the encoder that sends only the common message when such a knowledge is beneficial. The encoders collaborate to convey to the decoder a lossy version of the state, in addition to transmitting the information messages through a generalized Gel'fand-Pinsker binning. Particularly important in this problem are the questions of 1) optimal ways of performing the state compression and 2) whether or not the compression indices should be decoded uniquely. We show that both compression à-la noisy network coding, i.e., with no binning, and compression using Wyner-Ziv binning are optimal. The scheme that uses Wyner-Ziv binning shares elements with Cover and El Gamal original compress-and-forward, but differs from it mainly in that backward decoding is employed instead of forward decoding and the compression indices are not decoded uniquely. Finally, by exploring the properties of our outer bound, we show that, although not required in general, the compression indices can in fact be decoded uniquely essentially without altering the capacity region, but at the expense of larger alphabets sizes for the auxiliary random variables.
Contextual Bandit Learning with Predictable Rewards
Venue: arXiv cs.LG 2012
Year: 2012

Contextual bandit learning is a reinforcement learning problem where the learner repeatedly receives a set of features (context), takes an action and receives a reward based on the action and context. We consider this problem under a realizability assumption: there exists a function in a (known) function class, always capable of predicting the expected reward, given the action and context. Under this assumption, we show three things. We present a new algorithm---Regressor Elimination--- with a regret similar to the agnostic setting (i.e. in the absence of realizability assumption). We prove a new lower bound showing no algorithm can achieve superior performance in the worst case even with the realizability assumption. However, we do show that for any set of policies (mapping contexts to actions), there is a distribution over rewards (given context) such that our new algorithm has constant regret unlike the previous approaches.
Visualizing Communication on Social Media: Making Big Data Accessible
Venue: arXiv cs.SI 2012
Year: 2012

The broad adoption of the web as a communication medium has made it possible to study social behavior at a new scale. With social media networks such as Twitter, we can collect large data sets of online discourse. Social science researchers and journalists, however, may not have tools available to make sense of large amounts of data or of the structure of large social networks. In this paper, we describe our recent extensions to Truthy, a system for collecting and analyzing political discourse on Twitter. We introduce several new analytical perspectives on online discourse with the goal of facilitating collaboration between individuals in the computational and social sciences. The design decisions described in this article are motivated by real-world use cases developed in collaboration with colleagues at the Indiana University School of Journalism.
On the Coexistence of Macrocell Spatial Multiplexing and Cognitive Femtocells
Venue: arXiv cs.IT 2012
Year: 2012

We study a two-tier macrocell/femtocell system where the macrocell base station is equipped with multiple antennas and makes use of multiuser MIMO (spatial multiplexing), and the femtocells are "cognitive". In particular, we assume that the femtocells are aware of the locations of scheduled macrocell users on every time-frequency slot, so that they can make decisions on their transmission opportunities accordingly. Femtocell base stations are also equipped with multiple antennas. We propose a scheme where the macrocell downlink (macro- DL) is aligned with the femtocells uplink (femto-UL) and, Vice Versa, the macrocell uplink (macro-UL) is aligned with the femtocells downlink femto-DL). Using a simple "interference temperature" power control in the macro-DL/femto-UL direction, and exploiting uplink/downlink duality and the Yates, Foschini and Miljanic distributed power control algorithm in the macro- UL/femto-DL direction, we can achieve an extremely attractive macro/femto throughput tradeoff region in both directions. We investigate the impact of multiuser MIMO spatial multiplexing in the macrocell under the proposed scheme, and find that large gains are achievable by letting the macrocell schedule groups of co-located users, such that the number of femtocells affected by the interference temperature power constraint is small.
Information Forests
Venue: arXiv cs.LG 2012
Year: 2012

We describe Information Forests, an approach to classification that generalizes Random Forests by replacing the splitting criterion of non-leaf nodes from a discriminative one -- based on the entropy of the label distribution -- to a generative one -- based on maximizing the information divergence between the class-conditional distributions in the resulting partitions. The basic idea consists of deferring classification until a measure of "classification confidence" is sufficiently high, and instead breaking down the data so as to maximize this measure. In an alternative interpretation, Information Forests attempt to partition the data into subsets that are "as informative as possible" for the purpose of the task, which is to classify the data. Classification confidence, or informative content of the subsets, is quantified by the Information Divergence. Our approach relates to active learning, semi-supervised learning, mixed generative/discriminative learning.
Signal Recovery on Incoherent Manifolds
Venue: arXiv cs.IT 2012
Year: 2012

Suppose that we observe noisy linear measurements of an unknown signal that can be modeled as the sum of two component signals, each of which arises from a nonlinear sub-manifold of a high dimensional ambient space. We introduce SPIN, a first order projected gradient method to recover the signal components. Despite the nonconvex nature of the recovery problem and the possibility of underdetermined measurements, SPIN provably recovers the signal components, provided that the signal manifolds are incoherent and that the measurement operator satisfies a certain restricted isometry property. SPIN significantly extends the scope of current recovery models and algorithms for low dimensional linear inverse problems and matches (or exceeds) the current state of the art in terms of performance.
On the Invariance of the Unitary Cost Model for Head Reduction (Long Version)
Venue: arXiv cs.LO 2012
Year: 2012

The lambda calculus is a widely accepted computational model of higher-order functional pro- grams, yet there is not any direct and universally accepted cost model for it. As a consequence, the computational difficulty of reducing lambda terms to their normal form is typically studied by reasoning on concrete implementation algorithms. In this paper, we show that when head reduction is the underlying dynamics, the unitary cost model is indeed invariant. This improves on known results, which only deal with weak (call-by-value or call-by-name) reduction. Invariance is proved by way of a linear calculus of explicit substitutions, which allows to nicely decompose any head reduction step in the lambda calculus into more elementary substitution steps, thus making the combinatorics of head-reduction easier to reason about. The technique is also a promising tool to attack what we see as the main open problem, namely understanding for which normalizing strategies derivation complexity is an invariant cost model, if any.
A characterization of the number of subsequences obtained via the deletion channel
Venue: arXiv cs.IT 2012
Year: 2012

Motivated by the study of deletion channels, this work presents improved bounds on the number of subsequences obtained from a binary sting X of length n under t deletions. It is known that the number of subsequences in this setting strongly depends on the number of runs in the string X; where a run is a maximal sequence of the same character. Our improved bounds are obtained by a structural analysis of the family of r-run strings X, an analysis in which we identify the extremal strings with respect to the number of subsequences. Specifically, for every r, we present r-run strings with the minimum (respectively maximum) number of subsequences under any t deletions; and perform an exact analysis of the number of subsequences of these extremal strings.
Signcryption scheme based on schnorr digital signature
Venue: arXiv cs.CR 2012
Year: 2012

This article presents a new signcryption scheme which is based on the Schnorr digital signature algorithm. The new scheme represents my personal contribution to signcryption area. I have been implemented the algorithm in a program and here are provided the steps of the algorithm, the results and some examples. The paper also contains the presentation of the original Signcryption scheme, based on ElGamal digital signature and discusses the practical applications of Signcryption in real life.
Finding the Graph of Epidemic Cascades
Venue: arXiv cs.SI 2012
Year: 2012

We consider the problem of finding the graph on which an epidemic cascade spreads, given only the times when each node gets infected. While this is a problem of importance in several contexts -- offline and online social networks, e-commerce, epidemiology, vulnerabilities in infrastructure networks -- there has been very little work, analytical or empirical, on finding the graph. Clearly, it is impossible to do so from just one cascade; our interest is in learning the graph from a small number of cascades. For the classic and popular "independent cascade" SIR epidemics, we analytically establish the number of cascades required by both the global maximum-likelihood (ML) estimator, and a natural greedy algorithm. Both results are based on a key observation: the global graph learning problem decouples into $n$ local problems -- one for each node. For a node of degree $d$, we show that its neighborhood can be reliably found once it has been infected $O(d^2 \log n)$ times (for ML on general graphs) or $O(d\log n)$ times (for greedy on trees). We also provide a corresponding information-theoretic lower bound of $Ω(d\log n)$; thus our bounds are essentially tight. Furthermore, if we are given side-information in the form of a super-graph of the actual graph (as is often the case), then the number of cascade samples required -- in all cases -- becomes independent of the network size $n$. Finally, we show that for a very general SIR epidemic cascade model, the Markov graph of infection times is obtained via the moralization of the network graph.
A Proposed Architecture for Continuous Web Monitoring Through Online Crawling of Blogs
Venue: arXiv cs.IR 2012
Year: 2012

Getting informed of what is registered in the Web space on time, can greatly help the psychologists, marketers and political analysts to familiarize, analyse, make decision and act correctly based on the society`s different needs. The great volume of information in the Web space hinders us to continuously online investigate the whole space of the Web. Focusing on the considered blogs limits our working domain and makes the online crawling in the Web space possible. In this article, an architecture is offered which continuously online crawls the related blogs, using focused crawler, and investigates and analyses the obtained data. The online fetching is done based on the latest announcements of the ping server machines. A weighted graph is formed based on targeting the important key phrases, so that a focused crawler can do the fetching of the complete texts of the related Web pages, based on the weighted graph.
Effect of Packet Delay Variation on Video-Voice over DiffServ-MPLS in IPv4-IPv6 Networks
Venue: arXiv cs.NI 2012
Year: 2012

Over the last years, we have witnessed a rapid deployment of real-time applications on the Internet as well as many research works about Quality of Service (QoS), in particular IPv4 (Internet Protocol version 4). The inevitable exhaustion of the remaining IPv4 address pool has become progressively evident. As the evolution of Internet Protocol (IP) continues, the deployment of IPv6 QoS is underway. Today, there is limited experience in the deployment of QoS for IPv6 traffic in MPLS backbone networks in conjunction with DiffServ (Differentiated Services) support. DiffServ itself does not have the ability to control the traffic which has been taken for end-to-end path while a number of links of the path are congested. In contrast, MPLS Traffic Engineering (TE) is accomplished to control the traffic and can set up end-to-end routing path before data has been forwarded. From the evolution of IPv4 QoS solutions, we know that the integration of DiffServ and MPLS TE satisfies the guaranteed QoS requirement for real-time applications. This paper presents a QoS performance study of real-time applications such as voice and video conferencing in terms of Packet Delay Variation (PDV) over DiffServ with or without MPLS TE in IPv4/IPv6 networks using Optimized Network Engineering Tool (OPNET). We also study the interaction of Expedited Forwarding (EF), Assured Forwarding (AF) traffic aggregation, link congestion, as well as the effect of performance metric such as PDV. The effectiveness of DiffServ and MPLS TE integration in IPv4/IPv6 network is illustrated and analyzed. This paper shows that IPv6 experiences more PDV than their IPv4 counterparts.