OpenRaiser/Intern-Atlas huggingface dataset:
Types for BioAmbients
Venue: arXiv cs.CE 2010
Year: 2010

The BioAmbients calculus is a process algebra suitable for representing compartmentalization, molecular localization and movements between compartments. In this paper we enrich this calculus with a static type system classifying each ambient with group types specifying the kind of compartments in which the ambient can stay. The type system ensures that, in a well-typed process, ambients cannot be nested in a way that violates the type hierarchy. Exploiting the information given by the group types, we also extend the operational semantics of BioAmbients with rules signalling errors that may derive from undesired ambients' moves (i.e. merging incompatible tissues). Thus, the signal of errors can help the modeller to detect and locate unwanted situations that may arise in a biological system, and give practical hints on how to avoid the undesired behaviour.
What are suspicious VoIP delays?
Venue: arXiv cs.CR 2010
Year: 2010

Voice over IP (VoIP) is unquestionably the most popular real-time service in IP networks today. Recent studies have shown that it is also a suitable carrier for information hiding. Hidden communication may pose security concerns as it can lead to confidential information leakage. In VoIP, RTP (Real-time Transport Protocol) in particular, which provides the means for the successful transport of voice packets through IP networks, is suitable for steganographic purposes. It is characterised by a high packet rate compared to other protocols used in IP telephony, resulting in a potentially high steganographic bandwidth. The modification of an RTP packet stream provides many opportunities for hidden communication as the packets may be delayed, reordered or intentionally lost. In this paper, to enable the detection of steganographic exchanges in VoIP, we examined real RTP traffic traces to answer the questions, what do the "normal" delays in RTP packet streams look like? and, is it possible to detect the use of known RTP steganographic methods based on this knowledge?
Deterministic Sample Sort For GPUs
Venue: arXiv cs.DC 2010
Year: 2010

We present and evaluate GPU Bucket Sort, a parallel deterministic sample sort algorithm for many-core GPUs. Our method is considerably faster than Thrust Merge (Satish et.al., Proc. IPDPS 2009), the best comparison-based sorting algorithm for GPUs, and it is as fast as the new randomized sample sort for GPUs by Leischner et.al. (to appear in Proc. IPDPS 2010). Our deterministic sample sort has the advantage that bucket sizes are guaranteed and therefore its running time does not have the input data dependent fluctuations that can occur for randomized sample sort.
On linear $q$-ary completely regular codes with $ρ=2$ and dual antipodal
Venue: arXiv cs.IT 2010
Year: 2010

We characterize all linear $q$-ary completely regular codes with covering radius $ρ=2$ when the dual codes are antipodal. These completely regular codes are extensions of linear completely regular codes with covering radius 1, which are all classified. For $ρ=2$, we give a list of all such codes known to us. This also gives the characterization of two weight linear antipodal codes.
Feature Importance in Bayesian Assessment of Newborn Brain Maturity from EEG
Venue: arXiv cs.AI 2010
Year: 2010

The methodology of Bayesian Model Averaging (BMA) is applied for assessment of newborn brain maturity from sleep EEG. In theory this methodology provides the most accurate assessments of uncertainty in decisions. However, the existing BMA techniques have been shown providing biased assessments in the absence of some prior information enabling to explore model parameter space in details within a reasonable time. The lack in details leads to disproportional sampling from the posterior distribution. In case of the EEG assessment of brain maturity, BMA results can be biased because of the absence of information about EEG feature importance. In this paper we explore how the posterior information about EEG features can be used in order to reduce a negative impact of disproportional sampling on BMA performance. We use EEG data recorded from sleeping newborns to test the efficiency of the proposed BMA technique.
Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary
Venue: arXiv cs.DC 2010
Year: 2010

We describe an algorithm for Byzantine agreement that is scalable in the sense that each processor sends only $\tilde{O}(\sqrt{n})$ bits, where $n$ is the total number of processors. Our algorithm succeeds with high probability against an \emph{adaptive adversary}, which can take over processors at any time during the protocol, up to the point of taking over arbitrarily close to a 1/3 fraction. We assume synchronous communication but a \emph{rushing} adversary. Moreover, our algorithm works in the presence of flooding: processors controlled by the adversary can send out any number of messages. We assume the existence of private channels between all pairs of processors but make no other cryptographic assumptions. Finally, our algorithm has latency that is polylogarithmic in $n$. To the best of our knowledge, ours is the first algorithm to solve Byzantine agreement against an adaptive adversary, while requiring $o(n^{2})$ total bits of communication.
Using Information Semantic Systems for Absolutely Secure Processing
Venue: arXiv cs.IT 2010
Year: 2010

