OpenRaiser/Intern-Atlas huggingface dataset:
Competition of Wireless Providers for Atomic Users
Venue: arXiv cs.IT 2010
Year: 2010

We study a problem where wireless service providers compete for heterogenous wireless users. The users differ in their utility functions as well as in the perceived quality of service of individual providers. We model the interaction of an arbitrary number of providers and users as a two-stage multi-leader-follower game. We prove existence and uniqueness of the subgame perfect Nash equilibrium for a generic channel model and a wide class of users' utility functions. We show that the competition of resource providers leads to a globally optimal outcome under mild technical conditions. Most users will purchase the resource from only one provider at the unique subgame perfect equilibrium. The number of users who connect to multiple providers at the equilibrium is always smaller than the number of providers. We also present a decentralized algorithm that globally converges to the unique system equilibrium with only local information under mild conditions on the update rates.
Exponential Time Complexity of Weighted Counting of Independent Sets
Venue: arXiv cs.CC 2010
Year: 2010

We consider weighted counting of independent sets using a rational weight x: Given a graph with n vertices, count its independent sets such that each set of size k contributes x^k. This is equivalent to computation of the partition function of the lattice gas with hard-core self-repulsion and hard-core pair interaction. We show the following conditional lower bounds: If counting the satisfying assignments of a 3-CNF formula in n variables (#3SAT) needs time 2^{Ω(n)} (i.e. there is a c>0 such that no algorithm can solve #3SAT in time 2^{cn}), counting the independent sets of size n/3 of an n-vertex graph needs time 2^{Ω(n)} and weighted counting of independent sets needs time 2^{Ω(n/log^3 n)} for all rational weights x\neq 0. We have two technical ingredients: The first is a reduction from 3SAT to independent sets that preserves the number of solutions and increases the instance size only by a constant factor. Second, we devise a combination of vertex cloning and path addition. This graph transformation allows us to adapt a recent technique by Dell, Husfeldt, and Wahlen which enables interpolation by a family of reductions, each of which increases the instance size only polylogarithmically.
Inter-Sensing Time Optimization in Cognitive Radio Networks
Venue: arXiv cs.NI 2010
Year: 2010

We consider a set of primary channels that operate in an unslotted fashion, switching activity at random times. A secondary user senses the primary channels searching for transmission opportunities. If a channel is sensed to be free, the secondary terminal transmits, and if sensed to be busy, the secondary transmitter remains silent.We solve the problem of determining the optimal time after which a primary channel needs to be sensed again depending on the sensing outcome. The objective is to find the inter-sensing times such that the mean secondary throughput is maximized while imposing a constraint over the maximum tolerable interference inflicted on the primary network. Our numerical results show that by optimizing the sensing-dependent inter-sensing times, our proposed scheme reduces the impact of sensing errors caused by false alarm and misdetection and outperforms the case of a single sensing period.
Minimum Sum Dipolar Spanning Tree in R^3
Venue: arXiv cs.CG 2010
Year: 2010

In this paper we consider finding a geometric minimum-sum dipolar spanning tree in R^3, and present an algorithm that takes O(n^2 log^2 n) time using O(n^2) space, thus almost matching the best known results for the planar case. Our solution uses an interesting result related to the complexity of the common intersection of n balls in R^3, of possible different radii, that are all tangent to a given point p. The problem has applications in communication networks, when the goal is to minimize the distance between two hubs or servers as well as the distance from any node in the network to the closer of the two hubs. The approach used in this paper also provides a solution to the discrete 2-center problem in R^3 within the same time and space bounds.
Queue-Architecture and Stability Analysis in Cooperative Relay Networks
Venue: arXiv cs.NI 2010
Year: 2010

An abstraction of the physical layer coding using bit pipes that are coupled through data-rates is insufficient to capture notions such as node cooperation in cooperative relay networks. Consequently, network-stability analyses based on such abstractions are valid for non-cooperative schemes alone and meaningless for cooperative schemes. Motivated from this, this paper develops a framework that brings the information-theoretic coding scheme together with network-stability analysis. This framework does not constrain the system to any particular achievable scheme, i.e., the relays can use any cooperative coding strategy of its choice, be it amplify/compress/quantize or any alter-and-forward scheme. The paper focuses on the scenario when coherence duration is of the same order of the packet/codeword duration, the channel distribution is unknown and the fading state is only known causally. The main contributions of this paper are two-fold: first, it develops a low-complexity queue-architecture to enable stable operation of cooperative relay networks, and, second, it establishes the throughput optimality of a simple network algorithm that utilizes this queue-architecture.
Context Awareness Framework Based on Contextual Graph
Venue: arXiv cs.NI 2010
Year: 2010

Nowadays computing becomes increasingly mobile and pervasive. One of the important steps in pervasive computing is context-awareness. Context-aware pervasive systems rely on information about the context and user preferences to adapt their behavior. However, context-aware applications do not always behave as user's desire, and can cause users to feel dissatisfied with unexpected actions. To solve these problems, context-aware systems must provide mechanisms to adapt automatically when the context changes significantly. The interesting characteristic of context is its own behaviors which depend on various aspects of the surrounding contexts. This paper uses contextual graphs to solve the problem "the mutual relationships among the contexts". We describe the most relevant work in this area, as well as ongoing research on developing context-aware system for ubiquitous computing based on contextual graph. The usage of contextual graph in context-awareness is expected to make it effective for developers to develop various applications with the need of context reasoning.
Network Anomaly Detection: Flow-based or Packet-based Approach?
Venue: arXiv cs.NI 2010
Year: 2010

One of the most critical tasks for network administrator is to ensure system uptime and availability. For the network security, anomaly detection systems, along with firewalls and intrusion prevention systems are the must-have tools. So far in the field of network anomaly detection, people are working on two different approaches. One is flow-based; usually rely on network elements to make so-called flow information available for analysis. The second approach is packet-based; which directly analyzes the data packet information for the detection of anomalies. This paper describes the main differences between the two approaches through an in-depth analysis. We try to answer the question of when and why an approach is better than the other. The answer is critical for network administrators to make their choices in deploying a defending system, securing the network and ensuring business continuity.
Scheduling for Optimal Rate Allocation in Ad Hoc Networks With Heterogeneous Delay Constraints
Venue: arXiv cs.NI 2010
Year: 2010

This paper studies the problem of scheduling in single-hop wireless networks with real-time traffic, where every packet arrival has an associated deadline and a minimum fraction of packets must be transmitted before the end of the deadline. Using optimization and stochastic network theory we propose a framework to model the quality of service (QoS) requirements under delay constraints. The model allows for fairly general arrival models with heterogeneous constraints. The framework results in an optimal scheduling algorithm which fairly allocates data rates to all flows while meeting long-term delay demands. We also prove that under a simplified scenario our solution translates into a greedy strategy that makes optimal decisions with low complexity.
Interactive Learning-Based Realizability for Heyting Arithmetic with EM1
Venue: arXiv cs.LO 2010
Year: 2010

We apply to the semantics of Arithmetic the idea of ``finite approximation'' used to provide computational interpretations of Herbrand's Theorem, and we interpret classical proofs as constructive proofs (with constructive rules for $\vee, \exists$) over a suitable structure $\StructureN$ for the language of natural numbers and maps of Gödel's system $\SystemT$. We introduce a new Realizability semantics we call ``Interactive learning-based Realizability'', for Heyting Arithmetic plus $\EM_1$ (Excluded middle axiom restricted to $Σ^0_1$ formulas). Individuals of $\StructureN$ evolve with time, and realizers may ``interact'' with them, by influencing their evolution. We build our semantics over Avigad's fixed point result, but the same semantics may be defined over different constructive interpretations of classical arithmetic (Berardi and de' Liguoro use continuations). Our notion of realizability extends intuitionistic realizability and differs from it only in the atomic case: we interpret atomic realizers as ``learning agents''.
A Tight Bound on the Maximum Interference of Random Sensors in the Highway Model
Venue: arXiv cs.CG 2010
Year: 2010

