OpenRaiser/Intern-Atlas huggingface dataset:
Codes over Hurwitz integers
Venue: arXiv cs.IT 2012
Year: 2012

In this study, we obtain new classes of linear codes over Hurwitz integers equipped with a new metric. We refer to the metric as Hurwitz metric. The codes with respect to Hurwitz metric use in coded modu- lation schemes based on quadrature amplitude modulation (QAM)-type constellations, for which neither Hamming metric nor Lee metric. Also, we define decoding algorithms for these codes when up to two coordinates of a transmitted code vector are effected by error of arbitrary Hurwitz weight.
Data Mining: A prediction for performance improvement using classification
Venue: arXiv cs.IR 2012
Year: 2012

Now-a-days the amount of data stored in educational database increasing rapidly. These databases contain hidden information for improvement of students' performance. The performance in higher education in India is a turning point in the academics for all students. This academic performance is influenced by many factors, therefore it is essential to develop predictive data mining model for students' performance so as to identify the difference between high learners and slow learners student. In the present investigation, an experimental methodology was adopted to generate a database. The raw data was preprocessed in terms of filling up missing values, transforming values in one form into another and relevant attribute/ variable selection. As a result, we had 300 student records, which were used for by Byes classification prediction model construction. Keywords- Data Mining, Educational Data Mining, Predictive Model, Classification.
A Multimodal Biometric System Using Linear Discriminant Analysis For Improved Performance
Venue: arXiv cs.CV 2012
Year: 2012

Essentially a biometric system is a pattern recognition system which recognizes a user by determining the authenticity of a specific anatomical or behavioral characteristic possessed by the user. With the ever increasing integration of computers and Internet into daily life style, it has become necessary to protect sensitive and personal data. This paper proposes a multimodal biometric system which incorporates more than one biometric trait to attain higher security and to handle failure to enroll situations for some users. This paper is aimed at investigating a multimodal biometric identity system using Linear Discriminant Analysis as backbone to both facial and speech recognition and implementing such system in real-time using SignalWAVE.
Packing of Rigid Spanning Subgraphs and Spanning Trees
Venue: arXiv cs.DM 2012
Year: 2012

We prove that every (6k + 2l, 2k)-connected simple graph contains k rigid and l connected edge-disjoint spanning subgraphs. This implies a theorem of Jackson and Jordán [4] and a theorem of Jordán [6] on packing of rigid spanning subgraphs. Both these results are generalizations of the classical result of Lovász and Yemini [9] saying that every 6-connected graph is rigid for which our approach provides a transparent proof. Our result also gives two improved upper bounds on the connectivity of graphs that have interesting properties: (1) every 8-connected graph packs a spanning tree and a 2-connected spanning subgraph; (2) every 14-connected graph has a 2-connected orientation.
Social Networks Research Aspects: A Vast and Fast Survey Focused on the Issue of Privacy in Social Network Sites
Venue: arXiv cs.SI 2012
Year: 2012

The increasing participation of people in online activities in recent years like content publishing, and having different kinds of relationships and interactions, along with the emergence of online social networks and people's extensive tendency toward them, have resulted in generation and availability of a huge amount of valuable information that has never been available before, and have introduced some new, attractive, varied, and useful research areas to researchers. In this paper we try to review some of the accomplished research on information of SNSs (Social Network Sites), and introduce some of the attractive applications that analyzing this information has. This will lead to the introduction of some new research areas to researchers. By reviewing the research in this area we will present a categorization of research topics about online social networks. This categorization includes seventeen research subtopics or subareas that will be introduced along with some of the accomplished research in these subareas. According to the consequences (slight, significant, and sometimes catastrophic) that revelation of personal and private information has, a research area that researchers have vastly investigated is privacy in online social networks. After an overview on different research subareas of SNSs, we will get more focused on the subarea of privacy protection in social networks, and introduce different aspects of it along with a categorization of these aspects.
An Entertaining Example for the Usage of Bitwise Operations in Programming
Venue: arXiv cs.OH 2012
Year: 2012

