OpenRaiser/Intern-Atlas huggingface dataset:
Common Representation of Information Flows for Dynamic Coalitions
Venue: arXiv cs.CR 2010
Year: 2010

We propose a formal foundation for reasoning about access control policies within a Dynamic Coalition, defining an abstraction over existing access control models and providing mechanisms for translation of those models into information-flow domain. The abstracted information-flow domain model, called a Common Representation, can then be used for defining a way to control the evolution of Dynamic Coalitions with respect to information flow.
Strategies in PRholog
Venue: arXiv cs.PL 2010
Year: 2010

PRholog is an experimental extension of logic programming with strategic conditional transformation rules, combining Prolog with Rholog calculus. The rules perform nondeterministic transformations on hedges. Queries may have several results that can be explored on backtracking. Strategies provide a control on rule applications in a declarative way. With strategy combinators, the user can construct more complex strategies from simpler ones. Matching with four different kinds of variables provides a flexible mechanism of selecting (sub)terms during execution. We give an overview on programming with strategies in PRholog and demonstrate how rewriting strategies can be expressed.
Not Every Domain of a Plain Decompressor Contains the Domain of a Prefix-Free One
Venue: arXiv cs.IT 2010
Year: 2010

C.Calude, A.Nies, L.Staiger, and F.Stephan posed the following question about the relation between plain and prefix Kolmogorov complexities (see their paper in DLT 2008 conference proceedings): does the domain of every optimal decompressor contain the domain of some optimal prefix-free decompressor? In this paper we provide a negative answer to this question.
Communication in a Poisson Field of Interferers -- Part I: Interference Distribution and Error Probability
Venue: arXiv cs.IT 2010
Year: 2010

We present a mathematical model for communication subject to both network interference and noise. We introduce a framework where the interferers are scattered according to a spatial Poisson process, and are operating asynchronously in a wireless environment subject to path loss, shadowing, and multipath fading. We consider both cases of slow and fast-varying interferer positions. The paper is comprised of two separate parts. In Part I, we determine the distribution of the aggregate network interference at the output of a linear receiver. We characterize the error performance of the link, in terms of average and outage probabilities. The proposed model is valid for any linear modulation scheme (e.g., M-ary phase shift keying or M-ary quadrature amplitude modulation), and captures all the essential physical parameters that affect network interference. Our work generalizes the conventional analysis of communication in the presence of additive white Gaussian noise and fast fading, allowing the traditional results to be extended to include the effect of network interference. In Part II of the paper, we derive the capacity of the link when subject to network interference and noise, and characterize the spectrum of the aggregate interference.
Towards a participatory E-learning 2.0 A new E-learning focused on learners and validation of the content
Venue: arXiv cs.CY 2010
Year: 2010

Our aim is to propose a collaborative methodological approach centred on learners and based on the Web 2.0 tools in order to make E-learning 2.0. It is based on a process consisting of four iterative steps which are: grouping, collaborating, validating and publishing content. In this context, learners will be the creators of the content of assigned courses in a virtual meeting through the chat. These contents will be validated after a pedagogical monitoring by the instructor through the class's blog and merged into a single course content published on a class wiki. Social interaction and sharing of files on the web will be the responsibility of social networks. The rest of the web 2.0 tools such as RSS feeds, tags, podcasts and video casts will be used as complementary tools in order to improve the quality of training. This methodological approach will allow E-learning 2.0 by ensuring a better interactivity, collaboration, sharing and an optimal exploitation of collaborative intelligence in the classroom.
Rate Region of the Gaussian Scalar-Help-Vector Source-Coding Problem
Venue: arXiv cs.IT 2010
Year: 2010