Propose a new cryptographic information concept. It allows : - to create absolutely algorithmic unbreakable ciphers for communication through open digital channels; - to create new code-breaking methods. They will be the most efficient decoding methods to-date, with the help of which any of the existing codes could, in principle, be broken, provided it is not absolutely unbreakable.
Transferring a symbolic polynomial expression from \emph{Mathematica} to \emph{Matlab}
Venue: arXiv cs.MS 2010
Year: 2010

A \emph{Mathematica} Notebook is presented which allows for the transfer or any kind of polynomial expression to \emph{Matlab}. The output is formatted in such a way that \emph{Matlab} routines such as "Root" can be readily implemented. Once the Notebook has been executed, only one copy-paste operation in necessary.
Performance Analysis of Uplink & Downlink Transmission in CDMA System
Venue: arXiv cs.NI 2010
Year: 2010

CDMA is a multiple access method in which the user's uses spread spectrum techniques and occupy the entire spectrum whenever they transmit. In wireless communication signal-to-noise ratio (SNR) is the very important parameter that influences the system performance. Any mode of mobile transmission is not free from channel impairment such as noise, interference and fading. This channel impairment caused signal distortion and degradation in SNR.Also there are differences between uplink (forward channel) and downlink (reverse channel).Along with these differences, both the links use different codes for chanellizing the individual users. This paper simulates the expressions for the pdfs of the SNR for both uplink and downlink transmission assuming that the system is operating at an average signal-to-noise ratio is 6dB per information bit.
SLAM : Solutions lexicales automatique pour métaphores
Venue: arXiv cs.CL 2010
Year: 2010

This article presents SLAM, an Automatic Solver for Lexical Metaphors like ?déshabiller* une pomme? (to undress* an apple). SLAM calculates a conventional solution for these productions. To carry on it, SLAM has to intersect the paradigmatic axis of the metaphorical verb ?déshabiller*?, where ?peler? (?to peel?) comes closer, with a syntagmatic axis that comes from a corpus where ?peler une pomme? (to peel an apple) is semantically and syntactically regular. We test this model on DicoSyn, which is a ?small world? network of synonyms, to compute the paradigmatic axis and on Frantext.20, a French corpus, to compute the syntagmatic axis. Further, we evaluate the model with a sample of an experimental corpus of the database of Flexsem
Analytical Evaluation of Unfairness Problem in Wireless LANs
Venue: arXiv cs.NI 2010
Year: 2010

The number of users using wireless Local Area Network is increasing exponentially and their behavior is changing day after day. Nowadays, users of wireless LAN are using huge amount of bandwidth because of the explosive growth of some services and applications such as video sharing. This situation imposes massive pressure on the wireless LAN performance especially in term of fairness among wireless stations. The limited resources are not distributed fairly in saturated conditions. The most important resource is the access point buffer space. This importance is a result of access point being the bottleneck between two different types of networks. These two types are wired network with relatively huge bandwidth and wireless network with much smaller bandwidth. Also the unfairness problem is keep getting worse because of the greedy nature Transmission Control Protocol (TCP). In this paper, we conduct a comprehensive study on wireless LAN dynamics and proposed a new mathematical model that describes the performance and effects of its behavior. We validate the proposed model by using the simulation technique. The proposed model was able to produce very good approximation in most of the cases. It also gave us a great insight into the effective variables in the wireless LAN behavior and what are the dimensions of the unfairness problem.
Analyzing the Low Power Wireless Links for Wireless Sensor Networks
Venue: arXiv cs.NI 2010
Year: 2010

There is now an increased understanding of the need for realistic link layer models in the wireless sensor networks. In this paper, we have used mathematical techniques from communication theory to model and analyze low power wireless links. Our work provides theoretical models for the link layer showing how Packet Reception Rate vary with Signal to Noise Ratio and distance for different modulation schemes and a comparison between MICA2 and TinyNode in terms of PRR.
Less Regret via Online Conditioning
Venue: arXiv cs.LG 2010
Year: 2010

We analyze and evaluate an online gradient descent algorithm with adaptive per-coordinate adjustment of learning rates. Our algorithm can be thought of as an online version of batch gradient descent with a diagonal preconditioner. This approach leads to regret bounds that are stronger than those of standard online gradient descent for general online convex optimization problems. Experimentally, we show that our algorithm is competitive with state-of-the-art algorithms for large scale machine learning problems.
A New Understanding of Prediction Markets Via No-Regret Learning
Venue: arXiv cs.AI 2010
Year: 2010

