OpenRaiser/Intern-Atlas huggingface dataset:
On Linear Index Coding for Random Graphs
Venue: arXiv cs.IT 2011
Year: 2011

A sender wishes to broadcast an n character word x in F^n (for a field F) to n receivers R_1,...,R_n. Every receiver has some side information on x consisting of a subset of the characters of x. The side information of the receivers is represented by a graph G on n vertices in which {i,j} is an edge if R_i knows x_j. In the index coding problem the goal is to encode x using a minimum number of characters in F in a way that enables every R_i to retrieve the ith character x_i using the encoded message and the side information. An index code is linear if the encoding is linear, and in this case the minimum possible length is known to be equal to a graph parameter called minrank (Bar-Yossef et al., FOCS'06). Several bounds on the minimum length of an index code for side information graphs G were shown in the study of index coding. However, the minimum length of an index code for the random graph G(n,p) is far from being understood. In this paper we initiate the study of the typical minimum length of a linear index code for G(n,p) over a field F. First, we prove that for every constant size field F and a constant p, the minimum length of a linear index code for G(n,p) over F is almost surely Omega(\sqrt{n}). Second, we introduce and study the following two restricted models of index coding: 1. A locally decodable index code is an index code in which the receivers are allowed to query at most q characters from the encoded message. 2. A low density index code is a linear index code in which every character of the word x affects at most q characters in the encoded message. Equivalently, it is a linear code whose generator matrix has at most q nonzero entries in each row.
The second-price auction solves King Solomon's dilemma
Venue: arXiv cs.GT 2011
Year: 2011

The planner wants to give k identical, indivisible objects to the top k valuation agents at zero costs. Each agent knows her own valuation of the object and whether it is among the top k. Modify the (k+1)st-price sealed-bid auction by introducing a small participation fee and the option not to participate in it. This simple mechanism implements the desired outcome in iteratively undominated strategies. Moreover, no pair of agents can profitably deviate from the equilibrium by coordinating their strategies or bribing each other.
Abstraction Super-structuring Normal Forms: Towards a Theory of Structural Induction
Venue: arXiv cs.AI 2011
Year: 2011

Induction is the process by which we obtain predictive laws or theories or models of the world. We consider the structural aspect of induction. We answer the question as to whether we can find a finite and minmalistic set of operations on structural elements in terms of which any theory can be expressed. We identify abstraction (grouping similar entities) and super-structuring (combining topologically e.g., spatio-temporally close entities) as the essential structural operations in the induction process. We show that only two more structural operations, namely, reverse abstraction and reverse super-structuring (the duals of abstraction and super-structuring respectively) suffice in order to exploit the full power of Turing-equivalent generative grammars in induction. We explore the implications of this theorem with respect to the nature of hidden variables, radical positivism and the 2-century old claim of David Hume about the principles of connexion among ideas.
Homological Coordinatization
Venue: arXiv cs.CG 2011
Year: 2011

In this paper, we review a method for computing and parameterizing the set of homotopy classes of chain maps between two chain complexes. This is then applied to finding topologically meaningful maps between simplicial complexes, which in the context of topological data analysis, can be viewed as an extension of conventional unsupervised learning methods to simplicial complexes.
Applications of Discrepancy Theory in Multiobjective Approximation
Venue: arXiv cs.DS 2011
Year: 2011

We apply a multi-color extension of the Beck-Fiala theorem to show that the multiobjective maximum traveling salesman problem is randomized 1/2-approximable on directed graphs and randomized 2/3-approximable on undirected graphs. Using the same technique we show that the multiobjective maximum satisfiablilty problem is 1/2-approximable.
Infinitary Term Graph Rewriting
Venue: arXiv cs.LO 2011
Year: 2011

Term graph rewriting provides a formalism for implementing term rewriting in an efficient manner by avoiding duplication. Infinitary term rewriting has been introduced to study infinite term reduction sequences. Such infinite reductions can be used to reason about lazy evaluation. In this paper, we combine term graph rewriting and infinitary term rewriting thereby addressing both components of lazy evaluation: non-strictness and sharing. Moreover, we show how our theoretical underpinnings, based on a metric space and a complete semilattice, provides a unified framework for both term rewriting and term graph rewriting. This makes it possible to study the correspondences between these two worlds. As an example, we show how the soundness of term graph rewriting w.r.t. term rewriting can be extended to the infinitary setting.
Generalized Maneuvers in Route Planning
Venue: arXiv cs.DS 2011
Year: 2011

We study an important practical aspect of the route planning problem in real-world road networks -- maneuvers. Informally, maneuvers represent various irregularities of the road network graph such as turn-prohibitions, traffic light delays, round-abouts, forbidden passages and so on. We propose a generalized model which can handle arbitrarily complex (and even negative) maneuvers, and outline how to enhance Dijkstra's algorithm in order to solve route planning queries in this model without prior adjustments of the underlying road network graph.
Online Vehicle Detection For Estimating Traffic Status
Venue: arXiv cs.CV 2011
Year: 2011

We propose a traffic congestion estimation system based on unsupervised on-line learning algorithm. The system does not rely on background extraction or motion detection. It extracts local features inside detection regions of variable size which are drawn on lanes in advance. The extracted features are then clustered into two classes using K-means and Gaussian Mixture Models(GMM). A Bayes classifier is used to detect vehicles according to the previous cluster information which keeps updated whenever system is running by on-line EM algorithm. Experimental result shows that our system can be adapted to various traffic scenes for estimating traffic status.
Genome Halving by Block Interchange
Venue: arXiv cs.DS 2011
Year: 2011

We address the problem of finding the minimal number of block interchanges (exchange of two intervals) required to transform a duplicated linear genome into a tandem duplicated linear genome. We provide a formula for the distance as well as a polynomial time algorithm for the sorting problem.
Finite Projective Geometry based Fast, Conflict-free Parallel Matrix Computations
Venue: arXiv cs.NA 2011
Year: 2011

Matrix computations, especially iterative PDE solving (and the sparse matrix vector multiplication subproblem within) using conjugate gradient algorithm, and LU/Cholesky decomposition for solving system of linear equations, form the kernel of many applications, such as circuit simulators, computational fluid dynamics or structural analysis etc. The problem of designing approaches for parallelizing these computations, to get good speedups as much as possible as per Amdahl's law, has been continuously researched upon. In this paper, we discuss approaches based on the use of finite projective geometry graphs for these two problems. For the problem of conjugate gradient algorithm, the approach looks at an alternative data distribution based on projective-geometry concepts. It is proved that this data distribution is an optimal data distribution for scheduling the main problem of dense matrix-vector multiplication. For the problem of parallel LU/Cholesky decomposition of general matrices, the approach is motivated by the recently published scheme for interconnects of distributed systems, perfect difference networks. We find that projective-geometry based graphs indeed offer an exciting way of parallelizing these computations, and in fact many others. Moreover, their applications ranges from architectural ones (interconnect choice) to algorithmic ones (data distributions).
Reachability Analysis of Time Basic Petri Nets: a Time Coverage Approach
Venue: arXiv cs.SE 2011
Year: 2011

We introduce a technique for reachability analysis of Time-Basic (TB) Petri nets, a powerful formalism for real- time systems where time constraints are expressed as intervals, representing possible transition firing times, whose bounds are functions of marking's time description. The technique consists of building a symbolic reachability graph relying on a sort of time coverage, and overcomes the limitations of the only available analyzer for TB nets, based in turn on a time-bounded inspection of a (possibly infinite) reachability-tree. The graph construction algorithm has been automated by a tool-set, briefly described in the paper together with its main functionality and analysis capability. A running example is used throughout the paper to sketch the symbolic graph construction. A use case describing a small real system - that the running example is an excerpt from - has been employed to benchmark the technique and the tool-set. The main outcome of this test are also presented in the paper. Ongoing work, in the perspective of integrating with a model-checking engine, is shortly discussed.
QuantUM: Quantitative Safety Analysis of UML Models
Venue: arXiv cs.SE 2011
Year: 2011

When developing a safety-critical system it is essential to obtain an assessment of different design alternatives. In particular, an early safety assessment of the architectural design of a system is desirable. In spite of the plethora of available formal quantitative analysis methods it is still difficult for software and system architects to integrate these techniques into their every day work. This is mainly due to the lack of methods that can be directly applied to architecture level models, for instance given as UML diagrams. Also, it is necessary that the description methods used do not require a profound knowledge of formal methods. Our approach bridges this gap and improves the integration of quantitative safety analysis methods into the development process. All inputs of the analysis are specified at the level of a UML model. This model is then automatically translated into the analysis model, and the results of the analysis are consequently represented on the level of the UML model. Thus the analysis model and the formal methods used during the analysis are hidden from the user. We illustrate the usefulness of our approach using an industrial strength case study.
Improvements for Free
Venue: arXiv cs.PL 2011
Year: 2011

"Theorems for Free!" (Wadler, FPCA 1989) is a slogan for a technique that allows to derive statements about functions just from their types. So far, the statements considered have always had a purely extensional flavor: statements relating the value semantics of program expressions, but not statements relating their runtime (or other) cost. Here we study an extension of the technique that allows precisely statements of the latter flavor, by deriving quantitative theorems for free. After developing the theory, we walk through a number of example derivations. Probably none of the statements derived in those simple examples will be particularly surprising to most readers, but what is maybe surprising, and at the very least novel, is that there is a general technique for obtaining such results on a quantitative level in a principled way. Moreover, there is good potential to bring that technique to bear on more complex examples as well. We turn our attention to short-cut fusion (Gill et al., FPCA 1993) in particular.
Analysis of Non-Linear Probabilistic Hybrid Systems
Venue: arXiv cs.LO 2011
Year: 2011

This paper shows how to compute, for probabilistic hybrid systems, the clock approximation and linear phase-portrait approximation that have been proposed for non probabilistic processes by Henzinger et al. The techniques permit to define a rectangular probabilistic process from a non rectangular one, hence allowing the model-checking of any class of systems. Clock approximation, which applies under some restrictions, aims at replacing a non rectangular variable by a clock variable. Linear phase-approximation applies without restriction and yields an approximation that simulates the original process. The conditions that we need for probabilistic processes are the same as those for the classic case.
Bidirected minimum Manhattan network problem
Venue: arXiv cs.CG 2011
Year: 2011

In the bidirected minimum Manhattan network problem, given a set T of n terminals in the plane, we need to construct a network N(T) of minimum total length with the property that the edges of N(T) are axis-parallel and oriented in a such a way that every ordered pair of terminals is connected in N(T) by a directed Manhattan path. In this paper, we present a polynomial factor 2 approximation algorithm for the bidirected minimum Manhattan network problem.
The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent
Venue: arXiv cs.CC 2011
Year: 2011

Polynomial identity testing and arithmetic circuit lower bounds are two central questions in algebraic complexity theory. It is an intriguing fact that these questions are actually related. One of the authors of the present paper has recently proposed a "real τ-conjecture" which is inspired by this connection. The real τ-conjecture states that the number of real roots of a sum of products of sparse univariate polynomials should be polynomially bounded. It implies a superpolynomial lower bound on the size of arithmetic circuits computing the permanent polynomial. In this paper we show that the real τ-conjecture holds true for a restricted class of sums of products of sparse polynomials. This result yields lower bounds for a restricted class of depth-4 circuits: we show that polynomial size circuits from this class cannot compute the permanent, and we also give a deterministic polynomial identity testing algorithm for the same class of circuits.
On Codes for Optimal Rebuilding Access
Venue: arXiv cs.IT 2011
Year: 2011

MDS (maximum distance separable) array codes are widely used in storage systems due to their computationally efficient encoding and decoding procedures. An MDS code with r redundancy nodes can correct any r erasures by accessing (reading) all the remaining information in both the systematic nodes and the parity (redundancy) nodes. However, in practice, a single erasure is the most likely failure event; hence, a natural question is how much information do we need to access in order to rebuild a single storage node? We define the rebuilding ratio as the fraction of remaining information accessed during the rebuilding of a single erasure. In our previous work we showed that the optimal rebuilding ratio of 1/r is achievable (using our newly constructed array codes) for the rebuilding of any systematic node, however, all the information needs to be accessed for the rebuilding of the parity nodes. Namely, constructing array codes with a rebuilding ratio of 1/r was left as an open problem. In this paper, we solve this open problem and present array codes that achieve the lower bound of 1/r for rebuilding any single systematic or parity node.
Throughput Computation in CSMA Wireless Networks with Collision Effects
Venue: arXiv cs.NI 2011
Year: 2011

It is known that link throughputs of CSMA wireless networks can be computed from a time-reversible Markov chain arising from an ideal CSMA network model (ICN). In particular, this model yields general closed-form equations of link throughputs. However, an idealized and important assumption made in ICN is that the backoff countdown process is in "contiuous-time" and carrier sensing is instantaneous. As a result, there is no collision in ICN. In practical CSMA protocols such as IEEE 802.11, the stations count down in "mini-timeslot" and the process is therefore a "discrete-time" process. In particular, two stations may end their backoff process in the same mini-timeslot and then transmit simultaneously, resulting in a packet collision. This paper is an attempt to study how to compute link throughputs after taking such backoff collision effects into account. We propose a generalized ideal CSMA network model (GICN) to characterize the collision states as well as the interactions and dependency among links in the network. We show that link throughputs and collision probability can be computed from GICN. Simulation results validate GICN's accuracy. Interestingly, we also find that the original ICN model yields fairly accurate results despite the fact that collisions are not modeled.
A Step towards an Easy Interconversion of Various Number Systems
Venue: arXiv cs.DM 2011
Year: 2011

Any system that is used for naming or representing numbers is a number system, also known as numeral system. The modern civilization is familiar with decimal number system using ten digits. However digital devices and computers use binary number system instead of decimal number system, using only two digits namely, 0 and 1 based on the fundamental concept of the decimal number system. Various other number systems also used this fundamental concept of decimal number system, for example octal system and hexadecimal number systems using eight and sixteen digits respectively. The knowledge of number systems and their inter conversion is essential for understanding of computers. More over, successful programming for digital devices requires a precise understanding of data formats, number systems and their inter conversion. The inter conversion (a process in which things are each converted into the other) of number system requires allot of time and techniques to expertise. In this paper the interconversion of four most common number systems is taken under the consideration in tabulated form. It is a step towards the easy interconversion of theses number systems to understand as well as memorise it. The four number systems are binary, octal, decimal and hexadecimal.
Information-Theoretic Measures for Objective Evaluation of Classifications
Venue: arXiv cs.CV 2011
Year: 2011

This work presents a systematic study of objective evaluations of abstaining classifications using Information-Theoretic Measures (ITMs). First, we define objective measures for which they do not depend on any free parameter. This definition provides technical simplicity for examining "objectivity" or "subjectivity" directly to classification evaluations. Second, we propose twenty four normalized ITMs, derived from either mutual information, divergence, or cross-entropy, for investigation. Contrary to conventional performance measures that apply empirical formulas based on users' intuitions or preferences, the ITMs are theoretically more sound for realizing objective evaluations of classifications. We apply them to distinguish "error types" and "reject types" in binary classifications without the need for input data of cost terms. Third, to better understand and select the ITMs, we suggest three desirable features for classification assessment measures, which appear more crucial and appealing from the viewpoint of classification applications. Using these features as "meta-measures", we can reveal the advantages and limitations of ITMs from a higher level of evaluation knowledge. Numerical examples are given to corroborate our claims and compare the differences among the proposed measures. The best measure is selected in terms of the meta-measures, and its specific properties regarding error types and reject types are analytically derived.
Knowledge Embedding and Retrieval Strategies in an Informledge System
Venue: arXiv cs.AI 2011
Year: 2011

Informledge System (ILS) is a knowledge network with autonomous nodes and intelligent links that integrate and structure the pieces of knowledge. In this paper, we put forward the strategies for knowledge embedding and retrieval in an ILS. ILS is a powerful knowledge network system dealing with logical storage and connectivity of information units to form knowledge using autonomous nodes and multi-lateral links. In ILS, the autonomous nodes known as Knowledge Network Nodes (KNN)s play vital roles which are not only used in storage, parsing and in forming the multi-lateral linkages between knowledge points but also in helping the realization of intelligent retrieval of linked information units in the form of knowledge. Knowledge built in to the ILS forms the shape of sphere. The intelligence incorporated into the links of a KNN helps in retrieving various knowledge threads from a specific set of KNNs. A developed entity of information realized through KNN forms in to the shape of a knowledge cone
Particle Swarm Optimization for Realizing Intelligent Routing in Networks with Quality Grading
Venue: arXiv cs.NI 2011
Year: 2011

Significant research has been carried out in the recent years for generating systems exhibiting intelligence for realizing optimized routing in networks. In this paper, a grade based twolevel based node selection method along with Particle Swarm Optimization (PSO) technique is proposed. It assumes that the nodes are intelligent and there exist a knowledge base about the environment in their local memory. There are two levels for approaching the effective route selection process through grading. At the first level, grade based selection is applied and at the second level, the optimum path is explored using PSO. The simulation has been carried out on different topological structures and it is observed that a graded network produces a significant reduction in number of iteration to arrive at the optimal path selection.
A Novel Adaptive Routing through Fitness Function Estimation Technique with Multiple QoS Parameters Compliance
Venue: arXiv cs.NI 2011
Year: 2011

The paper presents a method which shows a significant improvement in discovering the path over the distance vector protocol. The proposed method is a multi-parameter QoS along with the fitness function which shows that it overcomes the limitation of DV like routing loops by spanning tree approach, count-to-infinity problem by decision attribute. The input considered is a topology satisfying the QoS parameters of size 1 to 64 nodes and it was shown that an optimal path selection was obtained efficiently over the classical distance vector algorithm
On an Efficient Marie Curie Initial Training Network
Venue: arXiv cs.SI 2011
Year: 2011

Collaboration in science is one of the key components of world-class research. The European Commission supports collaboration between institutions and funds young researchers appointed by these partner institutions. In these networks, the mobility of the researchers is enforced in order to enhance the collaboration. In this study, based on a real Marie Curie Initial Training Network, an algorithm to construct a collaboration network is investigated. The algorithm suggests that a strongly efficient expansion leads to a star-like network. The results might help the design of efficient collaboration networks for future Initial Training Network proposals.
One dimensional Convolutional Goppa Codes over the projective line
Venue: arXiv cs.IT 2011
Year: 2011

We give a general method to construct MDS one-dimensional convolutional codes. Our method generalizes previous constructions of H. Gluesing-Luerssen and B. Langfeld. Moreover we give a classification of one-dimensional Convolutional Goppa Codes and propose a characterization of MDS codes of this type.