The present study is meant to fill in some information gaps occurring in the most widespread and well-known educational and reference literature about programming. The stress is laid on a very useful instrument - the bitwise operations, topic which is, unfortunately, seldom dealt with in most of the well-known books on programming. In addition, the research is very useful as regards the topic of overloading operators in any Object-oriented programming course. Given some appropriate examples, with the emphasis being laid on some particular and data structures language constructions, the results are quite interesting. The algorithm of solving the popular Sudoku puzzle is one such entertaining example.
Construction of Learning Path Using Ant Colony Optimization from a Frequent Pattern Graph
Venue: arXiv cs.OH 2012
Year: 2012

In an e-Learning system a learner may come across multiple unknown terms, which are generally hyperlinked, while reading a text definition or theory on any topic. It becomes even harder when one tries to understand those unknown terms through further such links and they again find some new terms that have new links. As a consequence they get confused where to initiate from and what are the prerequisites. So it is very obvious for the learner to make a choice of what should be learnt before what. In this paper we have taken the data mining based frequent pattern graph model to define the association and sequencing between the words and then adopted the Ant Colony Optimization, an artificial intelligence approach, to derive a searching technique to obtain an efficient and optimized learning path to reach to a unknown term.
Min-Sum algorithm for lattices constructed by Construction D
Venue: arXiv cs.CR 2012
Year: 2012

The so-called min-sum algorithm has been applied for decoding lattices constructed by Construction D'. We generalize this iterative decoding algorithm to decode lattices constructed by Construction D. An upper bound on the decoding complexity per iteration, in terms of coding gain, label group sizes of the lattice and other factors is derived. We show that iterative decoding of LDGM lattices has a reasonably low complexity such that lattices with dimensions of a few thousands can be easily decoded.
Analysis of a Key Distribution Scheme in Secure Multicasting
Venue: arXiv cs.CR 2012
Year: 2012

This article presents an analysis of the secure key broadcasting scheme proposed by Wu, Ruan, Lai and Tseng. The study of the parameters of the system is based on a connection with a special type of symmetric equations over finite fields. We present two different attacks against the system, whose efficiency depends on the choice of the parameters. In particular, a time-memory tradeoff attack is described, effective when a parameter of the scheme is chosen without care. In such a situation, more than one third of the cases can be broken with a time and space complexity in the range of the square root of the complexity of the best attack suggested by Wu et al. against their system. This leads to a feasible attack in a realistic scenario.
Évaluation et consolidation d'un réseau lexical via un outil pour retrouver le mot sur le bout de la langue
Venue: arXiv cs.HC 2012
Year: 2012

Since September 2007, a large scale lexical network for French is under construction through methods based on some kind of popular consensus by means of games (JeuxDeMots project). Human intervention can be considered as marginal. It is limited to corrections, adjustments and validation of the senses of terms, which amounts to less than 0,5 % of the relations in the network. To appreciate the quality of this resource built by non-expert users (players of the game), we use a similar approach to its construction. The resource must be validated by laymen, persistent in time, on open class vocabulary. We suggest to check whether our tool is able to solve the Tip of the Tongue (TOT) problem. Just like JeuxDeMots, our tool can be considered as an on-line game. Like the former, it allows the acquisition of new relations, enriching thus the (existing) network.
An efficient parallel algorithm for the longest path problem in meshes
Venue: arXiv cs.DS 2012
Year: 2012

In this paper, first we give a sequential linear-time algorithm for the longest path problem in meshes. This algorithm can be considered as an improvement of [13]. Then based on this sequential algorithm, we present a constant-time parallel algorithm for the problem which can be run on every parallel machine.
A Solution to Fastest Distributed Consensus Problem for Generic Star & K-cored Star Networks
Venue: arXiv cs.IT 2012
Year: 2012