Consider $n$ sensors whose positions are represented by $n$ uniform, independent and identically distributed random variables assuming values in the open unit interval $(0,1)$. A natural way to guarantee connectivity in the resulting sensor network is to assign to each sensor as its range, the maximum of the two possible distances to its two neighbors. The interference at a given sensor is defined as the number of sensors that have this sensor within their range. In this paper we prove that the expected maximum interference of the sensors is $Θ(\sqrt{\ln n})$.
Matroid Secretary Problem in the Random Assignment Model
Venue: arXiv cs.DS 2010
Year: 2010

In the Matroid Secretary Problem, introduced by Babaioff et al. [SODA 2007], the elements of a given matroid are presented to an online algorithm in random order. When an element is revealed, the algorithm learns its weight and decides whether or not to select it under the restriction that the selected elements form an independent set in the matroid. The objective is to maximize the total weight of the chosen elements. In the most studied version of this problem, the algorithm has no information about the weights beforehand. We refer to this as the zero information model. In this paper we study a different model, also proposed by Babaioff et al., in which the relative order of the weights is random in the matroid. To be precise, in the random assignment model, an adversary selects a collection of weights that are randomly assigned to the elements of the matroid. Later, the elements are revealed to the algorithm in a random order independent of the assignment. Our main result is the first constant competitive algorithm for the matroid secretary problem in the random assignment model. This solves an open question of Babaioff et al. Our algorithm achieves a competitive ratio of $2e^2/(e-1)$. It exploits the notion of principal partition of a matroid, its decomposition into uniformly dense minors, and a $2e$-competitive algorithm for uniformly dense matroids we also develop. As additional results, we present simple constant competitive algorithms in the zero information model for various classes of matroids including cographic, low density and the case when every element is in a small cocircuit. In the same model, we also give a $ke$-competitive algorithm for $k$-column sparse linear matroids, and a new $O(\log r)$-competitive algorithm for general matroids of rank $r$ which only uses the relative order of the weights seen and not their numerical value, as previously needed.
A measure of state transition of collective of stateless automata in discrete environment
Venue: arXiv cs.FL 2010
Year: 2010

