OpenRaiser/Intern-Atlas huggingface dataset:
Multi-user lattice coding for the multiple-access relay channel
Venue: arXiv cs.IT 2013
Year: 2013

This paper considers the multi-antenna multiple access relay channel (MARC), in which multiple users transmit messages to a common destination with the assistance of a relay. In a variety of MARC settings, the dynamic decode and forward (DDF) protocol is very useful due to its outstanding rate performance. However, the lack of good structured codebooks so far hinders practical applications of DDF for MARC. In this work, two classes of structured MARC codes are proposed: 1) one-to-one relay-mapper aided multiuser lattice coding (O-MLC), and 2) modulo-sum relay-mapper aided multiuser lattice coding (MS-MLC). The former enjoys better rate performance, while the latter provides more flexibility to tradeoff between the complexity of the relay mapper and the rate performance. It is shown that, in order to approach the rate performance achievable by an unstructured codebook with maximum-likelihood decoding, it is crucial to use a new K-stage coset decoder for structured O-MLC, instead of the one-stage decoder proposed in previous works. However, if O-MLC is decoded with the one-stage decoder only, it can still achieve the optimal DDF diversity-multiplexing gain tradeoff in the high signal-to-noise ratio regime. As for MS-MLC, its rate performance can approach that of the O-MLC by increasing the complexity of the modulo-sum relay-mapper. Finally, for practical implementations of both O-MLC and MS-MLC, practical short length lattice codes with linear mappers are designed, which facilitate efficient lattice decoding. Simulation results show that the proposed coding schemes outperform existing schemes in terms of outage probabilities in a variety of channel settings.
Fast Multi-Scale Community Detection based on Local Criteria within a Multi-Threaded Algorithm
Venue: arXiv cs.DS 2013
Year: 2013

Many systems can be described using graphs, or networks. Detecting communities in these networks can provide information about the underlying structure and functioning of the original systems. Yet this detection is a complex task and a large amount of work was dedicated to it in the past decade. One important feature is that communities can be found at several scales, or levels of resolution, indicating several levels of organisations. Therefore solutions to the community structure may not be unique. Also networks tend to be large and hence require efficient processing. In this work, we present a new algorithm for the fast detection of communities across scales using a local criterion. We exploit the local aspect of the criterion to enable parallel computation and improve the algorithm's efficiency further. The algorithm is tested against large generated multi-scale networks and experiments demonstrate its efficiency and accuracy.
Charting the Tractability Frontier of Certain Conjunctive Query Answering
Venue: arXiv cs.DB 2013
Year: 2013

An uncertain database is defined as a relational database in which primary keys need not be satisfied. A repair (or possible world) of such database is obtained by selecting a maximal number of tuples without ever selecting two distinct tuples with the same primary key value. For a Boolean query q, the decision problem CERTAINTY(q) takes as input an uncertain database db and asks whether q is satisfied by every repair of db. Our main focus is on acyclic Boolean conjunctive queries without self-join. Previous work has introduced the notion of (directed) attack graph of such queries, and has proved that CERTAINTY(q) is first-order expressible if and only if the attack graph of q is acyclic. The current paper investigates the boundary between tractability and intractability of CERTAINTY(q). We first classify cycles in attack graphs as either weak or strong, and then prove among others the following. If the attack graph of a query q contains a strong cycle, then CERTAINTY(q) is coNP-complete. If the attack graph of q contains no strong cycle and every weak cycle of it is terminal (i.e., no edge leads from a vertex in the cycle to a vertex outside the cycle), then CERTAINTY(q) is in P. We then partially address the only remaining open case, i.e., when the attack graph contains some nonterminal cycle and no strong cycle. Finally, we establish a relationship between the complexities of CERTAINTY(q) and evaluating q on probabilistic databases.
Interactive Overlays of Journals and the Measurement of Interdisciplinarity on the basis of Aggregated Journal-Journal Citations
Venue: arXiv cs.DL 2013
Year: 2013