We determine the rate region of the Gaussian scalar-help-vector source-coding problem under a covariance matrix distortion constraint. The rate region is achieved by a Gaussian achievable scheme. We introduce a novel outer bounding technique to establish the converse of the main result. Our approach is based on lower bounding the problem with a potentially reduced dimensional problem by projecting the main source and imposing the distortion constraint in certain directions determined by the optimal Gaussian scheme. We also prove several properties that the optimal solution to the point-to-point rate-distortion problem for a vector Gaussian source under a covariance matrix distortion constraint satisfies. These properties play an important role in our converse proof. We further establish an outer bound to the rate region of the more general problem in which there are distortion constraints on both the sources. The outer bound is partially tight in general. We also study its tightness in some nontrivial cases.
The Citation Field of Evolutionary Economics
Venue: arXiv cs.DL 2010
Year: 2010

Evolutionary economics has developed into an academic field of its own, institutionalized around, amongst others, the Journal of Evolutionary Economics (JEE). This paper analyzes the way and extent to which evolutionary economics has become an interdisciplinary journal, as its aim was: a journal that is indispensable in the exchange of expert knowledge on topics and using approaches that relate naturally with it. Analyzing citation data for the relevant academic field for the Journal of Evolutionary Economics, we use insights from scientometrics and social network analysis to find that, indeed, the JEE is a central player in this interdisciplinary field aiming mostly at understanding technological and regional dynamics. It does not, however, link firmly with the natural sciences (including biology) nor to management sciences, entrepreneurship, and organization studies. Another journal that could be perceived to have evolutionary acumen, the Journal of Economic Issues, does relate to heterodox economics journals and is relatively more involved in discussing issues of firm and industry organization. The JEE seems most keen to develop theoretical insights.
Worst Configurations (Instantons) for Compressed Sensing over Reals: a Channel Coding Approach
Venue: arXiv cs.IT 2010
Year: 2010

We consider the Linear Programming (LP) solution of the Compressed Sensing (CS) problem over reals, also known as the Basis Pursuit (BasP) algorithm. The BasP allows interpretation as a channel-coding problem, and it guarantees error-free reconstruction with a properly chosen measurement matrix and sufficiently sparse error vectors. In this manuscript, we examine how the BasP performs on a given measurement matrix and develop an algorithm to discover the sparsest vectors for which the BasP fails. The resulting algorithm is a generalization of our previous results on finding the most probable error-patterns degrading performance of a finite size Low-Density Parity-Check (LDPC) code in the error-floor regime. The BasP fails when its output is different from the actual error-pattern. We design a CS-Instanton Search Algorithm (ISA) generating a sparse vector, called a CS-instanton, such that the BasP fails on the CS-instanton, while the BasP recovery is successful for any modification of the CS-instanton replacing a nonzero element by zero. We also prove that, given a sufficiently dense random input for the error-vector, the CS-ISA converges to an instanton in a small finite number of steps. The performance of the CS-ISA is illustrated on a randomly generated $120\times 512$ matrix. For this example, the CS-ISA outputs the shortest instanton (error vector) pattern of length 11.
Auction-based Bandwidth Allocation Mechanisms for Wireless Future Internet
Venue: arXiv cs.NI 2010
Year: 2010

An important aspect of the Future Internet is the efficient utilization of (wireless) network resources. In order for the - demanding in terms of QoS - Future Internet services to be provided, the current trend is evolving towards an "integrated" wireless network access model that enables users to enjoy mobility, seamless access and high quality of service in an all-IP network on an "Anytime, Anywhere" basis. The term "integrated" is used to denote that the Future Internet wireless "last mile" is expected to comprise multiple heterogeneous geographically coexisting wireless networks, each having different capacity and coverage radius. The efficient management of the wireless access network resources is crucial due to their scarcity that renders wireless access a potential bottleneck for the provision of high quality services. In this paper we propose an auction mechanism for allocating the bandwidth of such a network so that efficiency is attained, i.e. social welfare is maximized. In particular, we propose an incentive-compatible, efficient auction-based mechanism of low computational complexity. We define a repeated game to address user utilities and incentives issues. Subsequently, we extend this mechanism so that it can also accommodate multicast sessions. We also analyze the computational complexity and message overhead of the proposed mechanism. We then show how user bids can be replaced from weights generated by the network and transform the auction to a cooperative mechanism capable of prioritizing certain classes of services and emulating DiffServ and time-of-day pricing schemes. The theoretical analysis is complemented by simulations that assess the proposed mechanisms properties and performance. We finally provide some concluding remarks and directions for future research.
An Agent-Based Modeling for Pandemic Influenza in Egypt
Venue: arXiv cs.MA 2010
Year: 2010