We explore the striking mathematical connections that exist between market scoring rules, cost function based prediction markets, and no-regret learning. We show that any cost function based prediction market can be interpreted as an algorithm for the commonly studied problem of learning from expert advice by equating trades made in the market with losses observed by the learning algorithm. If the loss of the market organizer is bounded, this bound can be used to derive an O(sqrt(T)) regret bound for the corresponding learning algorithm. We then show that the class of markets with convex cost functions exactly corresponds to the class of Follow the Regularized Leader learning algorithms, with the choice of a cost function in the market corresponding to the choice of a regularizer in the learning problem. Finally, we show an equivalence between market scoring rules and prediction markets with convex cost functions. This implies that market scoring rules can also be interpreted naturally as Follow the Regularized Leader algorithms, and may be of independent interest. These connections provide new insight into how it is that commonly studied markets, such as the Logarithmic Market Scoring Rule, can aggregate opinions into accurate estimates of the likelihood of future events.
Change of word types to word tokens ratio in the course of translation (based on Russian translations of K. Vonnegut novels)
Venue: arXiv cs.CL 2010
Year: 2010

The article provides lexical statistical analysis of K. Vonnegut's two novels and their Russian translations. It is found out that there happen some changes between the speed of word types and word tokens ratio change in the source and target texts. The author hypothesizes that these changes are typical for English-Russian translations, and moreover, they represent an example of Baker's translation feature of levelling out.
Information-Sharing and Privacy in Social Networks
Venue: arXiv cs.GT 2010
Year: 2010

We present a new model for reasoning about the way information is shared among friends in a social network, and the resulting ways in which it spreads. Our model formalizes the intuition that revealing personal information in social settings involves a trade-off between the benefits of sharing information with friends, and the risks that additional gossiping will propagate it to people with whom one is not on friendly terms. We study the behavior of rational agents in such a situation, and we characterize the existence and computability of stable information-sharing networks, in which agents do not have an incentive to change the partners with whom they share information. We analyze the implications of these stable networks for social welfare, and the resulting fragmentation of the social network.
Agent Based Approaches to Engineering Autonomous Space Software
Venue: arXiv cs.MA 2010
Year: 2010

Current approaches to the engineering of space software such as satellite control systems are based around the development of feedback controllers using packages such as MatLab's Simulink toolbox. These provide powerful tools for engineering real time systems that adapt to changes in the environment but are limited when the controller itself needs to be adapted. We are investigating ways in which ideas from temporal logics and agent programming can be integrated with the use of such control systems to provide a more powerful layer of autonomous decision making. This paper will discuss our initial approaches to the engineering of such systems.
Linguistic Geometries for Unsupervised Dimensionality Reduction
Venue: arXiv cs.CL 2010
Year: 2010

Text documents are complex high dimensional objects. To effectively visualize such data it is important to reduce its dimensionality and visualize the low dimensional embedding as a 2-D or 3-D scatter plot. In this paper we explore dimensionality reduction methods that draw upon domain knowledge in order to achieve a better low dimensional embedding and visualization of documents. We consider the use of geometries specified manually by an expert, geometries derived automatically from corpus statistics, and geometries computed from linguistic resources.
Particle Filtering on the Audio Localization Manifold
Venue: arXiv cs.AI 2010
Year: 2010

We present a novel particle filtering algorithm for tracking a moving sound source using a microphone array. If there are N microphones in the array, we track all $N \choose 2$ delays with a single particle filter over time. Since it is known that tracking in high dimensions is rife with difficulties, we instead integrate into our particle filter a model of the low dimensional manifold that these delays lie on. Our manifold model is based off of work on modeling low dimensional manifolds via random projection trees [1]. In addition, we also introduce a new weighting scheme to our particle filtering algorithm based on recent advancements in online learning. We show that our novel TDOA tracking algorithm that integrates a manifold model can greatly outperform standard particle filters on this audio tracking task.
Strategical languages of infinite words
Venue: arXiv cs.GT 2010
Year: 2010

We deal in this paper with strategical languages of infinite words, that is those generated by a nondeterministic strategy in the sense of game theory. We first show the existence of a minimal strategy for such languages, for which we give an explicit expression. Then we characterize the family of strategical languages as that of closed ones, in the topological space of infinite words. Finally, we give a definition of a Nash equilibrium for such languages, that we illustrate with a famous example.
Securing Interactive Sessions Using Mobile Device through Visual Channel and Visual Inspection
Venue: arXiv cs.CR 2010
Year: 2010

Communication channel established from a display to a device's camera is known as visual channel, and it is helpful in securing key exchange protocol. In this paper, we study how visual channel can be exploited by a network terminal and mobile device to jointly verify information in an interactive session, and how such information can be jointly presented in a user-friendly manner, taking into account that the mobile device can only capture and display a small region, and the user may only want to authenticate selective regions-of-interests. Motivated by applications in Kiosk computing and multi-factor authentication, we consider three security models: (1) the mobile device is trusted, (2) at most one of the terminal or the mobile device is dishonest, and (3) both the terminal and device are dishonest but they do not collude or communicate. We give two protocols and investigate them under the abovementioned models. We point out a form of replay attack that renders some other straightforward implementations cumbersome to use. To enhance user-friendliness, we propose a solution using visual cues embedded into the 2D barcodes and incorporate the framework of "augmented reality" for easy verifications through visual inspection. We give a proof-of-concept implementation to show that our scheme is feasible in practice.
On Probabilistic Alternating Simulations
Venue: arXiv cs.LO 2010
Year: 2010