Distributed average consensus is the main mechanism in algorithms for decentralized computation. In distributed average consensus algorithm each node has an initial state, and the goal is to compute the average of these initial states in every node. To accomplish this task, each node updates its state by a weighted average of its own and neighbors' states, by using local communication between neighboring nodes. In the networks with fixed topology, convergence rate of distributed average consensus algorithm depends on the choice of weights. This paper studies the weight optimization problem in distributed average consensus algorithm. The network topology considered here is a star network where the branches have different lengths. Closed-form formulas of optimal weights and convergence rate of algorithm are determined in terms of the network's topological parameters. Furthermore generic K-cored star topology has been introduced as an alternative to star topology. The introduced topology benefits from faster convergence rate compared to star topology. By simulation better performance of optimal weights compared to other common weighting methods has been proved.
Queue-Dispatch Asynchronous Systems
Venue: arXiv cs.LO 2012
Year: 2012

To make the development of efficient multi-core applications easier, libraries, such as Grand Central Dispatch, have been proposed. When using such a library, the programmer writes so-called blocks, which are chunks of codes, and dispatches them, using synchronous or asynchronous calls, to several types of waiting queues. A scheduler is then responsible for dispatching those blocks on the available cores. Blocks can synchronize via a global memory. In this paper, we propose Queue-Dispatch Asynchronous Systems as a mathematical model that faithfully formalizes the synchronization mechanisms and the behavior of the scheduler in those systems. We study in detail their relationships to classical formalisms such as pushdown systems, Petri nets, fifo systems, and counter systems. Our main technical contributions are precise worst-case complexity results for the Parikh coverability problem for several subclasses of our model.
Generating Program Invariants via Interpolation
Venue: arXiv cs.SE 2012
Year: 2012

This article focuses on automatically generating polynomial equations that are inductive loop invariants of computer programs. We propose a new algorithm for this task, which is based on polynomial interpolation. Though the proposed algorithm is not complete, it is efficient and can be applied to a broader range of problems compared to existing methods targeting similar problems. The efficiency of our approach is testified by experiments on a large collection of programs. The current implementation of our method is based on dense interpolation, for which a total degree bound is needed. On the theoretical front, we study the degree and dimension of the invariant ideal of loops which have no branches and where the assignments define a P-solvable recurrence. In addition, we obtain sufficient conditions for non-trivial polynomial equation invariants to exist (resp. not to exist).
Data Mining as a Torch Bearer in Education Sector
Venue: arXiv cs.IR 2012
Year: 2012

Every data has a lot of hidden information. The processing method of data decides what type of information data produce. In India education sector has a lot of data that can produce valuable information. This information can be used to increase the quality of education. But educational institution does not use any knowledge discovery process approach on these data. Information and communication technology puts its leg into the education sector to capture and compile low cost information. Now a day a new research community, educational data mining (EDM), is growing which is intersection of data mining and pedagogy. In this paper we present roadmap of research done in EDM in various segment of education sector.
Scrabble is PSPACE-Complete
Venue: arXiv cs.CC 2012
Year: 2012

In this paper we study the computational complexity of the game of Scrabble. We prove the PSPACE-completeness of a derandomized model of the game, answering an open question of Erik Demaine and Robert Hearn.
A Factor-Graph Representation of Probabilities in Quantum Mechanics
Venue: arXiv cs.IT 2012
Year: 2012

A factor-graph representation of quantum-mechanical probabilities is proposed. Unlike standard statistical models, the proposed representation uses auxiliary variables (state variables) that are not random variables.
A multiagent urban traffic simulation
Venue: arXiv cs.AI 2012
Year: 2012