Pandemic influenza has great potential to cause large and rapid increases in deaths and serious illness. The objective of this paper is to develop an agent-based model to simulate the spread of pandemic influenza (novel H1N1) in Egypt. The proposed multi-agent model is based on the modeling of individuals' interactions in a space time context. The proposed model involves different types of parameters such as: social agent attributes, distribution of Egypt population, and patterns of agents' interactions. Analysis of modeling results leads to understanding the characteristics of the modeled pandemic, transmission patterns, and the conditions under which an outbreak might occur. In addition, the proposed model is used to measure the effectiveness of different control strategies to intervene the pandemic spread.
Performance Comparisons of PSO based Clustering
Venue: arXiv cs.NE 2010
Year: 2010

In this paper we have investigated the performance of PSO Particle Swarm Optimization based clustering on few real world data sets and one artificial data set. The performances are measured by two metric namely quantization error and inter-cluster distance. The K means clustering algorithm is first implemented for all data sets, the results of which form the basis of comparison of PSO based approaches. We have explored different variants of PSO such as gbest, lbest ring, lbest vonneumann and Hybrid PSO for comparison purposes. The results reveal that PSO based clustering algorithms perform better compared to K means in all data sets.
Kannada Character Recognition System A Review
Venue: arXiv cs.CV 2010
Year: 2010

Intensive research has been done on optical character recognition ocr and a large number of articles have been published on this topic during the last few decades. Many commercial OCR systems are now available in the market, but most of these systems work for Roman, Chinese, Japanese and Arabic characters. There are no sufficient number of works on Indian language character recognition especially Kannada script among 12 major scripts in India. This paper presents a review of existing work on printed Kannada script and their results. The characteristics of Kannada script and Kannada Character Recognition System kcr are discussed in detail. Finally fusion at the classifier level is proposed to increase the recognition accuracy.
Threshold Based Indexing of Commercial Shoe Print to Create Reference and Recovery Images
Venue: arXiv cs.CV 2010
Year: 2010

One of the important evidence in a crime scene that is normally overlooked but very important evidence is shoe print as the criminal is normally unaware of the mask for this. In this paper we use image processing technique to process reference shoe images to make it index-able for a search from the database the shoe print impressions available in the commercial market. This is achieved first by converting the commercially available image through the process of converting them to gray scale then apply image enhancement and restoration techniques and finally do image segmentation to store the segmented parameter as index in the database storage. We use histogram method for image enhancement, inverse filtering for image restoration and threshold method for indexing. We use global threshold as index of the shoe print. The paper describes this method and simulation results are included to validate the method.
The Power of Vocabulary: The Case of Cyclotomic Polynomials
Venue: arXiv cs.SC 2010
Year: 2010

We observe that the vocabulary used to construct the "answer" to problems in computer algebra can have a dramatic effect on the computational complexity of solving that problem. We recall a formalization of this observation and explain the classic example of sparse polynomial arithmetic. For this case, we show that it is possible to extend the vocabulary so as reap the benefits of conciseness whilst avoiding the obvious pitfall of repeating the problem statement as the "solution". It is possible to extend the vocabulary either by irreducible cyclotomics or by $x^n-1$: we look at the options and suggest that the pragmatist might opt for both.
Multi-dimensional Boltzmann Sampling of Languages
Venue: arXiv cs.DS 2010
Year: 2010