Using "Analyze Results" at the Web of Science, one can directly generate overlays onto global journal maps of science. The maps are based on the 10,000+ journals contained in the Journal Citation Reports (JCR) of the Science and Social Science Citation Indices (2011). The disciplinary diversity of the retrieval is measured in terms of Rao-Stirling's "quadratic entropy." Since this indicator of interdisciplinarity is normalized between zero and one, the interdisciplinarity can be compared among document sets and across years, cited or citing. The colors used for the overlays are based on Blondel et al.'s (2008) community-finding algorithms operating on the relations journals included in JCRs. The results can be exported from VOSViewer with different options such as proportional labels, heat maps, or cluster density maps. The maps can also be web-started and/or animated (e.g., using PowerPoint). The "citing" dimension of the aggregated journal-journal citation matrix was found to provide a more comprehensive description than the matrix based on the cited archive. The relations between local and global maps and their different functions in studying the sciences in terms of journal litteratures are further discussed: local and global maps are based on different assumptions and can be expected to serve different purposes for the explanation.
On the complexity of the Rank Syndrome Decoding problem
Venue: arXiv cs.CR 2013
Year: 2013

In this paper we propose two new generic attacks on the Rank Syndrome Decoding (RSD) problem Let $C$ be a random $[n,k]$ rank code over $GF(q^m)$ and let $y=x+e$ be a received word such that $x \in C$ and the $Rank(e)=r$. The first attack is combinatorial and permits to recover an error $e$ of rank weight $r$ in $min(O((n-k)^3m^3q^{r\lfloor\frac{km}{n}\rfloor}, O((n-k)^3m^3q^{(r-1)\lfloor\frac{(k+1)m}{n}\rfloor}))$ operations on $GF(q)$. This attack dramatically improves on previous attack by introducing the length $n$ of the code in the exponent of the complexity, which was not the case in previous generic attacks. which can be considered The second attack is based on a algebraic attacks: based on the theory of $q$-polynomials introduced by Ore we propose a new algebraic setting for the RSD problem that permits to consider equations and unknowns in the extension field $GF(q^m)$ rather than in $GF(q)$ as it is usually the case. We consider two approaches to solve the problem in this new setting. Linearization technics show that if $n \ge (k+1)(r+1)-1$ the RSD problem can be solved in polynomial time, more generally we prove that if $\lceil \frac{(r+1)(k+1)-(n+1)}{r} \rceil \le k$, the problem can be solved with an average complexity $O(r^3k^3q^{r\lceil \frac{(r+1)(k+1)-(n+1)}{r} \rceil})$. We also consider solving with \grob bases for which which we discuss theoretical complexity, we also consider consider hybrid solving with \grob bases on practical parameters. As an example of application we use our new attacks on all proposed recent cryptosystems which reparation the GPT cryptosystem, we break all examples of published proposed parameters, some parameters are broken in less than 1 s in certain cases.
Connecting Mobile Things to Global Sensor Network Middleware using System-generated Wrappers
Venue: arXiv cs.SE 2013
Year: 2013

Internet of Things (IoT) will create a cyberphysical world where all the things around us are connected to the Inter net, sense and produce "big data" that has to be stored, processed and communicated with minimum human intervention. With the ever increasing emergence of new sensors, interfaces and mobile devices, the grand challenge is to keep up with this race in developing software drivers and wrappers for IoT things. In this paper, we examine the approaches that automate the process of developing middleware drivers/wrappers for the IoT things. We propose ASCM4GSN architecture to address this challenge efficiently and effectively. We demonstrate the proposed approach using Global Sensor Network (GSN) middleware which exemplifies a cluster of data streaming engines. The ASCM4GSN architecture significantly speeds up the wrapper development and sensor configuration process as demonstrated for Android mobile phone based sensors as well as for Sun SPOT sensors.
Performance Analysis of Wireless Network with Opportunistic Spectrum Sharing via Cognitive Radio Nodes
Venue: arXiv cs.NI 2013
Year: 2013

Cognitive radio (CR) is found to be an emerging key for efficient spectrum utilization. In this paper, spectrum sharing among service providers with the help of cognitive radio has been investigated. The technique of spectrum sharing among service providers to share the licensed spectrum of licensed service providers in a dynamic manner is considered. The performance of the wireless network with opportunistic spectrum sharing techniques is analyzed. Thus, the spectral utilization and efficiency of sensing is increased, the interference is minimized, and the call blockage is reduced.
My Software has a Vulnerability, should I worry?
Venue: arXiv cs.CR 2013
Year: 2013

(U.S) Rule-based policies to mitigate software risk suggest to use the CVSS score to measure the individual vulnerability risk and act accordingly: an HIGH CVSS score according to the NVD (National (U.S.) Vulnerability Database) is therefore translated into a "Yes". A key issue is whether such rule is economically sensible, in particular if reported vulnerabilities have been actually exploited in the wild, and whether the risk score do actually match the risk of actual exploitation. We compare the NVD dataset with two additional datasets, the EDB for the white market of vulnerabilities (such as those present in Metasploit), and the EKITS for the exploits traded in the black market. We benchmark them against Symantec's threat explorer dataset (SYM) of actual exploit in the wild. We analyze the whole spectrum of CVSS submetrics and use these characteristics to perform a case-controlled analysis of CVSS scores (similar to those used to link lung cancer and smoking) to test its reliability as a risk factor for actual exploitation. We conclude that (a) fixing just because a high CVSS score in NVD only yields negligible risk reduction, (b) the additional existence of proof of concepts exploits (e.g. in EDB) may yield some additional but not large risk reduction, (c) fixing in response to presence in black markets yields the equivalent risk reduction of wearing safety belt in cars (you might also die but still..). On the negative side, our study shows that as industry we miss a metric with high specificity (ruling out vulns for which we shouldn't worry). In order to address the feedback from BlackHat 2013's audience, the final revision (V3) provides additional data in Appendix A detailing how the control variables in the study affect the results.
PaFiMoCS: Particle Filtered Modified-CS and Applications in Visual Tracking across Illumination Change
Venue: arXiv cs.CV 2013
Year: 2013