This paper presents simulation-based relations for probabilistic game structures. The first relation is called probabilistic alternating simulation, and the second called probabilistic alternating forward simulation, following the naming convention of Segala and Lynch. We study these relations with respect to the preservation of properties specified in probabilistic alternating-time temporal logic.
Information Flow in One-Dimensional Vehicular Ad Hoc Networks
Venue: arXiv cs.IT 2010
Year: 2010

We consider content distribution in vehicular ad hoc networks. We assume that a file is encoded using fountain code, and the encoded message is cached at infostations. Vehicles are allowed to download data packets from infostations, which are placed along a highway. In addition, two vehicles can exchange packets with each other when they are in proximity. As long as a vehicle has received enough packets from infostations or from other vehicles, the original file can be recovered. In this work, we show that system throughput increases linearly with number of users, meaning that the system exhibits linear scalability. Furthermore, we analyze the effect of mobility on system throughput by considering both discrete and continuous velocity distributions for the vehicles. In both cases, system throughput is shown to decrease when the average speed of all vehicles increases. In other words, higher overall mobility reduces system throughput.
Decreasing log data of multi-tier services for effective request tracing
Venue: arXiv cs.DC 2010
Year: 2010

Previous work shows request tracing systems help understand and debug the performance problems of multi-tier services. However, for large-scale data centers, more than hundreds of thousands of service instances provide online service at the same time. Previous work such as white-box or black box tracing systems will produce large amount of log data, which would be correlated into large quantities of causal paths for performance debugging. In this paper, we propose an innovative algorithm to eliminate valueless logs of multitiers services. Our experiment shows our method filters 84% valueless causal paths and is promising to be used in large-scale data centers.
Verifying Recursive Active Documents with Positive Data Tree Rewriting
Venue: arXiv cs.DB 2010
Year: 2010

This paper proposes a data tree-rewriting framework for modeling evolving documents. The framework is close to Guarded Active XML, a platform used for handling XML repositories evolving through web services. We focus on automatic verification of properties of evolving documents that can contain data from an infinite domain. We establish the boundaries of decidability, and show that verification of a {\em positive} fragment that can handle recursive service calls is decidable. We also consider bounded model-checking in our data tree-rewriting framework and show that it is $\nexptime$-complete.
From Frequency to Meaning: Vector Space Models of Semantics
Venue: arXiv cs.CL 2010
Year: 2010

Computers understand very little of the meaning of human language. This profoundly limits our ability to give instructions to computers, the ability of computers to explain their actions to us, and the ability of computers to analyse and process text. Vector space models (VSMs) of semantics are beginning to address these limits. This paper surveys the use of VSMs for semantic processing of text. We organize the literature on VSMs according to the structure of the matrix in a VSM. There are currently three broad classes of VSMs, based on term-document, word-context, and pair-pattern matrices, yielding three classes of applications. We survey a broad range of applications in these three categories and we take a detailed look at a specific open source project in each category. Our goal in this survey is to show the breadth of applications of VSMs for semantics, to provide a new perspective on VSMs for those who are already familiar with the area, and to provide pointers into the literature for those who are less familiar with the field.
View Synthesis from Schema Mappings
Venue: arXiv cs.DB 2010
Year: 2010

In data management, and in particular in data integration, data exchange, query optimization, and data privacy, the notion of view plays a central role. In several contexts, such as data integration, data mashups, and data warehousing, the need arises of designing views starting from a set of known correspondences between queries over different schemas. In this paper we deal with the issue of automating such a design process. We call this novel problem "view synthesis from schema mappings": given a set of schema mappings, each relating a query over a source schema to a query over a target schema, automatically synthesize for each source a view over the target schema in such a way that for each mapping, the query over the source is a rewriting of the query over the target wrt the synthesized views. We study view synthesis from schema mappings both in the relational setting, where queries and views are (unions of) conjunctive queries, and in the semistructured data setting, where queries and views are (two-way) regular path queries, as well as unions of conjunctions thereof. We provide techniques and complexity upper bounds for each of these cases.
On the symbol error probability of regular polytopes
Venue: arXiv cs.IT 2010
Year: 2010

An exact expression for the symbol error probability of the four-dimensional 24-cell in Gaussian noise is derived. Corresponding expressions for other regular convex polytopes are summarized. Numerically stable versions of these error probabilities are also obtained.