This paper addresses the uniform random generation of words from a context-free language (over an alphabet of size $k$), while constraining every letter to a targeted frequency of occurrence. Our approach consists in a multidimensional extension of Boltzmann samplers \cite{Duchon2004}. We show that, under mostly \emph{strong-connectivity} hypotheses, our samplers return a word of size in $[(1-\varepsilon)n, (1+\varepsilon)n]$ and exact frequency in $\mathcal{O}(n^{1+k/2})$ expected time. Moreover, if we accept tolerance intervals of width in $Ω(\sqrt{n})$ for the number of occurrences of each letters, our samplers perform an approximate-size generation of words in expected $\mathcal{O}(n)$ time. We illustrate these techniques on the generation of Tetris tessellations with uniform statistics in the different types of tetraminoes.
Achievable rate regions and outer bounds for a multi-pair bi-directional relay network
Venue: arXiv cs.IT 2010
Year: 2010

In a bi-directional relay channel, a pair of nodes wish to exchange independent messages over a shared wireless half-duplex channel with the help of relays. Recent work has mostly considered information theoretic limits of the bi-directional relay channel with two terminal nodes (or end users) and one relay. In this work we consider bi-directional relaying with one base station, multiple terminal nodes and one relay, all of which operate in half-duplex modes. We assume that each terminal node communicates with the base-station in a bi-directional fashion through the relay and do not place any restrictions on the channels between the users, relays and base-stations; that is, each node has a direct link with every other node. Our contributions are three-fold: 1) the introduction of four new temporal protocols which fully exploit the two-way nature of the data and outperform simple routing or multi-hop communication schemes by carefully combining network coding, random binning and user cooperation which exploit over-heard and own-message side information, 2) derivations of inner and outer bounds on the capacity region of the discrete-memoryless multi-pair two-way network, and 3) a numerical evaluation of the obtained achievable rate regions and outer bounds in Gaussian noise which illustrate the performance of the proposed protocols compared to simpler schemes, to each other, to the outer bounds, which highlight the relative gains achieved by network coding, random binning and compress-and-forward-type cooperation between terminal nodes.
Extraction of Flat and Nested Data Records from Web Pages
Venue: arXiv cs.DB 2010
Year: 2010

This paper studies the problem of identification and extraction of flat and nested data records from a given web page. With the explosive growth of information sources available on the World Wide Web, it has become increasingly difficult to identify the relevant pieces of information, since web pages are often cluttered with irrelevant content like advertisements, navigation-panels, copyright notices etc., surrounding the main content of the web page. Hence, it is useful to mine such data regions and data records in order to extract information from such web pages to provide value-added services. Currently available automatic techniques to mine data regions and data records from web pages are still unsatisfactory because of their poor performance. In this paper a novel method to identify and extract the flat and nested data records from the web pages automatically is proposed. It comprises of two steps : (1) Identification and Extraction of the data regions based on visual clues information. (2) Identification and extraction of flat and nested data records from the data region of a web page automatically. For step1, a novel and more effective method is proposed, which finds the data regions formed by all types of tags using visual clues. For step2, a more effective and efficient method namely, Visual Clue based Extraction of web Data (VCED), is proposed, which extracts each record from the data region and identifies it whether it is a flat or nested data record based on visual clue information the area covered by and the number of data items present in each record. Our experimental results show that the proposed technique is effective and better than existing techniques.
Maximal f-vectors of Minkowski sums of large numbers of polytopes
Venue: arXiv cs.CG 2010
Year: 2010

It is known that in the Minkowski sum of $r$ polytopes in dimension $d$, with $r<d$, the number of vertices of the sum can potentially be as high as the product of the number of vertices in each summand. However, the number of vertices for sums of more polytopes was unknown so far. In this paper, we study sums of polytopes in general orientations, and show a linear relation between the number of faces of a sum of $r$ polytopes in dimension $d$, with $r\geq d$, and the number of faces in the sums of less than $d$ of the summand polytopes. We deduce from this exact formula a tight bound on the maximum possible number of vertices of the Minkowski sum of any number of polytopes in any dimension. In particular, the linear relation implies that a sum of $r$ polytopes in dimension $d$ has a number of vertices in $O(n^{d-1})$ of the total number of vertices in the summands, even when $r\geq d$. This bound is tight, in the sense that some sums do have that many vertices.
Bézout Identities Associated to a Finite Sequence
Venue: arXiv cs.IT 2010
Year: 2010