In this work a collective of interacting stateless automata in a discrete geometric environment is considered as an integral automata-like computational dynamic object. For such distributed on the environment object different approaches to definition of the measure of state transition are possible. We propose a geometric approach for defining what a state is.
The Complexity of Testing Monomials in Multivariate Polynomials
Venue: arXiv cs.CC 2010
Year: 2010

The work in this paper is to initiate a theory of testing monomials in multivariate polynomials. The central question is to ask whether a polynomial represented by certain economically compact structure has a multilinear monomial in its sum-product expansion. The complexity aspects of this problem and its variants are investigated with two folds of objectives. One is to understand how this problem relates to critical problems in complexity, and if so to what extent. The other is to exploit possibilities of applying algebraic properties of polynomials to the study of those problems. A series of results about $ΠΣΠ$ and $ΠΣ$ polynomials are obtained in this paper, laying a basis for further study along this line.
LANC: locality-aware network coding for better P2P traffic localization
Venue: arXiv cs.DC 2010
Year: 2010

As ISPs begin to cooperate to expose their network locality information as services, e.g., P4P, solutions based on locality information provision for P2P traffic localization will soon approach their capability limits. A natural question is: can we do any better provided that no further locality information improvement can be made? This paper shows how the utility of locality information could be limited by conventional P2P data scheduling algorithms, even as sophisticated as the local rarest first policy. Network coding's simplified data scheduling makes it competent for improving P2P application's throughput. Instead of only using locality information in the topology construction, this paper proposes the locality-aware network coding (LANC) that uses locality information in both the topology construction and downloading decision, and demonstrates its exceptional ability for P2P traffic localization. The randomization introduced by network coding enhances the chance for a peer to find innovative blocks in its neighborhood. Aided by proper locality-awareness, the probability for a peer to get innovative blocks from its proximity will increase as well, resulting in more efficient use of network resources. Extensive simulation results show that LANC can significantly reduce P2P traffic redundancy without sacrificing application-level performance. Aided by the same locality knowledge, the traffic redundancies of LANC in most cases are less than 50\% of the current best approach that does not use network coding.
Publishing and Discovery of Mobile Web Services in Peer to Peer Networks
Venue: arXiv cs.IR 2010
Year: 2010

It is now feasible to host Web Services on a mobile device due to the advances in cellular devices and mobile communication technologies. However, the reliability, usability and responsiveness of the Mobile Hosts depend on various factors including the characteristics of available network, computational resources, and better means of searching the services provided by them. P2P enhances the adoption of Mobile Host in commercial environments. Mobile Hosts in P2P can collaboratively share the resources of individual peers. P2P also enhances the service discovery of huge number of Web Services possible with Mobile Hosts. Advanced features like post filtering with weight of keywords and context-awareness can also be exploited to select the best possible mobile Web Service. This paper proposes the concept of Mobile Hosts in P2P networks and identifies the means of publishing and discovery of Web Services in mobile P2P networks.
A Mediation Framework for Mobile Web Service Provisioning
Venue: arXiv cs.DC 2010
Year: 2010

Web Services and mobile data services are the newest trends in information systems engineering in wired and wireless domains, respectively. Web Services have a broad range of service distributions while mobile phones have large and expanding user base. To address the confluence of Web Services and pervasive mobile devices and communication environments, a basic mobile Web Service provider was developed for smart phones. The performance of this Mobile Host was also analyzed in detail. Further analysis of the Mobile Host to provide proper QoS and to check Mobile Host's feasibility in the P2P networks, identified the necessity of a mediation framework. The paper describes the research conducted with the Mobile Host, identifies the tasks of the mediation framework and then discusses the feasible realization details of such a mobile Web Services mediation framework.
The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata
Venue: arXiv cs.FL 2010
Year: 2010

We discuss the power and limitation of various "advice," when it is given particularly to weak computational models of one-tape linear-time Turing machines and one-way finite (state) automata. Of various advice types, we consider deterministically-chosen advice (not necessarily algorithmically determined) and randomly-chosen advice (according to certain probability distributions). In particular, we show that certain weak machines can be significantly enhanced in computational power when randomized advice is provided in place of deterministic advice.
Strongly Resilient Non-Interactive Key Predistribution For Hierarchical Networks
Venue: arXiv cs.CR 2010
Year: 2010