We study the problem of tracking (causally estimating) a time sequence of sparse spatial signals with changing sparsity patterns, as well as other unknown states, from a sequence of nonlinear observations corrupted by (possibly) non-Gaussian noise. In many applications, particularly those in visual tracking, the unknown state can be split into a small dimensional part, e.g. global motion, and a spatial signal, e.g. illumination or shape deformation. The spatial signal is often well modeled as being sparse in some domain. For a long sequence, its sparsity pattern can change over time, although the changes are usually slow. To address the above problem, we propose a novel solution approach called Particle Filtered Modified-CS (PaFiMoCS). The key idea of PaFiMoCS is to importance sample for the small dimensional state vector, while replacing importance sampling by slow sparsity pattern change constrained posterior mode tracking for recovering the sparse spatial signal. We show that the problem of tracking moving objects across spatially varying illumination change is an example of the above problem and explain how to design PaFiMoCS for it. Experiments on both simulated data as well as on real videos with significant illumination changes demonstrate the superiority of the proposed algorithm as compared with existing particle filter based tracking algorithms.
Language ASP{f} with Arithmetic Expressions and Consistency-Restoring Rules
Venue: arXiv cs.AI 2013
Year: 2013

In this paper we continue the work on our extension of Answer Set Programming by non-Herbrand functions and add to the language support for arithmetic expressions and various inequality relations over non-Herbrand functions, as well as consistency-restoring rules from CR-Prolog. We demonstrate the use of this latest version of the language in the representation of important kinds of knowledge.
A Dual Number Approach for Numerical Calculation of Velocity and Acceleration in the Spherical 4R Mechanism
Venue: arXiv cs.CE 2013
Year: 2013

This paper proposes a methodology to calculate both the first and second derivatives of a vector function of one variable in a single computation step. The method is based on the nested application of the dual number approach for first order derivatives. It has been implemented in Fortran language, a module which contains the dual version of elementary functions as well as more complex functions, which are common in the field of rotational kinematics. Since we have three quantities of interest, namely the function itself and its first and second derivative, our basic numerical entity has three elements. Then, for a given vector function $f:\mathbb{R}\to \mathbb{R}^m$, its dual version will have the form $\tilde{f}:\mathbb{R}^3\to \mathbb{R}^{3m}$. As a study case, the proposed methodology is used to calculate the velocity and acceleration of a point moving on the coupler-point curve generated by a spherical four-bar mechanism.
Composition Closure of Linear Extended Top-down Tree Transducers
Venue: arXiv cs.FL 2013
Year: 2013

