OpenRaiser/Intern-Atlas huggingface dataset:
Modeling Routing Overhead Generated by Wireless Proactive Routing Protocols
Venue: arXiv cs.NI 2011
Year: 2011

In this paper, we present a detailed framework consisting of modeling of routing overhead generated by three widely used proactive routing protocols; Destination-Sequenced Distance Vector (DSDV), Fish-eye State Routing (FSR) and Optimized Link State Routing (OLSR). The questions like, how these protocols differ from each other on the basis of implementing different routing strategies, how neighbor estimation errors affect broadcast of route requests, how reduction of broadcast overhead achieves bandwidth, how to cope with the problem of mobility and density, etc, are attempted to respond. In all of the above mentioned situations, routing overhead and delay generated by the chosen protocols can exactly be calculated from our modeled equations. Finally, we analyze the performance of selected routing protocols using our proposed framework in NS-2 by considering different performance parameters; Route REQuest (RREQ) packet generation, End-to-End Delay (E2ED) and Normalized Routing Load (NRL) with respect to varying rates of mobility and density of nodes in the underlying wireless network.
Learning From Labeled And Unlabeled Data: An Empirical Study Across Techniques And Domains
Venue: arXiv cs.LG 2011
Year: 2011

There has been increased interest in devising learning techniques that combine unlabeled data with labeled data ? i.e. semi-supervised learning. However, to the best of our knowledge, no study has been performed across various techniques and different types and amounts of labeled and unlabeled data. Moreover, most of the published work on semi-supervised learning techniques assumes that the labeled and unlabeled data come from the same distribution. It is possible for the labeling process to be associated with a selection bias such that the distributions of data points in the labeled and unlabeled sets are different. Not correcting for such bias can result in biased function approximation with potentially poor performance. In this paper, we present an empirical study of various semi-supervised learning techniques on a variety of datasets. We attempt to answer various questions such as the effect of independence or relevance amongst features, the effect of the size of the labeled and unlabeled sets and the effect of noise. We also investigate the impact of sample-selection bias on the semi-supervised learning techniques under study and implement a bivariate probit technique particularly designed to correct for such bias.
Combining Knowledge- and Corpus-based Word-Sense-Disambiguation Methods
Venue: arXiv cs.CL 2011
Year: 2011

In this paper we concentrate on the resolution of the lexical ambiguity that arises when a given word has several different meanings. This specific task is commonly referred to as word sense disambiguation (WSD). The task of WSD consists of assigning the correct sense to words using an electronic dictionary as the source of word definitions. We present two WSD methods based on two main methodological approaches in this research area: a knowledge-based method and a corpus-based method. Our hypothesis is that word-sense disambiguation requires several knowledge sources in order to solve the semantic ambiguity of the words. These sources can be of different kinds--- for example, syntagmatic, paradigmatic or statistical information. Our approach combines various sources of knowledge, through combinations of the two WSD methods mentioned above. Mainly, the paper concentrates on how to combine these methods and sources of information in order to achieve good results in the disambiguation. Finally, this paper presents a comprehensive study and experimental work on evaluation of the methods and their combinations.
Pure Nash Equilibria: Hard and Easy Games
Venue: arXiv cs.GT 2011
Year: 2011

We investigate complexity issues related to pure Nash equilibria of strategic games. We show that, even in very restrictive settings, determining whether a game has a pure Nash Equilibrium is NP-hard, while deciding whether a game has a strong Nash equilibrium is SigmaP2-complete. We then study practically relevant restrictions that lower the complexity. In particular, we are interested in quantitative and qualitative restrictions of the way each players payoff depends on moves of other players. We say that a game has small neighborhood if the utility function for each player depends only on (the actions of) a logarithmically small number of other players. The dependency structure of a game G can be expressed by a graph DG(G) or by a hypergraph H(G). By relating Nash equilibrium problems to constraint satisfaction problems (CSPs), we show that if G has small neighborhood and if H(G) has bounded hypertree width (or if DG(G) has bounded treewidth), then finding pure Nash and Pareto equilibria is feasible in polynomial time. If the game is graphical, then these problems are LOGCFL-complete and thus in the class NC2 of highly parallelizable problems.
Deconstructing Approximate Offsets
Venue: arXiv cs.CG 2011
Year: 2011

