OpenRaiser/Intern-Atlas huggingface dataset:
Scheduling in a random environment: stability and asymptotic optimality
Venue: arXiv cs.PF 2011
Year: 2011

We investigate the scheduling of a common resource between several concurrent users when the feasible transmission rate of each user varies randomly over time. Time is slotted and users arrive and depart upon service completion. This may model for example the flow-level behavior of end-users in a narrowband HDR wireless channel (CDMA 1xEV-DO). As performance criteria we consider the stability of the system and the mean delay experienced by the users. Given the complexity of the problem we investigate the fluid-scaled system, which allows to obtain important results and insights for the original system: (1) We characterize for a large class of scheduling policies the stability conditions and identify a set of maximum stable policies, giving in each time slot preference to users being in their best possible channel condition. We find in particular that many opportunistic scheduling policies like Score-Based, Proportionally Best or Potential Improvement are stable under the maximum stability conditions, whereas the opportunistic scheduler Relative-Best or the cmu-rule are not. (2) We show that choosing the right tie-breaking rule is crucial for the performance (e.g. average delay) as perceived by a user. We prove that a policy is asymptotically optimal if it is maximum stable and the tie-breaking rule gives priority to the user with the highest departure probability. We will refer to such tie-breaking rule as myopic. (3) We derive the growth rates of the number of users in the system in overload settings under various policies, which give additional insights on the performance. (4) We conclude that simple priority-index policies with the myopic tie-breaking rule, are stable and asymptotically optimal. All our findings are validated with extensive numerical experiments.
The VC-Dimension of Queries and Selectivity Estimation Through Sampling
Venue: arXiv cs.DB 2011
Year: 2011

We develop a novel method, based on the statistical concept of the Vapnik-Chervonenkis dimension, to evaluate the selectivity (output cardinality) of SQL queries - a crucial step in optimizing the execution of large scale database and data-mining operations. The major theoretical contribution of this work, which is of independent interest, is an explicit bound to the VC-dimension of a range space defined by all possible outcomes of a collection (class) of queries. We prove that the VC-dimension is a function of the maximum number of Boolean operations in the selection predicate and of the maximum number of select and join operations in any individual query in the collection, but it is neither a function of the number of queries in the collection nor of the size (number of tuples) of the database. We leverage on this result and develop a method that, given a class of queries, builds a concise random sample of a database, such that with high probability the execution of any query in the class on the sample provides an accurate estimate for the selectivity of the query on the original large database. The error probability holds simultaneously for the selectivity estimates of all queries in the collection, thus the same sample can be used to evaluate the selectivity of multiple queries, and the sample needs to be refreshed only following major changes in the database. The sample representation computed by our method is typically sufficiently small to be stored in main memory. We present extensive experimental results, validating our theoretical analysis and demonstrating the advantage of our technique when compared to complex selectivity estimation techniques used in PostgreSQL and the Microsoft SQL Server.
Avalanche Structure in the Kadanoff Sand Pile Model
Venue: arXiv cs.DM 2011
Year: 2011

Sand pile models are dynamical systems emphasizing the phenomenon of Self Organized Criticality (SOC). From N stacked grains, iterating evolution rules leads to some critical configuration where a small disturbance has deep consequences on the system, involving numerous steps of grain fall. Physicists L. Kadanoff et al. inspire KSPM, a model presenting a sharp SOC behavior, extending the well known Sand Pile Model. In KSPM with parameter D we start from a pile of N stacked grains and apply the rule: D-1 grains can fall from column i onto the D-1 adjacent columns to the right if the difference of height between columns i and i+1 is greater or equal to D. We propose an iterative study of KSPM evolution where one single grain addition is repeated on a heap of sand. The sequence of grain falls following a single grain addition is called an avalanche. From a certain column precisely studied for D=3, we provide a plain process describing avalanches.
A Kind of Representation of Common Knowledge and its Application in Requirements Analysis
Venue: arXiv cs.SE 2011
Year: 2011

