OpenRaiser/Intern-Atlas huggingface dataset:
Review on the Advancements of DNA Cryptography
Venue: arXiv cs.CR 2010
Year: 2010

Since security is one of the most important issues, the evolve of cryptography and cryptographic analysis are considered as the fields of on-going research. The latest development on this field is DNA cryptography. It has emerged after the disclosure of computational ability of Deoxyribo Nucleic Acid (DNA). DNA cryptography uses DNA as the computational tool along with several molecular techniques to manipulate it. Due to very high storage capacity of DNA, this field is becoming very promising. Currently it is in the development phase and it requires a lot of work and research to reach a mature stage. By reviewing all the potential and cutting edge technology of current research, this paper shows the directions that need to be addressed further in the field of DNA cryptography.
Effects of Single-Cycle Structure on Iterative Decoding for Low-Density Parity-Check Codes
Venue: arXiv cs.IT 2010
Year: 2010

We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes and belief propagation (BP) decoding. For fixed numbers of BP iterations, the bit error probability approaches a limit as blocklength tends to infinity, and the limit is obtained via density evolution. On the other hand, the difference between the bit error probability of codes with blocklength $n$ and that in the large blocklength limit is asymptotically $α(ε,t)/n + Θ(n^{-2})$ where $α(ε,t)$ denotes a specific constant determined by the code ensemble considered, the number $t$ of iterations, and the erasure probability $ε$ of the BEC. In this paper, we derive a set of recursive formulas which allows evaluation of the constant $α(ε,t)$ for standard irregular ensembles. The dominant difference $α(ε,t)/n$ can be considered as effects of cycle-free and single-cycle structures of local graphs. Furthermore, it is confirmed via numerical simulations that estimation of the bit error probability using $α(ε,t)$ is accurate even for small blocklengths.
Distributed Storage Codes Meet Multiple-Access Wiretap Channels
Venue: arXiv cs.IT 2010
Year: 2010

We consider {\it i)} the overhead minimization of maximum-distance separable (MDS) storage codes for the repair of a single failed node and {\it ii)} the total secure degrees-of-freedom (S-DoF) maximization in a multiple-access compound wiretap channel. We show that the two problems are connected. Specifically, the overhead minimization for a single node failure of an {\it optimal} MDS code, i.e. one that can achieve the information theoretic overhead minimum, is equivalent to maximizing the S-DoF in a multiple-access compound wiretap channel. Additionally, we show that maximizing the S-DoF in a multiple-access compound wiretap channel is equivalent to minimizing the overhead of an MDS code for the repair of a departed node. An optimal MDS code maps to a full S-DoF channel and a full S-DoF channel maps to an MDS code with minimum repair overhead for one failed node. We also state a general framework for code-to-channel and channel-to-code mappings and performance bounds between the two settings. The underlying theme for all connections presented is interference alignment (IA). The connections between the two problems become apparent when we restate IA as an optimization problem. Specifically, we formulate the overhead minimization and the S-DoF maximization as rank constrained, sum-rank and max-rank minimization problems respectively. The derived connections allow us to map repair strategies of recently discovered repair codes to beamforming matrices and characterize the maximum S-DoF for the single antenna multiple-access compound wiretap channel.
Back To The Future: On Predicting User Uptime
Venue: arXiv cs.NI 2010
Year: 2010

Correlation in user connectivity patterns is generally considered a problem for system designers, since it results in peaks of demand and also in the scarcity of resources for peer-to-peer applications. The other side of the coin is that these connectivity patterns are often predictable and that, to some extent, they can be dealt with proactively. In this work, we build predictors aiming to determine the probability that any given user will be online at any given time in the future. We evaluate the quality of these predictors on various large traces from instant messaging and file sharing applications. We also illustrate how availability prediction can be applied to enhance the behavior of peer-to-peer applications: we show through simulation how data availability is substantially increased in a distributed hash table simply by adjusting data placement policies according to peer availability prediction and without requiring any additional storage from any peer.
A Platform-independent Programming Environment for Robot Control
Venue: arXiv cs.RO 2010
Year: 2010

The development of robot control programs is a complex task. Many robots are different in their electrical and mechanical structure which is also reflected in the software. Specific robot software environments support the program development, but are mainly text-based and usually applied by experts in the field with profound knowledge of the target robot. This paper presents a graphical programming environment which aims to ease the development of robot control programs. In contrast to existing graphical robot programming environments, our approach focuses on the composition of parallel action sequences. The developed environment allows to schedule independent robot actions on parallel execution lines and provides mechanism to avoid side-effects of parallel actions. The developed environment is platform-independent and based on the model-driven paradigm. The feasibility of our approach is shown by the application of the sequencer to a simulated service robot and a robot for educational purpose.
Improved Methods For Generating Quasi-Gray Codes
Venue: arXiv cs.DM 2010
Year: 2010