We consider finite sequences $s\in D^n$ where $D$ is a commutative, unital, integral domain. We prove three sets of identities (possibly with repetitions), each involving $2n$ polynomials associated to $s$. The right-hand side of these identities is a recursively-defined (non-zero) 'product-of-discrepancies'. There are implied iterative algorithms (of quadratic complexity) for the left-hand side coefficients; when the ground domain is factorial, the identities are in effect Bézout identities. We give a number of applications: an algorithm to compute Bézout coefficients over a field; the outputs of the Berlekamp-Massey algorithm; sequences with perfect linear complexity profile; annihilating polynomials which do not vanish at zero and have minimal degree: we simplify and extend an algorithm of Salagean to sequences over $D$. In the Appendix, we give a new proof of a theorem of Imamura and Yoshida on the linear complexity of reverse sequences, initially proved using Hankel matrices over a field and now valid for sequences over a factorial domain.
Construction et enrichissement automatique d'ontologie à partir de ressources externes
Venue: arXiv cs.IR 2010
Year: 2010

Automatic construction of ontologies from text is generally based on retrieving text content. For a much more rich ontology we extend these approaches by taking into account the document structure and some external resources (like thesaurus of indexing terms of near domain). In this paper we describe how these external resources are at first analyzed and then exploited. This method has been applied on a geographical domain and the benefit has been evaluated.
Systems of Linear Equations over $\mathbb{F}_2$ and Problems Parameterized Above Average
Venue: arXiv cs.DM 2010
Year: 2010

In the problem Max Lin, we are given a system $Az=b$ of $m$ linear equations with $n$ variables over $\mathbb{F}_2$ in which each equation is assigned a positive weight and we wish to find an assignment of values to the variables that maximizes the excess, which is the total weight of satisfied equations minus the total weight of falsified equations. Using an algebraic approach, we obtain a lower bound for the maximum excess. Max Lin Above Average (Max Lin AA) is a parameterized version of Max Lin introduced by Mahajan et al. (Proc. IWPEC'06 and J. Comput. Syst. Sci. 75, 2009). In Max Lin AA all weights are integral and we are to decide whether the maximum excess is at least $k$, where $k$ is the parameter. It is not hard to see that we may assume that no two equations in $Az=b$ have the same left-hand side and $n={\rm rank A}$. Using our maximum excess results, we prove that, under these assumptions, Max Lin AA is fixed-parameter tractable for a wide special case: $m\le 2^{p(n)}$ for an arbitrary fixed function $p(n)=o(n)$. Max $r$-Lin AA is a special case of Max Lin AA, where each equation has at most $r$ variables. In Max Exact $r$-SAT AA we are given a multiset of $m$ clauses on $n$ variables such that each clause has $r$ variables and asked whether there is a truth assignment to the $n$ variables that satisfies at least $(1-2^{-r})m + k2^{-r}$ clauses. Using our maximum excess results, we prove that for each fixed $r\ge 2$, Max $r$-Lin AA and Max Exact $r$-SAT AA can be solved in time $2^{O(k \log k)}+m^{O(1)}.$ This improves $2^{O(k^2)}+m^{O(1)}$-time algorithms for the two problems obtained by Gutin et al. (IWPEC 2009) and Alon et al. (SODA 2010), respectively.
MIMO Transmission with Residual Transmit-RF Impairments
Venue: arXiv cs.IT 2010
Year: 2010

Physical transceiver implementations for multiple-input multiple-output (MIMO) wireless communication systems suffer from transmit-RF (Tx-RF) impairments. In this paper, we study the effect on channel capacity and error-rate performance of residual Tx-RF impairments that defy proper compensation. In particular, we demonstrate that such residual distortions severely degrade the performance of (near-)optimum MIMO detection algorithms. To mitigate this performance loss, we propose an efficient algorithm, which is based on an i.i.d. Gaussian model for the distortion caused by these impairments. In order to validate this model, we provide measurement results based on a 4-stream Tx-RF chain implementation for MIMO orthogonal frequency-division multiplexing (OFDM).