Since the birth of software engineering, it always are recognized as one pure engineering subject, therefore, the foundational scientific problems are not paid much attention. This paper proposes that Requirements Analysis, the kernel process of software engineering, can be modeled based on the concept of "common knowledge". Such a model would make us understand the nature of this process. This paper utilizes the formal language as the tool to characterize the "common knowledge"-based Requirements Analysis model, and theoretically proves that : 1) the precondition of success of software projects regardless of cost would be that the participants in a software project have fully known the requirement specification, if the participants do not understand the meaning of the other participants; 2) the precondition of success of software projects regardless of cost would be that the union set of knowledge of basic facts of the participants in a software project can fully cover the requirement specification, if the participants can always understand the meaning of the other participants. These two theorems may have potential meanings to propose new software engineering methodology.
On the Analysis of Weighted Nonbinary Repeat Multiple-Accumulate Codes
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we consider weighted nonbinary repeat multiple-accumulate (WNRMA) code ensembles obtained from the serial concatenation of a nonbinary rate-1/n repeat code and the cascade of L>= 1 accumulators, where each encoder is followed by a nonbinary random weighter. The WNRMA codes are assumed to be iteratively decoded using the turbo principle with maximum a posteriori constituent decoders. We derive the exact weight enumerator of nonbinary accumulators and subsequently give the weight enumerators for WNRMA code ensembles. We formally prove that the symbol-wise minimum distance of WNRMA code ensembles asymptotically grows linearly with the block length when L >= 3 and n >= 2, and L=2 and n >= 3, for all powers of primes q >= 3 considered, where q is the field size. Thus, WNRMA code ensembles are asymptotically good for these parameters. We also give iterative decoding thresholds, computed by an extrinsic information transfer chart analysis, on the q-ary symmetric channel to show the convergence properties. Finally, we consider the binary image of WNRMA code ensembles and compare the asymptotic minimum distance growth rates with those of binary repeat multiple-accumulate code ensembles.
New Model for Multi-Objective Evolutionary Algorithms
Venue: arXiv cs.NE 2011
Year: 2011

Multi-Objective Evolutionary Algorithms (MOEAs) have been proved efficient to deal with Multi-objective Optimization Problems (MOPs). Until now tens of MOEAs have been proposed. The unified mode would provide a more systematic approach to build new MOEAs. Here a new model is proposed which includes two sub-models based on two classes of different schemas of MOEAs. According to the new model, some representatives algorithms are decomposed and some interesting issues are discussed.
Let Cognitive Radios Imitate: Imitation-based Spectrum Access for Cognitive Radio Networks
Venue: arXiv cs.NI 2011
Year: 2011

In this paper, we tackle the problem of opportunistic spectrum access in large-scale cognitive radio networks, where the unlicensed Secondary Users (SU) access the frequency channels partially occupied by the licensed Primary Users (PU). Each channel is characterized by an availability probability unknown to the SUs. We apply evolutionary game theory to model the spectrum access problem and develop distributed spectrum access policies based on imitation, a behavior rule widely applied in human societies consisting of imitating successful behavior. We first develop two imitation-based spectrum access policies based on the basic Proportional Imitation (PI) rule and the more advanced Double Imitation (DI) rule given that a SU can imitate any other SUs. We then adapt the proposed policies to a more practical scenario where a SU can only imitate the other SUs operating on the same channel. A systematic theoretical analysis is presented for both scenarios on the induced imitation dynamics and the convergence properties of the proposed policies to an imitation-stable equilibrium, which is also the $ε$-optimum of the system. Simple, natural and incentive-compatible, the proposed imitation-based spectrum access policies can be implemented distributedly based on solely local interactions and thus is especially suited in decentralized adaptive learning environments as cognitive radio networks.
Power Allocation in Team Jamming Games in Wireless Ad Hoc Networks
Venue: arXiv cs.GT 2011
Year: 2011