Consider a sequence of bit strings of length d, such that each string differs from the next in a constant number of bits. We call this sequence a quasi-Gray code. We examine the problem of efficiently generating such codes, by considering the number of bits read and written at each generating step, the average number of bits read while generating the entire code, and the number of strings generated in the code. Our results give a trade-off between these constraints, and present algorithms that do less work on average than previous results, and that increase the number of bit strings generated.
Signal Space Alignment for an Encryption Message and Successive Network Code Decoding on the MIMO K-way Relay Channel
Venue: arXiv cs.IT 2010
Year: 2010

This paper investigates a network information flow problem for a multiple-input multiple-output (MIMO) Gaussian wireless network with $K$-users and a single intermediate relay having $M$ antennas. In this network, each user intends to convey a multicast message to all other users while receiving $K-1$ independent messages from the other users via an intermediate relay. This network information flow is termed a MIMO Gaussian $K$-way relay channel. For this channel, we show that $\frac{K}{2}$ degrees of freedom is achievable if $M=K-1$. To demonstrate this, we come up with an encoding and decoding strategy inspired from cryptography theory. The proposed encoding and decoding strategy involves a \textit{signal space alignment for an encryption message} for the multiple access phase (MAC) and \textit{zero forcing with successive network code decoding} for the broadcast (BC) phase. The idea of the \emph{signal space alignment for an encryption message} is that all users cooperatively choose the precoding vectors to transmit the message so that the relay can receive a proper encryption message with a special structure, \textit{network code chain structure}. During the BC phase, \emph{zero forcing combined with successive network code decoding} enables all users to decipher the encryption message from the relay despite the fact that they all have different self-information which they use as a key.
Un Algorithme génétique pour le problème de ramassage et de livraison avec fenêtres de temps à plusieurs véhicules
Venue: arXiv cs.NE 2010
Year: 2010

The PDPTW is an optimization vehicles routing problem which must meet requests for transport between suppliers and customers satisfying precedence, capacity and time constraints. We present, in this paper, a genetic algorithm for optimization of a multi pickup and delivery problem with time windows (m-PDPTW). We purposes a brief literature review of the PDPTW, present an approach based on genetic algorithms to give a satisfying solution to the m-PDPTW minimizing the total travel cost.
Mixed integer programming for the resolution of GPS carrier phase ambiguities
Venue: arXiv cs.IT 2010
Year: 2010

This arXiv upload is to clarify that the now well-known sorted QR MIMO decoder was first presented in the 1995 IUGG General Assembly. We clearly go much further in the sense that we directly incorporated reduction into this one step, non-exact suboptimal integer solution. Except for these first few lines up to this point, this paper is an unaltered version of the paper presented at the IUGG1995 Assembly in Boulder. Ambiguity resolution of GPS carrier phase observables is crucial in high precision geodetic positioning and navigation applications. It consists of two aspects: estimating the integer ambiguities in the mixed integer observation model and examining whether they are sufficiently accurate to be fixed as known nonrandom integers. We shall discuss the first point in this paper from the point of view of integer programming. A one-step nonexact approach is proposed by employing minimum diagonal pivoting Gaussian decompositions, which may be thought of as an improvement of the simple rounding-off method, since the weights and correlations of the floating-estimated ambiguities are fully taken into account. The second approach is to reformulate the mixed integer least squares problem into the standard 0-1 linear integer programming model, which can then be solved by using, for instance, the practically robust and efficient simplex algorithm for linear integer programming. It is exact, if proper bounds for the ambiguities are given. Theoretical results on decorrelation by unimodular transformation are given in the form of a theorem.
An Explicit Framework for Interaction Nets
Venue: arXiv cs.LO 2010
Year: 2010

Interaction nets are a graphical formalism inspired by Linear Logic proof-nets often used for studying higher order rewriting e.g. \Beta-reduction. Traditional presentations of interaction nets are based on graph theory and rely on elementary properties of graph theory. We give here a more explicit presentation based on notions borrowed from Girard's Geometry of Interaction: interaction nets are presented as partial permutations and a composition of nets, the gluing, is derived from the execution formula. We then define contexts and reduction as the context closure of rules. We prove strong confluence of the reduction within our framework and show how interaction nets can be viewed as the quotient of some generalized proof-nets.
Faster Polynomial Multiplication via Discrete Fourier Transforms
Venue: arXiv cs.CC 2010
Year: 2010