Key establishment is the basic necessary tool in the network security, by which pairs in the network can establish shared keys for protecting their pairwise communications. There have been some key agreement or predistribution schemes with the property that the key can be established without the interaction (\cite{Blom84,BSHKY92,S97}). Recently the hierarchical cryptography and the key management for hierarchical networks have been active topics(see \cite{BBG05,GHKRRW08,GS02,HNZI02,HL02,Matt04}. ). Key agreement schemes for hierarchical networks were presented in \cite{Matt04,GHKRRW08} which is based on the Blom key predistribution scheme(Blom KPS, [1]) and pairing. In this paper we introduce generalized Blom-Blundo et al key predistribution schemes. These generalized Blom-Blundo et al key predistribution schemes have the same security functionality as the Blom-Blundo et al KPS. However different and random these KPSs can be used for various parts of the networks for enhancing the resilience. We also presentkey predistribution schemes from a family hyperelliptic curves. These key predistribution schemes from different random curves can be used for various parts of hierarchical networks. Then the non-interactive, identity-based and dynamic key predistributon scheme based on this generalized Blom-Blundo et al KPSs and hyperelliptic curve KPSs for hierarchical networks with the following properties are constructed. 1)$O(A_KU)$ storage at each node in the network where $U$ is the expansion number and $A_K$ is the number of nodes at the $K$-th level of the hierarchical network; 2)Strongly resilience to the compromising of arbitrary many leaf and internal nodes; 3)Information theoretical security without random oracle.
Safety Message Power Transmission Control for Vehicular Ad hoc Networks
Venue: arXiv cs.NI 2010
Year: 2010

Vehicular Ad hoc Networks (VANET) is one of the most challenging research area in the field of Mobile Ad Hoc Networks. In this research we proposed a dynamic power adjustment protocol that will be used for sending the periodical safety message. (Beacon)based on the analysis of the channel status depending on the channel congestion and the power used for transmission. The Beacon Power Control (BPC) protocol first sensed and examined the percentage of the channel congestion, the result obtained was used to adjust the transmission power for the safety message to reach the optimal power. This will lead to decrease the congestion in the channel and achieve good channel performance and beacon dissemination.
Link Graph Analysis for Adult Images Classification
Venue: arXiv cs.IR 2010
Year: 2010

In order to protect an image search engine's users from undesirable results adult images' classifier should be built. The information about links from websites to images is employed to create such a classifier. These links are represented as a bipartite website-image graph. Each vertex is equipped with scores of adultness and decentness. The scores for image vertexes are initialized with zero, those for website vertexes are initialized according to a text-based website classifier. An iterative algorithm that propagates scores within a website-image graph is described. The scores obtained are used to classify images by choosing an appropriate threshold. The experiments on Internet-scale data have shown that the algorithm under consideration increases classification recall by 17% in comparison with a simple algorithm which classifies an image as adult if it is connected with at least one adult site (at the same precision level).
Distinguishing Fact from Fiction: Pattern Recognition in Texts Using Complex Networks
Venue: arXiv cs.CL 2010
Year: 2010

We establish concrete mathematical criteria to distinguish between different kinds of written storytelling, fictional and non-fictional. Specifically, we constructed a semantic network from both novels and news stories, with $N$ independent words as vertices or nodes, and edges or links allotted to words occurring within $m$ places of a given vertex; we call $m$ the word distance. We then used measures from complex network theory to distinguish between news and fiction, studying the minimal text length needed as well as the optimized word distance $m$. The literature samples were found to be most effectively represented by their corresponding power laws over degree distribution $P(k)$ and clustering coefficient $C(k)$; we also studied the mean geodesic distance, and found all our texts were small-world networks. We observed a natural break-point at $k=\sqrt{N}$ where the power law in the degree distribution changed, leading to separate power law fit for the bulk and the tail of $P(k)$. Our linear discriminant analysis yielded a $73.8 \pm 5.15%$ accuracy for the correct classification of novels and $69.1 \pm 1.22%$ for news stories. We found an optimal word distance of $m=4$ and a minimum text length of 100 to 200 words $N$.
Formal study of plane Delaunay triangulation
Venue: arXiv cs.LO 2010
Year: 2010

This article presents the formal proof of correctness for a plane Delaunay triangulation algorithm. It consists in repeating a sequence of edge flippings from an initial triangulation until the Delaunay property is achieved. To describe triangulations, we rely on a combinatorial hypermap specification framework we have been developing for years. We embed hypermaps in the plane by attaching coordinates to elements in a consistent way. We then describe what are legal and illegal Delaunay edges and a flipping operation which we show preserves hypermap, triangulation, and embedding invariants. To prove the termination of the algorithm, we use a generic approach expressing that any non-cyclic relation is well-founded when working on a finite set.