In this work, we study the problem of power allocation in teams. Each team consists of two agents who try to split their available power between the tasks of communication and jamming the nodes of the other team. The agents have constraints on their total energy and instantaneous power usage. The cost function is the difference between the rates of erroneously transmitted bits of each team. We model the problem as a zero-sum differential game between the two teams and use {\it{Isaacs'}} approach to obtain the necessary conditions for the optimal trajectories. This leads to a continuous-kernel power allocation game among the players. Based on the communications model, we present sufficient conditions on the physical parameters of the agents for the existence of a pure strategy Nash equilibrium (PSNE). Finally, we present simulation results for the case when the agents are holonomic.
A polynomial 3-colorability algorithm with automatic generation of NO 3-colorability (i.e. Co-NP) short proofs
Venue: arXiv cs.DM 2011
Year: 2011

In this paper, an algorithm for determining 3-colorability, i.e. the decision problem (YES/NO), in planar graphs is presented. The algorithm, although not exact (it could produce false positives) has two very important features: (i) it has polynomial complexity and (ii) for every "NO" answer, a "short" proof is generated, which is of much interest since 3-colorability is a NP-complete problem and thus its complementary problem is in Co-NP. Hence the algorithm is exact when it determines that a given planar graph is not 3-colorable since this is verifiable via an automatic generation of short formal proofs (also human-readable).
Tensor Rank: Some Lower and Upper Bounds
Venue: arXiv cs.CC 2011
Year: 2011

The results of Strassen and Raz show that good enough tensor rank lower bounds have implications for algebraic circuit/formula lower bounds. We explore tensor rank lower and upper bounds, focusing on explicit tensors. For odd d, we construct field-independent explicit 0/1 tensors T:[n]^d->F with rank at least 2n^(floor(d/2))+n-Theta(d log n). This matches (over F_2) or improves (all other fields) known lower bounds for d=3 and improves (over any field) for odd d>3. We also explore a generalization of permutation matrices, which we denote permutation tensors. We show, by counting, that there exists an order-3 permutation tensor with super-linear rank. We also explore a natural class of permutation tensors, which we call group tensors. For any group G, we define the group tensor T_G^d:G^d->F, by T_G^d(g_1,...,g_d)=1 iff g_1 x ... x g_d=1_G. We give two upper bounds for the rank of these tensors. The first uses representation theory and works over large fields F, showing (among other things) that rank_F(T_G^d)<= |G|^(d/2). We also show that if this upper bound is tight, then super-linear tensor rank lower bounds would follow. The second upper bound uses interpolation and only works for abelian G, showing that over any field F that rank_F(T_G^d)<= O(|G|^(1+log d)log^(d-1)|G|). In either case, this shows that many permutation tensors have far from maximal rank, which is very different from the matrix case and thus eliminates many natural candidates for high tensor rank. We also explore monotone tensor rank. We give explicit 0/1 tensors T:[n]^d->F that have tensor rank at most dn but have monotone tensor rank exactly n^(d-1). This is a nearly optimal separation.
Partition Functions of Normal Factor Graphs
Venue: arXiv cs.IT 2011
Year: 2011

One of the most common types of functions in mathematics, physics, and engineering is a sum of products, sometimes called a partition function. After "normalization," a sum of products has a natural graphical representation, called a normal factor graph (NFG), in which vertices represent factors, edges represent internal variables, and half-edges represent the external variables of the partition function. In physics, so-called trace diagrams share similar features. We believe that the conceptual framework of representing sums of products as partition functions of NFGs is an important and intuitive paradigm that, surprisingly, does not seem to have been introduced explicitly in the previous factor graph literature. Of particular interest are NFG modifications that leave the partition function invariant. A simple subclass of such NFG modifications offers a unifying view of the Fourier transform, tree-based reparameterization, loop calculus, and the Legendre transform.
Vertices Belonging to All Critical Independent Sets of a Graph
Venue: arXiv cs.DM 2011
Year: 2011

Let G=(V,E) be a graph. A set S is independent if no two vertices from S are adjacent. The independence number alpha(G) is the cardinality of a maximum independent set, and mu(G) is the size of a maximum matching. The number id_{c}(G)=max{|I|-|N(I)|:I is an independent set} is called the critical independence difference of G, and A is critical if |A|-|N(A)|=id_{c}(G). We define core(G) as the intersection of all maximum independent sets, and ker(G)as the intersection of all critical independent sets. In this paper we prove that if a graph G is non-quasi-regularizable (i.e., there exists some independent set A, such that |A|>|N(A)|), then: ker(G) is a subset of core(G), and |ker(G)|> id_{c}(G) >= alpha(G)-mu(G) > 0.
Delays Induce an Exponential Memory Gap for Rendezvous in Trees
Venue: arXiv cs.DC 2011
Year: 2011

The aim of rendezvous in a graph is meeting of two mobile agents at some node of an unknown anonymous connected graph. In this paper, we focus on rendezvous in trees, and, analogously to the efforts that have been made for solving the exploration problem with compact automata, we study the size of memory of mobile agents that permits to solve the rendezvous problem deterministically. We assume that the agents are identical, and move in synchronous rounds. We first show that if the delay between the starting times of the agents is arbitrary, then the lower bound on memory required for rendezvous is Omega(log n) bits, even for the line of length n. This lower bound meets a previously known upper bound of O(log n) bits for rendezvous in arbitrary graphs of size at most n. Our main result is a proof that the amount of memory needed for rendezvous with simultaneous start depends essentially on the number L of leaves of the tree, and is exponentially less impacted by the number n of nodes. Indeed, we present two identical agents with O(log L + loglog n) bits of memory that solve the rendezvous problem in all trees with at most n nodes and at most L leaves. Hence, for the class of trees with polylogarithmically many leaves, there is an exponential gap in minimum memory size needed for rendezvous between the scenario with arbitrary delay and the scenario with delay zero. Moreover, we show that our upper bound is optimal by proving that Omega(log L + loglog n)$ bits of memory are required for rendezvous, even in the class of trees with degrees bounded by 3.
Design, Implementation and Characterization of a Cooperative Communications System
Venue: arXiv cs.IT 2011
Year: 2011

Cooperative communications is a class of techniques which seek to improve reliability and throughput in wireless systems by pooling the resources of distributed nodes. While cooperation can occur at different network layers and time scales, physical layer cooperation at symbol time scales offers the largest benefit in combating losses due to fading. However, symbol level cooperation poses significant implementation challenges, especially in synchronizing the behaviors and carrier frequencies of distributed nodes. We present the implementation and characterization of a complete, real-time cooperative physical layer transceiver built on the Rice Wireless Open-Access Research Platform (WARP). In our implementation autonomous nodes employ physical layer cooperation without a central synchronization source, and are capable of selecting between non-cooperative and cooperative communication per packet. Cooperative transmissions use a distributed Alamouti space-time block code and employ either amplify-and-forward or decode-and-forward relaying. We also present experimental results of our transceiver's real-time performance under a variety of topologies and propagation conditions. Our results clearly demonstrate significant performance gains (more than 40x improvement in PER in some topologies) provided by physical layer cooperation, even when subject to the constraints of a real-time implementation. We also present methodologies to isolate and understand the sources of performance bottlenecks in our design. As with all our work on WARP, our transceiver design and experimental framework are available via the open-source WARP repository for use by other wireless researchers.
Thin Client Web-Based Campus Information Systems for Fiji National University
Venue: arXiv cs.SE 2011
Year: 2011

Fiji National University is encountering many difficulties with its current administrative systems. These difficulties include accessibility, scalability, performance, flexibility and integration. We propose a new campus information system, FNU-CIS to addresses these difficulties. FNU-CIS has the potential to provide wide range of the services for students and staffs at the university. In order to assist in the design and implementation of proposed FNU-CIS, we present an overview, software architecture and prototype implementation of our proposed system. We discuss the key properties of our system, compare it with other similar systems available and outline our future plans for research in FNU-CIS implementation.
Persistent Robotic Tasks: Monitoring and Sweeping in Changing Environments
Venue: arXiv cs.RO 2011
Year: 2011

We present controllers that enable mobile robots to persistently monitor or sweep a changing environment. The changing environment is modeled as a field which grows in locations that are not within range of a robot, and decreases in locations that are within range of a robot. We assume that the robots travel on given closed paths. The speed of each robot along its path is controlled to prevent the field from growing unbounded at any location. We consider the space of speed controllers that can be parametrized by a finite set of basis functions. For a single robot, we develop a linear program that is guaranteed to compute a speed controller in this space to keep the field bounded, if such a controller exists. Another linear program is then derived whose solution is the speed controller that minimizes the maximum field value over the environment. We extend our linear program formulation to develop a multi-robot controller that keeps the field bounded. The multi-robot controller has the unique feature that it does not require communication among the robots. Simulation studies demonstrate the robustness of the controllers to modeling errors, and to stochasticity in the environment.
Domain decomposition schemes for the Stokes equation
Venue: arXiv cs.NA 2011
Year: 2011

Numerical algorithms for solving problems of mathematical physics on modern parallel computers employ various domain decomposition techniques. Domain decomposition schemes are developed here to solve numerically initial/boundary value problems for the Stokes system of equations in the primitive variables pressure-velocity. Unconditionally stable schemes of domain decomposition are based on the partition of unit for a computational domain and the corresponding Hilbert spaces of grid functions.
A Domain Specific Ontology Based Semantic Web Search Engine
Venue: arXiv cs.IR 2011
Year: 2011

Since its emergence in the 1990s the World Wide Web (WWW) has rapidly evolved into a huge mine of global information and it is growing in size everyday. The presence of huge amount of resources on the Web thus poses a serious problem of accurate search. This is mainly because today's Web is a human-readable Web where information cannot be easily processed by machine. Highly sophisticated, efficient keyword based search engines that have evolved today have not been able to bridge this gap. So comes up the concept of the Semantic Web which is envisioned by Tim Berners-Lee as the Web of machine interpretable information to make a machine processable form for expressing information. Based on the semantic Web technologies we present in this paper the design methodology and development of a semantic Web search engine which provides exact search results for a domain specific search. This search engine is developed for an agricultural Website which hosts agricultural information about the state of West Bengal.
CPC: programming with a massive number of lightweight threads
Venue: arXiv cs.PL 2011
Year: 2011

Threads are a convenient and modular abstraction for writing concurrent programs, but often fairly expensive. The standard alternative to threads, event-loop programming, allows much lighter units of concurrency, but leads to code that is difficult to write and even harder to understand. Continuation Passing C (CPC) is a translator that converts a program written in threaded style into a program written with events and native system threads, at the programmer's choice. Together with two undergraduate students, we taught ourselves how to program in CPC by writing Hekate, a massively concurrent network server designed to efficiently handle tens of thousands of simultaneously connected peers. In this paper, we describe a number of programming idioms that we learnt while writing Hekate; while some of these idioms are specific to CPC, many should be applicable to other programming systems with sufficiently cheap threads.
Axiomatic Attribution for Multilinear Functions
Venue: arXiv cs.GT 2011
Year: 2011

We study the attribution problem, that is, the problem of attributing a change in the value of a characteristic function to its independent variables. We make three contributions. First, we propose a formalization of the problem based on a standard cost sharing model. Second, we show that there is a unique attribution method that satisfies Dummy, Additivity, Conditional Nonnegativity, Affine Scale Invariance, and Anonymity for all characteristic functions that are the sum of a multilinear function and an additive function. We term this the Aumann-Shapley-Shubik method. Conversely, we show that such a uniqueness result does not hold for characteristic functions outside this class. Third, we study multilinear characteristic functions in detail; we describe a computationally efficient implementation of the Aumann-Shapley-Shubik method and discuss practical applications to pay-per-click advertising and portfolio analysis.