Linear extended top-down tree transducers (or synchronous tree-substitution grammars) are popular formal models of tree transformations. The expressive power of compositions of such transducers with and without regular look-ahead is investigated. In particular, the restrictions of nondeletion, epsilon-freeness, and strictness are considered. The composition hierarchy turns out to be finite for all epsilon-free (all rules consume input) variants of these transducers except for nondeleting epsilon-free linear extended top-down tree transducers. The least number of transducers needed for the full expressive power of arbitrary compositions is presented. In all remaining cases (including nondeleting epsilon-free linear extended top-down tree transducers) the composition hierarchy does not collapse.
Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
Venue: arXiv cs.DS 2013
Year: 2013

We give an algebraic, determinant-based algorithm for the K-Cycle problem, i.e., the problem of finding a cycle through a set of specified elements. Our approach gives a simple FPT algorithm for the problem, matching the $O^*(2^{|K|})$ running time of the algorithm of Björklund et al. (SODA, 2012). Furthermore, our approach is open for treatment by classical algebraic tools (e.g., Gaussian elimination), and we show that it leads to a polynomial compression of the problem, i.e., a polynomial-time reduction of the $K$-Cycle problem into an algebraic problem with coding size $O(|K|^3)$. This is surprising, as several related problems (e.g., k-Cycle and the Disjoint Paths problem) are known not to admit such a reduction unless the polynomial hierarchy collapses. Furthermore, despite the result, we are not aware of any witness for the K-Cycle problem of size polynomial in $|K|+\log n$, which seems (for now) to separate the notions of polynomial compression and polynomial kernelization (as a polynomial kernelization for a problem in NP necessarily implies a small witness).
Influence Of The User Importance Measure On The Group Evolution Discovery
Venue: arXiv cs.SI 2013
Year: 2013

One of the most interesting topics in social network science are social groups. Their extraction, dynamics and evolution. One year ago the method for group evolution discovery (GED) was introduced. The GED method during extraction process takes into account both the group members quality and quantity. The quality is reflected by user importance measure. In this paper the influence of different user importance measures on the results of the GED method is examined and presented. The results indicate that using global measures like social position (page rank) allows to achieve more precise results than using local measures like degree centrality or no measure at all.
Two Design Issues in Cognitive Sub-Small Cell for Sojourners
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we propound a solution named Cognitive Sub-Small Cell for Sojourners (CSCS) in allusion to a broadly representative small cell scenario, where users can be categorized into two groups: sojourners and inhabitants. CSCS contributes to save energy, enhance the number of concurrently supportable users and enshield inhabitants. We consider two design issues in CSCS: i) determining the number of transmit antennas on sub-small cell APs; ii) controlling downlink inter-sub-small cell interference. For issue i), we excogitate an algorithm helped by the probability distribution of the number of concurrent sojourners. For issue ii), we propose an interference control scheme named BDBF: Block Diagonalization (BD) Precoding based on uncertain channel state information in conjunction with auxiliary optimal Beamformer (BF). In the simulation, we delve into the issue: how the factors impact the number of transmit antennas on sub-small cell APs. Moreover, we verify a significant conclusion: Using BDBF gains more capacity than using optimal BF alone within a bearably large radius of uncertainty region.
Partial Orders for Efficient BMC of Concurrent Software
Venue: arXiv cs.LO 2013
Year: 2013

The vast number of interleavings that a concurrent program can have is typically identified as the root cause of the difficulty of automatic analysis of concurrent software. Weak memory is generally believed to make this problem even harder. We address both issues by modelling programs' executions with partial orders rather than the interleaving semantics (SC). We implemented a software analysis tool based on these ideas. It scales to programs of sufficient size to achieve first-time formal verification of non-trivial concurrent systems code over a wide range of models, including SC, Intel x86 and IBM Power.
Driving an NP-Complete problem with Combinatorial Decomposition to generate a unique and irreversible bitstring from a single integer seed value
Venue: arXiv cs.CR 2013
Year: 2013