We built a multiagent simulation of urban traffic to model both ordinary traffic and emergency or crisis mode traffic. This simulation first builds a modeled road network based on detailed geographical information. On this network, the simulation creates two populations of agents: the Transporters and the Mobiles. Transporters embody the roads themselves; they are utilitarian and meant to handle the low level realism of the simulation. Mobile agents embody the vehicles that circulate on the network. They have one or several destinations they try to reach using initially their beliefs of the structure of the network (length of the edges, speed limits, number of lanes etc.). Nonetheless, when confronted to a dynamic, emergent prone environment (other vehicles, unexpectedly closed ways or lanes, traffic jams etc.), the rather reactive agent will activate more cognitive modules to adapt its beliefs, desires and intentions. It may change its destination(s), change the tactics used to reach the destination (favoring less used roads, following other agents, using general headings), etc. We describe our current validation of our model and the next planned improvements, both in validation and in functionalities.
A simple block representation of reversible cellular automata with time-symmetry
Venue: arXiv cs.DM 2012
Year: 2012

Reversible Cellular Automata (RCA) are a physics-like model of computation consisting of an array of identical cells, evolving in discrete time steps by iterating a global evolution G. Further, G is required to be shift-invariant (it acts the same everywhere), causal (information cannot be transmitted faster than some fixed number of cells per time step), and reversible (it has an inverse which verifies the same requirements). An important, though only recently studied special case is that of Time-symmetric Cellular Automata (TSCA), for which G and its inverse are related via a local operation. In this note we revisit the question of the Block representation of RCA, i.e. we provide a very simple proof of the existence of a reversible circuit description implementing G. This operational, bottom-up description of G turns out to be time-symmetric, suggesting interesting connections with TSCA. Indeed we prove, using a similar technique, that a wide class of them admit an Exact block representation (EBR), i.e. one which does not increase the state space.
On Approximation Lower Bounds for TSP with Bounded Metrics
Venue: arXiv cs.CC 2012
Year: 2012

We develop a new method for proving explicit approximation lower bounds for TSP problems with bounded metrics improving on the best up to now known bounds. They almost match the best known bounds for unbounded metric TSP problems. In particular, we prove the best known lower bound for TSP with bounded metrics for the metric bound equal to 4.
An iterative algorithm for parametrization of shortest length shift registers over finite rings
Venue: arXiv cs.IT 2012
Year: 2012

The construction of shortest feedback shift registers for a finite sequence S_1,...,S_N is considered over the finite ring Z_{p^r}. A novel algorithm is presented that yields a parametrization of all shortest feedback shift registers for the sequence of numbers S_1,...,S_N, thus solving an open problem in the literature. The algorithm iteratively processes each number, starting with S_1, and constructs at each step a particular type of minimal Gröbner basis. The construction involves a simple update rule at each step which leads to computational efficiency. It is shown that the algorithm simultaneously computes a similar parametrization for the reciprocal sequence S_N,...,S_1.
Floating-Point Numbers with Error Estimates (revised)
Venue: arXiv cs.NA 2012
Year: 2012

The study addresses the problem of precision in floating-point (FP) computations. A method for estimating the errors which affect intermediate and final results is proposed and a summary of many software simulations is discussed. The basic idea consists of representing FP numbers by means of a data structure collecting value and estimated error information. Under certain constraints, the estimate of the absolute error is accurate and has a compact statistical distribution. By monitoring the estimated relative error during a computation (an ad-hoc definition of relative error has been used), the validity of results can be ensured. The error estimate enables the implementation of robust algorithms, and the detection of ill-conditioned problems. A dynamic extension of number precision, under the control of error estimates, is advocated, in order to compute results within given error bounds. A reduced time penalty could be achieved by a specialized FP processor. The realization of a hardwired processor incorporating the method, with current technology, should not be anymore a problem and would make the practical adoption of the method feasible for most applications.
Construction of quasi-cyclic self-dual codes
Venue: arXiv cs.IT 2012
Year: 2012