We study the complexity of polynomial multiplication over arbitrary fields. We present a unified approach that generalizes all known asymptotically fastest algorithms for this problem. In particular, the well-known algorithm for multiplication of polynomials over fields supporting DFTs of large smooth orders, Schönhage-Strassen's algorithm over arbitrary fields of characteristic different from 2, Schönhage's algorithm over fields of characteristic 2, and Cantor-Kaltofen's algorithm over arbitrary algebras---all appear to be instances of this approach. We also obtain faster algorithms for polynomial multiplication over certain fields which do not support DFTs of large smooth orders. We prove that the Schönhage-Strassen's upper bound cannot be improved further over the field of rational numbers if we consider only algorithms based on consecutive applications of DFT, as all known fastest algorithms are. We also explore the ways to transfer the recent Fürer's algorithm for integer multiplication to the problem of polynomial multiplication over arbitrary fields of positive characteristic. This work is inspired by the recent improvement for the closely related problem of complexity of integer multiplication by Fürer and its consequent modular arithmetic treatment due to De, Kurur, Saha, and Saptharishi. We explore the barriers in transferring the techniques for solutions of one problem to a solution of the other.
Automatic Verification of Parametric Specifications with Complex Topologies
Venue: arXiv cs.SE 2010
Year: 2010

The focus of this paper is on reducing the complexity in verification by exploiting modularity at various levels: in specification, in verification, and structurally. For specifications, we use the modular language CSP-OZ-DC, which allows us to decouple verification tasks concerning data from those concerning durations. At the verification level, we exploit modularity in theorem proving for rich data structures and use this for invariant checking. At the structural level, we analyze possibilities for modular verification of systems consisting of various components which interact.We illustrate these ideas by automatically verifying safety properties of a case study from the European Train Control System standard, which extends previous examples by comprising a complex track topology with lists of track segments and trains with different routes.
On the number of solutions of the discretizable molecular distance geometry problem
Venue: arXiv cs.DM 2010
Year: 2010

The Generalized Discretizable Molecular Distance Geometry Problem is a distance geometry problems that can be solved by a combinatorial algorithm called ``Branch-and-Prune''. It was observed empirically that the number of solutions of YES instances is always a power of two. We give a proof that this event happens with probability one.
Link power coordination for energy conservation in complex communication networks
Venue: arXiv cs.NI 2010
Year: 2010

Communication networks consume huge, and rapidly growing, amount of energy. However, a lot of the energy consumption is wasted due to the lack of global link power coordination in these complex systems. This paper proposes several link power coordination schemes to achieve energy-efficient routing by progressively putting some links into energy saving mode and hence aggregating traffic during periods of low traffic load. We show that the achievable energy savings not only depend on the link power coordination schemes, but also on the network topologies. In the random network, there is no scheme that can significantly outperform others. In the scale-free network, when the largest betweenness first (LBF) scheme is used, phase transition of the networks' transmission capacities during the traffic cooling down phase is observed. Motivated by this, a hybrid link power coordination scheme is proposed to significantly reduce the energy consumption in the scale-free network. In a real Internet Service Provider (ISP)'s router-level Internet topology, however, the smallest betweenness first (SBF) scheme significantly outperforms other schemes.
Transdichotomous Results in Computational Geometry, II: Offline Search
Venue: arXiv cs.DS 2010
Year: 2010

We reexamine fundamental problems from computational geometry in the word RAM model, where input coordinates are integers that fit in a machine word. We develop a new algorithm for offline point location, a two-dimensional analog of sorting where one needs to order points with respect to segments. This result implies, for example, that the convex hull of n points in three dimensions can be constructed in (randomized) time n 2^O(sqrt{lglg n}). Similar bounds hold for numerous other geometric problems, such as planar Voronoi diagrams, planar off-line nearest neighbor search, line segment intersection, and triangulation of non-simple polygons. In FOCS'06, we developed a data structure for online point location, which implied a bound of O(n lg n/lglg n) for three-dimensional convex hulls and the other problems. Our current bounds are dramatically better, and a convincing improvement over the classic O(nlg n) algorithms. As in the field of integer sorting, the main challenge is to find ways to manipulate information, while avoiding the online problem (in that case, predecessor search).
Ontological Matchmaking in Recommender Systems
Venue: arXiv cs.DB 2010
Year: 2010

The electronic marketplace offers great potential for the recommendation of supplies. In the so called recommender systems, it is crucial to apply matchmaking strategies that faithfully satisfy the predicates specified in the demand, and take into account as much as possible the user preferences. We focus on real-life ontology-driven matchmaking scenarios and identify a number of challenges, being inspired by such scenarios. A key challenge is that of presenting the results to the users in an understandable and clear-cut fashion in order to facilitate the analysis of the results. Indeed, such scenarios evoke the opportunity to rank and group the results according to specific criteria. A further challenge consists of presenting the results to the user in an asynchronous fashion, i.e. the 'push' mode, along with the 'pull' mode, in which the user explicitly issues a query, and displays the results. Moreover, an important issue to consider in real-life cases is the possibility of submitting a query to multiple providers, and collecting the various results. We have designed and implemented an ontology-based matchmaking system that suitably addresses the above challenges. We have conducted a comprehensive experimental study, in order to investigate the usability of the system, the performance and the effectiveness of the matchmaking strategies with real ontological datasets.
Optimizing real world applications with GCC Link Time Optimization
Venue: arXiv cs.PL 2010
Year: 2010