We consider the offset-deconstruction problem: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance \eps in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius? If it does, we also seek a preferably simple-looking solution P; then, P's offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give an O(n log n)-time exact decision algorithm that handles any polygonal shape, assuming the real-RAM model of computation. A variant of the algorithm, which we have implemented using CGAL, is based on rational arithmetic and answers the same deconstruction problem up to an uncertainty parameter δ; its running time additionally depends on δ. If the input shape is found to be approximable, this algorithm also computes an approximate solution for the problem. It also allows us to solve parameter-optimization problems induced by the offset-deconstruction problem. For convex shapes, the complexity of the exact decision algorithm drops to O(n), which is also the time required to compute a solution P with at most one more vertex than a vertex-minimal one.
The Complexity of the Empire Colouring Problem
Venue: arXiv cs.CC 2011
Year: 2011

We investigate the computational complexity of the empire colouring problem (as defined by Percy Heawood in 1890) for maps containing empires formed by exactly $r > 1$ countries each. We prove that the problem can be solved in polynomial time using $s$ colours on maps whose underlying adjacency graph has no induced subgraph of average degree larger than $s/r$. However, if $s \geq 3$, the problem is NP-hard even if the graph is a forest of paths of arbitrary lengths (for any $r \geq 2$, provided $s < 2r - \sqrt(2r + 1/4+ 3/2)$. Furthermore we obtain a complete characterization of the problem's complexity for the case when the input graph is a tree, whereas our result for arbitrary planar graphs fall just short of a similar dichotomy. Specifically, we prove that the empire colouring problem is NP-hard for trees, for any $r \geq 2$, if $3 \leq s \leq 2r-1$ (and polynomial time solvable otherwise). For arbitrary planar graphs we prove NP-hardness if $s<7$ for $r=2$, and $s < 6r-3$, for $r \geq 3$. The result for planar graphs also proves the NP-hardness of colouring with less than 7 colours graphs of thickness two and less than $6r-3$ colours graphs of thickness $r \geq 3$.
A New Proposed Cost Model for List Accessing Problem using Buffering
Venue: arXiv cs.DS 2011
Year: 2011

There are many existing well known cost models for the list accessing problem. The standard cost model developed by Sleator and Tarjan is most widely used. In this paper, we have made a comprehensive study of the existing cost models and proposed a new cost model for the list accessing problem. In our proposed cost model, for calculating the processing cost of request sequence using a singly linked list, we consider the access cost, matching cost and replacement cost. The cost of processing a request sequence is the sum of access cost, matching cost and replacement cost. We have proposed a novel method for processing the request sequence which does not consider the rearrangement of the list and uses the concept of buffering, matching, look ahead and flag bit.
The World is Either Algorithmic or Mostly Random
Venue: arXiv cs.IT 2011
Year: 2011

I will propose the notion that the universe is digital, not as a claim about what the universe is made of but rather about the way it unfolds. Central to the argument will be the concepts of symmetry breaking and algorithmic probability, which will be used as tools to compare the way patterns are distributed in our world to the way patterns are distributed in a simulated digital one. These concepts will provide a framework for a discussion of the informational nature of reality. I will argue that if the universe were analog, then the world would likely be random, making it largely incomprehensible. The digital model has, however, an inherent beauty in its imposition of an upper limit and in the convergence in computational power to a maximal level of sophistication. Even if deterministic, that it is digital doesn't mean that the world is trivial or predictable, but rather that it is built up from operations that at the lowest scale are very simple but that at a higher scale look complex and even random, though only in appearance.
The Standard Aspect of Dialectical Logic
Venue: arXiv cs.LO 2011
Year: 2011

Dialectical logic is the logic of dialectical processes. The goal of dialectical logic is to introduce dynamic notions into logical computational systems. The fundamental notions of proposition and truth-value in standard logic are subsumed by the notions of process and flow in dialectical logic. Dialectical logic has a standard aspect, which can be defined in terms of the "local cartesian closure" of subtypes. The standard aspect of dialectical logic provides a natural program semantics which incorporates Hoare's precondition/postcondition semantics and extends the standard Kripke semantics of dynamic logic. The goal of the standard aspect of dialectical logic is to unify the logic of small-scale and large-scale programming.
An Algebraic Characterization of Rainbow Connectivity
Venue: arXiv cs.DM 2011
Year: 2011

The use of algebraic techniques to solve combinatorial problems is studied in this paper. We formulate the rainbow connectivity problem as a system of polynomial equations. We first consider the case of two colors for which the problem is known to be hard and we then extend the approach to the general case. We also give a formulation of the rainbow connectivity problem as an ideal membership problem.
Internet and political communication - Macedonian case
Venue: arXiv cs.SI 2011
Year: 2011

Analysis how to use Internet influence to the process of political communication, marketing and the management of public relations, what kind of online communication methods are used by political parties, and to assess satisfaction, means of communication and the services they provide to their partys voters (people) and other interest groups and whether social networks can affect the political and economic changes in the state, and the political power of one party.
Timed Automata Semantics for Visual e-Contracts
Venue: arXiv cs.LO 2011
Year: 2011

C-O Diagrams have been introduced as a means to have a more visual representation of electronic contracts, where it is possible to represent the obligations, permissions and prohibitions of the different signatories, as well as what are the penalties in case of not fulfillment of their obligations and prohibitions. In such diagrams we are also able to represent absolute and relative timing constraints. In this paper we present a formal semantics for C-O Diagrams based on timed automata extended with an ordering of states and edges in order to represent different deontic modalities.
On Kahan's Rules for Determining Branch Cuts
Venue: arXiv cs.SC 2011
Year: 2011

In computer algebra there are different ways of approaching the mathematical concept of functions, one of which is by defining them as solutions of differential equations. We compare different such approaches and discuss the occurring problems. The main focus is on the question of determining possible branch cuts. We explore the extent to which the treatment of branch cuts can be rendered (more) algorithmic, by adapting Kahan's rules to the differential equation setting.
Real Interference Alignment and Degrees of Freedom Region of Wireless X Networks
Venue: arXiv cs.IT 2011
Year: 2011

We consider a single hop wireless X network with $K$ transmitters and $J$ receivers, all with single antenna. Each transmitter conveys for each receiver an independent message. The channel is assumed to have constant coefficients. We develop interference alignment scheme for this setup and derived several achievable degrees of freedom regions. We show that in some cases, the derived region meets a previous outer bound and are hence the DoF region. For our achievability schemes, we divide each message into streams and use real interference alignment on the streams. Several previous results on the DoF region and total DoF for various special cases can be recovered from our result.
Downlink Performance and Capacity of Distributed Antenna Systems
Venue: arXiv cs.IT 2011
Year: 2011

This paper investigates the performance of the downlink channel in distributed antenna systems. We first establish the ergodic capacity of distributed antennas, under different channel side information (CSI) assumptions. We consider a generalized distributed antenna system with $N$ distributed ports, each of which is equipped with an array of $L$ transmit antennas and constrained by a fixed transmit power. For this system we calculate the downlink capacity to a single antenna receiver, under different assumptions about the availability of the channel states at the transmitter. Having established this information theoretic analysis of the ergodic capacity of distributed antenna systems, this paper also investigates the effect of antenna placement on the performance of such systems. In particular, we investigate the optimal placement of the transmit antennas in distributed antenna systems. We present a fairly general framework for this optimization with no constraint on the location of the antennas. Based on stochastic approximation theory, we adopt a formulation that is suitable for node placement optimization in various wireless network scenarios. We show that optimal placement of antennas inside the coverage region can significantly improve the power efficiency of wireless networks.
Performance of Multi-Antenna MMSE Receivers in Non-homogeneous Poisson Networks
Venue: arXiv cs.IT 2011
Year: 2011

A technique to compute the Cumulative Distribution Function (CDF) of the Signal-to-Interference-plus-Noise-Ratio (SINR) for a wireless link with a multi-antenna, Linear, Minimum-Mean-Square-Error (MMSE) receiver in the presence of interferers distributed according to a non-homogenous Poisson point process on the plane, and independent Rayleigh fading between antennas is presented. This technique is used to compute the CDF of the SINR for several different models of intensity functions, in particular, power-law intensity functions, circular-symmetric Gaussian intensity functions and intensity functions described by a polynomial in a bounded domain. Additionally it is shown that if the number of receiver antennas is scaled linearly with the intensity function, the SINR converges in probability to a limit determined by the "shape" of the underlying intensity function. This work generalizes known results for homogenous Poisson networks to non-homogenous Poisson networks.
A Statistically Modelling Method for Performance Limits in Sensor Localization
Venue: arXiv cs.SY 2011
Year: 2011

In this paper, we study performance limits of sensor localization from a novel perspective. Specifically, we consider the Cramer-Rao Lower Bound (CRLB) in single-hop sensor localization using measurements from received signal strength (RSS), time of arrival (TOA) and bearing, respectively, but differently from the existing work, we statistically analyze the trace of the associated CRLB matrix (i.e. as a scalar metric for performance limits of sensor localization) by assuming anchor locations are random. By the Central Limit Theorems for $U$-statistics, we show that as the number of the anchors increases, this scalar metric is asymptotically normal in the RSS/bearing case, and converges to a random variable which is an affine transformation of a chi-square random variable of degree 2 in the TOA case. Moreover, we provide formulas quantitatively describing the relationship among the mean and standard deviation of the scalar metric, the number of the anchors, the parameters of communication channels, the noise statistics in measurements and the spatial distribution of the anchors. These formulas, though asymptotic in the number of the anchors, in many cases turn out to be remarkably accurate in predicting performance limits, even if the number is small. Simulations are carried out to confirm our results.
Sample-Based Planning with Volumes in Configuration Space
Venue: arXiv cs.RO 2011
Year: 2011

A simple sample-based planning method is presented which approximates connected regions of free space with volumes in Configuration space instead of points. The algorithm produces very sparse trees compared to point-based planning approaches, yet it maintains probabilistic completeness guarantees. The planner is shown to improve performance on a variety of planning problems, by focusing sampling on more challenging regions of a planning problem, including collision boundary areas such as narrow passages.
Non-termination Analysis of Logic Programs with Integer arithmetics
Venue: arXiv cs.PL 2011
Year: 2011

In the past years, analyzers have been introduced to detect classes of non-terminating queries for definite logic programs. Although these non-termination analyzers have shown to be rather precise, their applicability on real-life Prolog programs is limited because most Prolog programs use non-logical features. As a first step towards the analysis of Prolog programs, this paper presents a non-termination condition for Logic Programs containing integer arithmetics. The analyzer is based on our non-termination analyzer presented at ICLP 2009. The analysis starts from a class of queries and infers a subclass of non-terminating ones. In a first phase, we ignore the outcome (success or failure) of the arithmetic operations, assuming success of all arithmetic calls. In a second phase, we characterize successful arithmetic calls as a constraint problem, the solution of which determines the non-terminating queries.
Large-scale Complex IT Systems
Venue: arXiv cs.SE 2011
Year: 2011

This paper explores the issues around the construction of large-scale complex systems which are built as 'systems of systems' and suggests that there are fundamental reasons, derived from the inherent complexity in these systems, why our current software engineering methods and techniques cannot be scaled up to cope with the engineering challenges of constructing such systems. It then goes on to propose a research and education agenda for software engineering that identifies the major challenges and issues in the development of large-scale complex, software-intensive systems. Central to this is the notion that we cannot separate software from the socio-technical environment in which it is used.
Using In-Memory Encrypted Databases on the Cloud
Venue: arXiv cs.CR 2011
Year: 2011

Storing data in the cloud poses a number of privacy issues. A way to handle them is supporting data replication and distribution on the cloud via a local, centrally synchronized storage. In this paper we propose to use an in-memory RDBMS with row-level data encryption for granting and revoking access rights to distributed data. This type of solution is rarely adopted in conventional RDBMSs because it requires several complex steps. In this paper we focus on implementation and benchmarking of a test system, which shows that our simple yet effective solution overcomes most of the problems.
Local Correction of Juntas
Venue: arXiv cs.CC 2011
Year: 2011

A Boolean function f over n variables is said to be q-locally correctable if, given a black-box access to a function g which is "close" to an isomorphism f_sigma of f, we can compute f_sigma(x) for any x in Z_2^n with good probability using q queries to g. We observe that any k-junta, that is, any function which depends only on k of its input variables, is O(2^k)-locally correctable. Moreover, we show that there are examples where this is essentially best possible, and locally correcting some k-juntas requires a number of queries which is exponential in k. These examples, however, are far from being typical, and indeed we prove that for almost every k-junta, O(k log k) queries suffice.
New Principles of Coordination in Large-scale Micro- and Molecular-Robotic Groups
Venue: arXiv cs.RO 2011
Year: 2011

Micro- and molecular-robotic systems act as large-scale swarms. Capabilities of sensing, communication and information processing are very limited on these scales. This short position paper describes a swarm-based minimalistic approach, which can be applied for coordinating collective behavior in such systems.
Online Robust Subspace Tracking from Partial Information
Venue: arXiv cs.IT 2011
Year: 2011

This paper presents GRASTA (Grassmannian Robust Adaptive Subspace Tracking Algorithm), an efficient and robust online algorithm for tracking subspaces from highly incomplete information. The algorithm uses a robust $l^1$-norm cost function in order to estimate and track non-stationary subspaces when the streaming data vectors are corrupted with outliers. We apply GRASTA to the problems of robust matrix completion and real-time separation of background from foreground in video. In this second application, we show that GRASTA performs high-quality separation of moving objects from background at exceptional speeds: In one popular benchmark video example, GRASTA achieves a rate of 57 frames per second, even when run in MATLAB on a personal laptop.
A Dynamic Stabbing-Max Data Structure with Sub-Logarithmic Query Time
Venue: arXiv cs.DS 2011
Year: 2011

In this paper we describe a dynamic data structure that answers one-dimensional stabbing-max queries in optimal $O(\log n/\log\log n)$ time. Our data structure uses linear space and supports insertions and deletions in $O(\log n)$ and $O(\log n/\log \log n)$ amortized time respectively. We also describe a $O(n(\log n/\log\log n)^{d-1})$ space data structure that answers $d$-dimensional stabbing-max queries in $O((\log n/\log\log n)^{d})$ time. Insertions and deletions are supported in $O((\log n/\log\log n)^d\log\log n)$ and $O((\log n/\log\log n)^d)$ amortized time respectively.
Benefits of Bias: Towards Better Characterization of Network Sampling
Venue: arXiv cs.SI 2011
Year: 2011

From social networks to P2P systems, network sampling arises in many settings. We present a detailed study on the nature of biases in network sampling strategies to shed light on how best to sample from networks. We investigate connections between specific biases and various measures of structural representativeness. We show that certain biases are, in fact, beneficial for many applications, as they "push" the sampling process towards inclusion of desired properties. Finally, we describe how these sampling biases can be exploited in several, real-world applications including disease outbreak detection and market research.