There is a one-to-one correspondence between $\ell$-quasi-cyclic codes over a finite field $\mathbb F_q$ and linear codes over a ring $R = \mathbb F_q[Y]/(Y^m-1)$. Using this correspondence, we prove that every $\ell$-quasi-cyclic self-dual code of length $m\ell$ over a finite field $\mathbb F_q$ can be obtained by the {\it building-up} construction, provided that char $(\mathbb F_q)=2$ or $q \equiv 1 \pmod 4$, $m$ is a prime $p$, and $q$ is a primitive element of $\mathbb F_p$. We determine possible weight enumerators of a binary $\ell$-quasi-cyclic self-dual code of length $p\ell$ (with $p$ a prime) in terms of divisibility by $p$. We improve the result of [3] by constructing new binary cubic (i.e., $\ell$-quasi-cyclic codes of length $3\ell$) optimal self-dual codes of lengths $30, 36, 42, 48$ (Type I), 54 and 66. We also find quasi-cyclic optimal self-dual codes of lengths 40, 50, and 60. When $m=5$, we obtain a new 8-quasi-cyclic self-dual $[40, 20, 12]$ code over $\mathbb F_3$ and a new 6-quasi-cyclic self-dual $[30, 15, 10]$ code over $\mathbb F_4$. When $m=7$, we find a new 4-quasi-cyclic self-dual $[28, 14, 9]$ code over $\mathbb F_4$ and a new 6-quasi-cyclic self-dual $[42,21,12]$ code over $\mathbb F_4$.
Compact Symbolic Execution (technical report)
Venue: arXiv cs.SE 2012
Year: 2012

We present a generalisation of King's symbolic execution technique called compact symbolic execution. It is based on a concept of templates: a template is a declarative parametric description of such a program part, generating paths in symbolic execution tree with regularities in program states along them. Typical sources of these paths are program loops and recursive calls. Using the templates we fold the corresponding paths into single vertices and therefore considerably reduce size of the tree without loss of any information. There are even programs for which compact symbolic execution trees are finite even though the classic symbolic execution trees are infinite.
Programming errors in traversal programs over structured data
Venue: arXiv cs.PL 2012
Year: 2012

Traversal strategies á la Stratego (also á la Strafunski and 'Scrap Your Boilerplate') provide an exceptionally versatile and uniform means of querying and transforming deeply nested and heterogeneously structured data including terms in functional programming and rewriting, objects in OO programming, and XML documents in XML programming. However, the resulting traversal programs are prone to programming errors. We are specifically concerned with errors that go beyond conservative type errors; examples we examine include divergent traversals, prematurely terminated traversals, and traversals with dead code. Based on an inventory of possible programming errors we explore options of static typing and static analysis so that some categories of errors can be avoided. This exploration generates suggestions for improvements to strategy libraries as well as their underlying programming languages. Haskell is used for illustrations and specifications with sufficient explanations to make the presentation comprehensible to the non-specialist. The overall ideas are language-agnostic and they are summarized accordingly.
Throughput Optimal Switching in Multi-channel WLANs
Venue: arXiv cs.SY 2012
Year: 2012

We observe that in a multi-channel wireless system, an opportunistic channel/spectrum access scheme that solely focuses on channel quality sensing measured by received SNR may induce users to use channels that, while providing better signals, are more congested. Ultimately the notion of channel quality should include both the signal quality and the level of congestion, and a good multi-channel access scheme should take both into account in deciding which channel to use and when. Motivated by this, we focus on the congestion aspect and examine what type of dynamic channel switching schemes may result in the best system throughput performance. Specifically we derive the stability region of a multi-user multi-channel WLAN system and determine the throughput optimal channel switching scheme within a certain class of schemes.
An Efficient Method for Mining Event-Related Potential Patterns
Venue: arXiv cs.DB 2012
Year: 2012

In the present paper, we propose a Neuroelectromagnetic Ontology Framework (NOF) for mining Event-related Potentials (ERP) patterns as well as the process. The aim for this research is to develop an infrastructure for mining, analysis and sharing the ERP domain ontologies. The outcome of this research is a Neuroelectromagnetic knowledge-based system. The framework has 5 stages: 1) Data pre-processing and preparation; 2) Data mining application; 3) Rule Comparison and Evaluation; 4) Association rules Post-processing 5) Domain Ontologies. In 5th stage a new set of hidden rules can be discovered base on comparing association rules by domain ontologies and expert rules.