GCC has a new infrastructure to support a link time optimization (LTO). The infrastructure is designed to allow linking of large applications using a special mode (WHOPR) which support parallelization of the compilation process. In this paper we present overview of the design and implementation of WHOPR and present test results of its behavior when optimizing large applications. We give numbers on compile time, memory usage and code quality comparisons to the classical file by file based optimization model. In particular we focus on Firefox web browser. We show main problems seen only when compiling a large application, such as startup time and code size growth.
Using Context Dependent Semantic Similarity to Browse Information Resources: an Application for the Industrial Design
Venue: arXiv cs.DL 2010
Year: 2010

This paper deals with the semantic interpretation of information resources (e.g., images, videos, 3D models). We present a case study of an approach based on semantic and context dependent similarity applied to the industrial design. Different application contexts are considered and modelled to browse a repository of 3D digital objects according to different perspectives. The paper briefly summarises the basic concepts behind the semantic similarity approach and illustrates its application and results.
On Designing Multicore-aware Simulators for Biological Systems
Venue: arXiv cs.DC 2010
Year: 2010

The stochastic simulation of biological systems is an increasingly popular technique in bioinformatics. It often is an enlightening technique, which may however result in being computational expensive. We discuss the main opportunities to speed it up on multi-core platforms, which pose new challenges for parallelisation techniques. These opportunities are developed in two general families of solutions involving both the single simulation and a bulk of independent simulations (either replicas of derived from parameter sweep). Proposed solutions are tested on the parallelisation of the CWC simulator (Calculus of Wrapped Compartments) that is carried out according to proposed solutions by way of the FastFlow programming framework making possible fast development and efficient execution on multi-cores.
Collaborative Trust: A Novel Paradigm of Trusted Mobile Computing
Venue: arXiv cs.CR 2010
Year: 2010

With increasing complexity of modern-day mobile devices, security of these devices in presence of myriad attacks by an intelligent adversary is becoming a major issue. The vast majority of cell phones still remain unsecured from many existing and emerging security threats. To address the security threats in mobile devices we are exploring a technology, which we refer as "Collaborative Trust". It is a technology that uses a system of devices cooperating with each other (working in a fixed or ad-hoc network) to achieve the individual security of each device. The idea is that each device is insecure by itself, since in many cases it is incapable of checking its safety by itself (e.g. when it is compromised it may lose its ability to monitor its own trustworthiness), but together, they can ensure each other's security in a collaborative manner.
Fractional Repetition Codes for Repair in Distributed Storage Systems
Venue: arXiv cs.IT 2010
Year: 2010

We introduce a new class of exact Minimum-Bandwidth Regenerating (MBR) codes for distributed storage systems, characterized by a low-complexity uncoded repair process that can tolerate multiple node failures. These codes consist of the concatenation of two components: an outer MDS code followed by an inner repetition code. We refer to the inner code as a Fractional Repetition code since it consists of splitting the data of each node into several packets and storing multiple replicas of each on different nodes in the system. Our model for repair is table-based, and thus, differs from the random access model adopted in the literature. We present constructions of Fractional Repetition codes based on regular graphs and Steiner systems for a large set of system parameters. The resulting codes are guaranteed to achieve the storage capacity for random access repair. The considered model motivates a new definition of capacity for distributed storage systems, that we call Fractional Repetition capacity. We provide upper bounds on this capacity while a precise expression remains an open problem.
ASMs and Operational Algorithmic Completeness of Lambda Calculus
Venue: arXiv cs.LO 2010
Year: 2010

We show that lambda calculus is a computation model which can step by step simulate any sequential deterministic algorithm for any computable function over integers or words or any datatype. More formally, given an algorithm above a family of computable functions (taken as primitive tools, i.e., kind of oracle functions for the algorithm), for every constant K big enough, each computation step of the algorithm can be simulated by exactly K successive reductions in a natural extension of lambda calculus with constants for functions in the above considered family. The proof is based on a fixed point technique in lambda calculus and on Gurevich sequential Thesis which allows to identify sequential deterministic algorithms with Abstract State Machines. This extends to algorithms for partial computable functions in such a way that finite computations ending with exceptions are associated to finite reductions leading to terms with a particular very simple feature.