Generation of an (arbitrarily) long string of bits unique to a given finite-length numerical seed is of great value in the field of random number generation, computer simulations, and other areas of computer science. Extending this idea such that the bitstring cannot be reverse-engineered to recover the original seed value extends the value of such a system to the field of cryptography, as the string can be used directly as an encryption mask, or as the input to some other cryptographic function. The longer the string that can be generated, the closer the system would come to the ideal cryptographic case of the One Time Pad. In this paper we propose a scheme for taking an initial seed (nominally a 128-bit integer, but not restricted to such), and expanding this into a unique bitstring of a length determined by a limit cycle that makes it useful in practical applications. We utilize novel mathematical concepts such as combinatorial decomposition to turn the seed value into unique rotations of a pre-defined table, which are operated on via destructive functions such as exclusive-OR (XOR) and add-with-carry (ADC) to eventually produce the unique bitstring. We assert that the process of iterating the XOR or ADC operation conforms to the known NP-complete problem known as Subset-Sum, meaning that the reversal of the process that produced the bitstring is tantamount to solving the NP-Complete Subset-Sum problem, which in turn is less efficient than the brute-force method of testing every seed value until the corresponding bitstring is found, making the system highly relevant in a cryptographic context.
Syntactic Analysis Based on Morphological Characteristic Features of the Romanian Language
Venue: arXiv cs.CL 2013
Year: 2013

This paper refers to the syntactic analysis of phrases in Romanian, as an important process of natural language processing. We will suggest a real-time solution, based on the idea of using some words or groups of words that indicate grammatical category; and some specific endings of some parts of sentence. Our idea is based on some characteristics of the Romanian language, where some prepositions, adverbs or some specific endings can provide a lot of information about the structure of a complex sentence. Such characteristics can be found in other languages, too, such as French. Using a special grammar, we developed a system (DIASEXP) that can perform a dialogue in natural language with assertive and interogative sentences about a "story" (a set of sentences describing some events from the real life).
In-situ associative permuting
Venue: arXiv cs.DS 2013
Year: 2013

The technique of in-situ associative permuting is introduced which is an association of in-situ permuting and in-situ inverting. It is suitable for associatively permutable permutations of {1,2,...,n} where the elements that will be inverted are negative and stored in order relative to each other according to their absolute values. Let K[1...n] be an array of n integer keys each in the range [1,n], and it is allowed to modify the keys in the range [-n,n]. If the integer keys are rearranged such that one of each distinct key having the value i is moved to the i'th position of K, then the resulting arrangement (will be denoted by K^P) can be transformed in-situ into associatively permutable permutation pi^P using only logn additional bits. The associatively permutable permutation pi^P not only stores the ranks of the keys of K^P but also uniquely represents K^P. Restoring the keys from pi^P is not considered. However, in-situ associative permuting pi^P in O(n) time using logn additional bits rearranges the elements of pi^P in order, as well as lets to restore the keys of K^P in O(n) further time using the inverses of the negative ranks. This means that an array of n integer keys each in the range [1,n] can be sorted using only logn bits of additional space.
A Paraconsistent Tableau Algorithm Based on Sign Transformation in Semantic Web
Venue: arXiv cs.AI 2013
Year: 2013

In an open, constantly changing and collaborative environment like the forthcoming Semantic Web, it is reasonable to expect that knowledge sources will contain noise and inaccuracies. It is well known, as the logical foundation of the Semantic Web, description logic is lack of the ability of tolerating inconsistent or incomplete data. Recently, the ability of paraconsistent approaches in Semantic Web is weaker in this paper, we present a tableau algorithm based on sign transformation in Semantic Web which holds the stronger ability of reasoning. We prove that the tableau algorithm is decidable which hold the same function of classical tableau algorithm for consistent knowledge bases.